formal languages fibrationally

formal languages fibrationally

[categories]

Date: Mon, 9 Feb 1998 09:39:06 +0100 (MET)
From: Koslowski <koslowj@iti.cs.tu-bs.de>


Dear Colleagues,

  Has anyone come across or have any interest in the following
  fibrational formulation of formal language theory?  This is an
  observation of Robin Cockett during his recent visit to
  Braunschweig.

  Let T be the list monad on set and let set_T be the corresponding
  Kleisli category.  Consider the functor from (set_T)^op to ord that
  maps a set_T-morphism A --f-> B (i.e., a set-function A --f-> T(B)=B^*) 
  to the inverse image function from the power set of B^* to the power
  set of A^* (ordered by inclusion) induced by the unique extension
  \bar f of f.  It corresponds to a bi-fibration  lang --U-> set_T.
  The objects of the category  lang  are pairs <L,V> with V a set and
  L\inc V^* a language over V.  A  lang  morphism from <L,V> to <M,W> is
  a set_T-morphism V --h-> W subject to the requirement that L be
  contained in the inverse image of M under \bar h, or equivalently,
  that the direct image of L under \bar h be contained in M.

  Recall that a language L\inc V^* is of type

    0, if it is generated by some grammar,
    1, it it is generated by a context-sensitive grammar,
    2, it it is generated by a context-free grammar,
    3, if it is generated by a regular grammar.

  Now we may consider the subcategories lang_i of lang, 0<=i<=3, where
  the languages have to be of type i.  Standard results of formal
  language theory tell us that for i\in\{0,2,3\} the restriction of U to
  lang_i still is a bi-fibration, while the restriction of U to lang_1
  still is a fibration, but not a cofibration, since homomorphic
  images of type-1 languages need not be of type 1.  For type-2
  languages, a theorem of Greibach states the existence of a universal
  such, i.e., a context-free language L_{gr} such that every other
  context-free language is a homomorphic pre-image of L_{gr}.  ([HK]
  has a construction of L_{gr} over a 7-element alphabet, but then
  one can of course find another such universal context-free language
  over a 2-element alphabet.)

  References:

  [G] Sheila A. Greibach: The hardest context-free language.  SIAM
      J. Comput. 2(4) December 1973, 304--310

  [HK] G"unter Hotz and Thomas Kretschmer: The power of the Greibach
       normal form.  J. Inf. Process. Cybern. EIK 25 (10) 1989, 507--512

-- 
J"urgen Koslowski       % If I don't see you no more in this world
ITI                     % I meet you in the next world
TU Braunschweig         % and don't be late!
koslowj@iti.cs.tu-bs.de %              Jimi Hendrix (Voodoo Child)