Logic List Mailing Archive

Postdoctoral position on lambda-calculus / higher-order languages, Bordeaux (France), Deadline: 17 July 2011

Post-doctoral position: ANR project Frontiers of RECognizability
(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/[../../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. Snizergues.
emails: salvati@labri.fr, ges@labri.fr