(FREC)
Subject: Recognizability, Lambda-calculus, Higher-order languages}
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/
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/
(go to the ``news'' page)
Contact: S. Salvati, G. Sénizergues.
emails:salvati@labri.fr, ges@labri.fr
Posts
