9 Feb 1998 22:27

## formal languages fibrationally

Date: Mon, 9 Feb 1998 09:39:06 +0100 (MET)
From: Koslowski <koslowj <at> 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 <at> iti.cs.tu-bs.de %              Jimi Hendrix (Voodoo Child)



Gmane