[TYPES] FP and the Chomsky hierarchy

oleg at okmij.org oleg at okmij.org
Fri Dec 19 03:35:43 EST 2014

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


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


(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).

More information about the Types-list mailing list