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)