Summary:
Some generalizations of context-free grammars (resp. pushdown
automata) were proposed in the seventies by Aho (1968,1969). Later on, Maslov (1974,1976) defined
the infinite hierarchy of ``Higher-order pushdown automata'' which extends further the above 
notions.

The hierarchy of OI languages, defined by means of ``higher-order grammars'', based on 
lambda-calculus was introduced by Damm (1982). This hierarchy turned out to be strongly 
linked with the one defined by higher-order p.d.a. (Damma and Goerdt, 1986).

As the study of OI languages and their decidable properties require to express strong invariants 
about higher-order pushdown automata, it may be interesting to use the grammatical presentation 
of higher-order OI languages by means of lambda-terms and try to express these invariants on the 
lambda-terms directly. Indeed, doing so one can benefit from the good understanding of the models 
of simply typed lambda-calculus so as to express the invariants in a more elegant and powerful way.

Thus, the subject of this postdoc pertains to bridging the world of higher-order pushdown automata
with that of lambda-calculus. This bridging can be done with several applications in mind. A first
kind of application could be the generalisation of the result of decidability of the equality of 
deterministic context-free languages to certain higher-order grammars. It could also be the study 
of equations in the lambda-calculus etc ...

Background:
The candidate should have a strong background in theoretical computer science. In particular he/she
should have knowledge in formal language theory, automata and lambda-calculus.

Founding:
The post-doctoral position will be paid around 2090 euros, free of charges, per month.

Location: LaBRI, Bordeaux 1 university, FRANCE http://www.labri.fr/[../../jump.htm?goto=http%3A%2F%2Fwww.labri.fr%2F]

Dates:
Applications must be sent, by email, before 17/07/2011.
The Post Doctoral position would take place Sept. 1st 2011 - Aug. 31st 2012 (not strict).

More Information is on the web site:
http://frec.labri.fr/[../../jump.htm?goto=http%3A%2F%2Ffrec.labri.fr%2F]
(go to the ``news'' page)

Contact: S. Salvati, G. Sénizergues.
emails: salvati@labri.fr, ges@labri.fr