Pierre Bourreau, (Mr)
Email Pierre.Bourreau@gmail.com
Subject
Linguistics (computational linguistics)
PhD Project
Typing games and parsing non-linear context-free lambda-grammars
Abstract categorial grammars (or, equivalently, lambda-grammars) is formalism based on the simply-typed lambda-calculus. These grammars can be described as grammars of such terms and were introduced in order to bring a model of the syntax-semantics interface in natural language, based on two main ideas: the distinction between the tectogrammatical (i.e. the deep structure of an utterance) and phenogrammatical (i.e. the interpretation of this structure) levels in natural languages, which was expressed by Curry; and an algebraic modeling of the principle of compositionality in order to give account of the semantics of a sentence. an idea formalized by Montague. One of the main advantages of abstract categorial grammars is that both the problems of natural language parsing and generation can be tackled under the same problem: parsing abstract categorial grammars. Efficient algorithms were discovered for abstract categorial grammars of linear and almost linear lambda-terms, while it is known the recognition problem is decidable but non-elementary in general. This work focuses on the study of classes of terms for which parsing can still be solved in polynomial time. The results we give are mainly based on two theorems: the coherence theorem which specifies that a given lambda-term in the desired class must be the unique inhabitant of one of its typing; and the subject expansion theorem, which states that two beta-equivalent terms of the desired class must inhabit the same typings. In order to lead the study, we use an alternative representation of both simply-typed lambda-terms and their typings as games. In particular, we will use this representation in order to prove the coherence theorems for new classes of lambda-terms. Thanks to these results, we will show it is possible to build in a direct way, recognizers for grammars of almost affine lambda-terms as Datalog programs.
Conference presentations (5 most important)
On IO-copying and mildly context-sensitive formalisms. Formal Grammmar. Opole, Poland. 2012. Published in Lecture Notes in Computer Science
A Datalog recognizer for almost lambda-CFGs. Mathematics of Language. Nara, Japan. 2011. Published in Lecture Notes in Artificial Intelligence
Game semantics and Uniqueness of Type-Inhabitance on the simply typed lambda-calculus. Typed lambda-calculi and applications. Novi Sad, Serbia. 2011. Published in Lecture Notes in Computer Science
Traitement d’ellipses: deux approches par les grammaires catégorielles abstraites. Traitement automatique du Langage Naturel. Les Sables d’Olonnes, France. 2013.
Can we passe the Turing test using Church’s lambda-calculus? Computing 2011: symposium on 75 years of Turing Machines and Lambda-Calculus. Karlsruhe, Germany. 2011.
Prizes and fellowships
Junior researcher mobility grant 2012 from LaBRI
INRIA – CORDIS fellowship 2007-2010
Last updated
12 Mar 2013