Hello, The following question on sci.math.research didn't get much response, except from M.W. Hopkins himself. Maybe some category theorists can comment on this? (The question was aimed at a general math audience.) =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D M.W. Hopkins' algebraic approach to formal languages http://www.uwm.edu/~whopkins/cs/CompFAQ.txt seems to be based on the following observations: The free monoid construction, so fundamental in formal language theory, is of course part of a monad, with the inclusion of letters as singleton words as unit and the concatenation of strings of words as multplication. Similarly, we have the (covariant) powerset monad with the singleton map as unit and the union operation as multiplication. Its Eilenberg-Moore algebras are just SUP-semilattices (having arbitrary suprema). These monads are linked by a distributive law in the sense of Beck (69): \delta_X : (PX)^* --> P(X^*) maps a string of subsets to the set of words where the i-th letter belongs to the i-th subset. The resulting composite monad has unital quantales a EM-algebras. Moreover, the powerset monad on set lifts to a powerset monad on mon (the category of EM-algebras of the free monoid monad), again with unital quantales as EM-algebras. Passing from powersets PX to sets of finite subsets FX, the distributive law \delta restricts accordingly. The finite powerset monad over set has sup-semilattices as EM-algebras (finite suprema), while its lift to mon has so-called "dioids" as EM-algebras. Now formal language theory *should* be concerned with studying "interesting" submonads - either of the composite of the free monoid monad and the powerset monad over set, - or of the lifted powerset monad over mon. These submonads in turn should "contain" - the composite of the free monoid monad with the sup-semilattice monad over set, respectively - the dioid-monad over mon. "Interesting" submonads would be those which admit a Kleene star operation (which the latter two do not). The least submonad which does just gives rise to regular languages/subset; its EM-Algebras being the Kleene algebras. Is anybody besides M.W. Hopkins actually viewing formal language theory from this angle? This approach stikes me as much cleaner and simpler than what is usually presented in textbooks, but also in the Handbook of Formal Languages. I wouldn't be surprised if this was known to category theorists in the 60's or 70's, but never found its way to the computer scientists (no flame wars, please). =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D While none of this is particularly deep, I find it a very pretty applicatio= n of category theory, one that might win over some computer scientists. -- Juergen --=20 Juergen Koslowski If I don't see you no more on this world ITI, TU Braunschweig I'll meet you on the next one koslowj@iti.cs.tu-bs.de and don't be late! http://www.iti.cs.tu-bs.de/~koslowj Jimi Hendrix (Voodoo Child, SR) 24-Oct-2002 15:37:24 -0300,895;000000000000-00000000