[ The Types Forum (announcements only), http://lists.seas.upenn.edu/mailman/listinfo/types-announce ]
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:salv...@labri.fr, g...@labri.fr