A Datalog recognizer for almost affine lambda-CFGs

Pierre Bourreau 1 Sylvain Salvati 2, 3
3 SIGNES - Linguistic signs, grammar and meaning: computational logic for natural language
Université Sciences et Technologies - Bordeaux 1, CNRS - Centre National de la Recherche Scientifique : UMR5800, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Michel de Montaigne - Bordeaux 3, Inria Bordeaux - Sud-Ouest
Abstract : The recent emergence of linguistic formalisms exclusively based on the simply-typed λ-calculus to represent both syntax and semantics led to the presentation of innovative techniques which apply to both the problems of parsing and generating natural languages. A common feature of these techniques consists in using strong relations between typing properties and syntactic structures of families of simply-typed λ-terms. Among significant results, an efficient algorithm based on Datalog programming is presented in [Kan07] for context-free grammar of almost linear λ-terms, which are linear λ-terms augmented with a restricted form of copy. We present an extension of this method to terms for which deletion is allowed.
Document type :
Conference papers
Springer. Mathematics of Language, Sep 2011, Nara, Japan. 6878, pp.21-38, 2011, <10.1007/978-3-642-23211-4>

Contributor : Pierre Bourreau <>
Submitted on : Wednesday, October 10, 2012 - 4:44:46 PM
Last modification on : Wednesday, September 9, 2015 - 4:36:25 PM
Document(s) archivé(s) le : Friday, January 11, 2013 - 3:42:18 AM


Files produced by the author(s)




Pierre Bourreau, Sylvain Salvati. A Datalog recognizer for almost affine lambda-CFGs. Springer. Mathematics of Language, Sep 2011, Nara, Japan. 6878, pp.21-38, 2011, <10.1007/978-3-642-23211-4>. <hal-00740701>




Record views


Document downloads