[TYPES/announce] Post-doc LaBRI, Bordeaux

[Salvati Sylvain]

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/

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 at labri.fr, ges at labri.fr