[ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]
Representing Chomsky hierarchy in the `natural' for functional
programmers way (as a type-restricted linear lambda-calculus) is one of
the attractions of the so-called Abstract Categorial Grammar (ACG)
formalism. It is being developed by Philippe de Groote and
collaborators. One can find many pointers on the ACG home page
http://www.loria.fr/equipes/calligramme/acg/
The specific question about Chomsky hierarchy and the orders of types
in ACG is answered on slide 44 (PDF page 44) of the following course
http://www.loria.fr/equipes/calligramme/acg/publications/esslli-09/2009-esslli-acg-week-1-day-3.pdf
(Of course one have to read previous slides to understand the L(n,m)
notation). Slide 56 talks about the hierarchy of tree
languages (rather than string languages) and the open problems.
Incidentally, ACG turns out to closely related to the Tagless-Final
approach (as Philippe de Groote himself told me).
lmpx.com only provides a reader for public news (NNTP) servers. It is not
affiliated with the servers or forums shown here and is not responsible for
the content of articles, which is written by their respective authors.