Publications

Books and Proceedings

• Denis Béchet and Alexandre Dikovsky, editors. BibTeX DOI URL
  Logical Aspects of Computational Linguistics, 7th International Conference, LACL 2012, Nantes, France, July 2-4, 2012, Proceedings.
  In volume 7351 of Lecture Notes in Computer Science (LNCS), Springer-Verlag, 2012. ISBN 978-3-642-31261-8.
  
  

Book Chapters

• Denis Béchet. BibTeX Draft DOI
  NP-Completeness of Grammars Based upon Products of Free Pregroups.
  In Claudia Casadio, Bob Coecke, Michael Moortgat, and Philip Scott, editors, Categories and Types in Logic, Language, and Physics, Essays Dedicated to Jim Lambek on the Occasion of His 90th Birthday, volume 8222 of Lecture Notes in Computer Science (LNCS), pages 51–62. Springer-Verlag, 2014. ISBN 978-3-642-54788-1.
  

  Pregroup grammars are context-free lexicalized grammars based upon free pregroups which can describe parts of the syntax of natural languages. Some extensions are useful to model special constructions like agreements with complex features or non-projective relations or dependencies. A simple solution for these problems is given by lexicalized grammars based upon the product of free pregroups rather than on a single free pregroup. Such grammars are not necessarily context-free. However, the membership problem is NP-complete. To prove this theorem, the article defines a particular grammar built on the product of three free pregroups. This grammar is used to encode any SAT problem as a membership problem in the language corresponding to the grammar.

• Denis Béchet, Alexander Dikovsky, and Ophélie Lacroix. BibTeX Draft DOI
  ``CDG Lab'': an Integrated Environment for Categorial Dependency Grammar and Dependency Treebank Development.
  In Kim Gerdes, Eva Hajičová, and Leo Wanner, editors, Computational Dependency Theory, volume 258 of Frontiers in Artificial Intelligence and Applications, pages 153–169. IOS Press, 2014. ISBN 978-1-61499-351-3.
  

  We present ``CDG Lab'', an integrated environment for development of dependency grammars and treebanks. It uses the Categorial Dependency Grammars (CDG) as a formal model of dependency grammars. CDG are very expressive. They generate unlimited dependency structures, are analyzed in polynomial time and are conservatively extendable by regular type expressions without loss of parsing efficiency. Due to these features, they are well adapted to definition of large scale grammars. CDG Lab supports the analysis of correctness of treebanks developed in parallel with evolving grammars.

• Denis Béchet, Alexander Dikovsky, Annie Foret, and Emmanuelle Garel. BibTeX Draft
  Introduction of Option and Iteration into Pregroup Grammars.
  In Claudia Casadio and Joachim Lambek, editors, Computational Algebraic Approaches to Natural Language, pages 85–107. Polimetrica, Monza (Milan), Italy, 2008. ISBN 978-88-7699-125-7.
  

  Pregroup grammars are a context-free grammar formalism which may be used to describe the syntax of natural languages. However, this formalism is not able to naturally define the types of optional or iterated arguments like optional verb complements or its iterated optional circumstantials. In this paper are introduced and formalized two constructions that make up for this inadequacy without loss of efficiency.

International Journal Articles

• Denis Béchet and Annie Foret. BibTeX DOI URL
  Incremental learning of iterated dependencies.
  Machine Learning, March 2021. ISSN 1573-0565.
  

  We study some learnability problems in the family of Categorial Dependency Grammars (CDG), a class of categorial grammars defining dependency structures. CDG is a formal system, where types are attached to words, combining the classical categorial grammars’ elimination rules with valency pairing rules defining non-projective (discontinuous) dependencies; very importantly, the elimination rules are naturally extended to the so called “iterated dependencies” expressed by a specific type constructor and related elimination rules. This paper first reviews key points on negative results: even the rigid (one type per word) CDG cannot be learned neither from function/argument structures, nor even from dependency structures themselves. Such negative results prove the impossibility to define a learning algorithm for these grammar classes. Nevertheless, we show that the CDG satisfying reasonable and linguistically valid conditions on the iterated dependencies are incrementally learnable in the limit from dependency structures. We provide algorithms and also discuss these aspects for recent variants of the formalism that allow the inference of CDG from linguistic treebanks.

• Denis Béchet and Michael Dekhtyar. BibTeX DOI URL
  Biography of Alexandre Dikovsky.
  Journal of Logic, Language and Information, 26(4):333–340. Springer Verlag, December 2017. ISSN 0925-8531.
  

  Alexandre Dikovsky is born in Leningrad (St. Petersburg), Russia on August 9, 1945. He died in Nantes, France in the beginning of 2014. He is well known for his significant contributions to the fields of Mathematics, Linguistics, and Informatics. In the course of his career, he published over 100 research papers, 12 book chapters, and participated in numerous national and international projects.

• Denis Béchet, Alexandre Dikovsky, and Annie Foret. BibTeX Draft DOI URL
  Categorial grammars with iterated types form a strict hierarchy of k-valued languages.
  Theoretical Computer Science, 450:22–30, 2012. Selection of articles from Implementation and Application of Automata (CIAA 2011), ISSN 0304-3975.
  

  The notion of k-valued categorial grammars in which every word is associated to at most k types is often used in the field of lexicalized grammars as a fruitful constraint for obtaining interesting properties like the existence of learning algorithms. This constraint is reasonable only when the classes of k-valued grammars correspond to a real hierarchy of generated languages. Such a hierarchy has been established earlier for the classical categorial grammars. In this paper the hierarchy by the k-valued constraint is established in the class of categorial grammars extended with iterated types adapted to express the so called projective dependency structures.

• Denis Béchet and Annie Foret. BibTeX Draft URL
  A Pregroup Toolbox for Parsing and Building Grammars of Natural Languages.
  Linguistic Analysis, 36(1-4):473–482, 2010. ISSN 0098-9053.
  

  Pregroup grammars are a mathematical formalism in the spirit of categorial grammars. They resemble logical formalisms such as the Lambek calculus but have a polynomial parsing algorithm. This paper presents a pregroup toolbox for parsing and building grammars of natural languages, including a parser that uses a tabular approach based on majority partial composition.

• Denis Béchet. BibTeX Draft DOI
  Parsing pregroup grammars and Lambek calculus using partial composition.
  Studia logica, 87(2/3):199–224, 2007. ISSN 0039-3215.
  

  The paper presents a way to transform pregroup grammars into context-free grammars using \em functional composition. The same technique can also be used for the proof-nets of multiplicative cyclic linear logic and for Lambek calculus allowing empty premises.

• Denis Béchet, Annie Foret, and Isabelle Tellier. BibTeX Draft DOI
  Learnability of Pregroup Grammars.
  Studia logica, 87(2/3):225–252, 2007. ISSN 0039-3215.
  

  This paper investigates the learnability by positive examples in the sense of Gold of Pregroup Grammars. In a first part, Pregroup Grammars are presented and a new parsing strategy is proposed. Then, theoretical learnability and non-learnability results for subclasses of Pregroup Grammars are proved. In the last two parts, we focus on learning Pregroup Grammars from a special kind of input called feature-tagged examples. A learning algorithm based on the parsing strategy presented in the first part is given. Its validity is proved and its properties are examplified.

• Denis Béchet and Annie Foret. BibTeX Draft DOI
  k-Valued non-associative Lambek grammars are learnable from generalized functor-argument structures.
  Theoretical Computer Science, 355(2):139–152, 2006. ISSN 0304-3975.
  

  This paper is concerned with learning categorial grammars from positive examples in the model of Gold. Functor-argument structures (written FA) are usual syntactical decompositions of sentences in sub-components distinguishing the functional parts from the argument parts defined in the case of classical categorial grammars also known as AB-grammars. In the case of non-associative type-logical grammars, we propose a similar notion that we call generalized functor-argument structures and we show that these structures capture the essence of non-associative Lambek (NL) calculus without product. We show that (i) rigid and k-valued non-associative Lambek (NL without product) grammars are learnable from generalized functor-argument structured sentences. We also define subclasses of k-valued grammars in terms of arity. We first show that (ii) for each k and each bound on arity the class of FA-arity bounded k-valued NL languages of FA structures is finite and (iii) that FA-arity bounded k-valued NL grammars are learnable both from strings and from FA structures as a corollary. Result (i) is obtained from (ii); this learnability result (i) is interesting and surprising when compared to other results: in fact we also show that (iv) this class has infinite elasticity. Moreover, these classes are very close to classes like rigid associative Lambek grammars learned from natural deduction structured sentences (that are different and much richer than FA or generalized FA) or to k-valued non-associative Lambek grammars unlearnable from strings or even from bracketed strings. Thus, the class of k-valued non-associative Lambek grammars learned from generalized functor-argument sentences is at the frontier between learnable and unlearnable classes of languages.

• Denis Béchet. BibTeX Draft
  Minimality of the correctness criterion for multiplicative proof nets.
  Mathematical Structures in Computer Science, 8:543–558, 1998. ISSN 0960-1295.
  
  

French Journal Articles

• Denis Béchet, Roberto Bonato, Alexandre Dikovsky, Annie Foret, Le Nir, Yannick, Erwan Moreau, Christian Retoré, and Isabelle Tellier. BibTeX URL
  MODÈLES ALGORITHMIQUES DE L'ACQUISTION DE LA SYNTAXE : concepts et méthodes, résultats et problèmes.
  Recherches linguistiques de Vincennes, 36:123–151, 2007. ISBN 978-2-84292-208-5, ISSN 0986-6124.
  

  In this paper, we present our recent results on the acquistion of the syntax of natural languages, from the point of view of the theory of grammatical inference. Given a class of possible grammars, the objective is to identify, from a set of positive examples, a grammar in the class which produces the examples. The Gold model formalises the learning process and gives stringent criteria of its success: when does there exist an algorithm producing a target grammar ? what kind of structure should the examples have (strings of words, strings of tagged words, trees) ? From a theoretical point of view, our results establish the learnability or the unlearnability of various classes of categorial grammars. From a practical perspective, these results enable the extraction of syntactic information from real data. Finally, we discuss the interest of this approach for modelling child language acquisition and for automated induction of grammars from corpora.

International Conferences

• Denis Béchet and Annie Foret. BibTeX PDF DOI URL
  Categorial Dependency Grammars extended with barriers (CDGb) yield an Abstract Family of Languages (AFL).
  In David C. Wyld and Dhinaharan Nagamalai, editors, Proceedings of the 5th International Conference on Natural Language Processing and Computational Linguistics (NLPCL 2024), September 21–22, 2024, Copenhagen, Denmark, pages 53–66, Septembre 2024.
  

  We consider the family of Categorial Dependency Grammars (CDG), as computational grammars for language processing. CDG are a class of categorial grammars defining dependency structures. They can be viewed as a formal system, where types are attached to words, combining the classical categorial grammars' elimination rules with valency pairing rules that are able to define non-projective (discontinuous) dependencies. Whereas the closure problem under iteration is open for the original version of CDG, we define “CDG extended with barriers an extended version of the original CDG that solves this formal issue. We provide a rule system and show that the extended version defines an Abstract Family of Languages (AFL) while preserving advantages of the original CDG in terms of expressivity, parsing and efficiency.

• Annie Foret, Denis Béchet, and Valérie Bellynck. BibTeX PDF URL
  Iterated Dependencies in a Breton treebank and implications for a Categorial Dependency Grammar.
  In Theodorus Fransen, William Lamb, and Delyth Prys, editors, Proceedings of the 4th Celtic Language Technology Workshop iat LREC 2022 (CLTW 4), Marseille, France, pages 40–46. European Language Resources Association, June 2022.
  

  Categorial Dependency Grammars (CDG) are computational grammars for natural language processing, defining dependency structures. They can be viewed as a formal system, where types are attached to words, combining the classical categorial grammars' elimination rules with valency pairing rules able to define discontinuous (non-projective) dependencies. Algorithms have been proposed to infer grammars in this class from treebanks, with respect to Mel'čuk principles. We consider this approach with experiments on Breton. We focus in particular on ``repeatable dependencies'' (iterated) and their patterns. A dependency $d$ is iterated in a dependency structure if some word in this structure governs several other words through dependency d. We illustrate this approach with data in the universal dependencies format and dependency patterns written in Grew (a graph rewriting tool dedicated to applications in Natural Language Processing).

• Denis Béchet and Annie Foret. BibTeX URL
  Categorial Dependency Grammars: Analysis and Learning (Invited Talk).
  In Ljungström, Axel, Loukanova, Roussanka, Lumsdaine, Peter LeFanu, and Muskens, Reinhard, editors, Proceedings of the SymposiumLogic and Algorithms in Computational Linguistics 2021 (LACompLing2021), pages 32–33. Stockholm University, 2021, DiVA Portal for Digital Publications, 2021. Conference webpage: https://staff.math.su.se/rloukanova/LACompLing2021-web/.
  

  We give an overview on the family of Categorial Dependency Grammars (CDG), as computational grammars for language processing, CDGs are a class of categorial grammars defining dependency structures. They can be viewed as a formal system, where types are attached to words, combining the classical categorial grammars’ elimination rules with valency pairing rules defining non- projective (discontinuous) dependencies. We shall discuss both formal aspects of CDG in terms of strength, derivability and complexity and practical issues and algorithms. We will also point to some open problems. We will also review results on CDG learnability and discuss CDG as large scale grammars with respect to Mel’čuk principles and to various hypotheses on training corpora.

• Denis Béchet and Annie Foret. BibTeX Draft
  Simple K-star Categorial Dependency Grammars and their Inference.
  In Sicco Verwer, Menno van Zaanenand, and Rick Smetsers, editors, The 13th International Conference on Grammatical Inference, ICGI 2016, Delft, The Netherlands, October 5–7, 2016. Proceedings, pages 1–12, 2016.
  

  We propose a novel subclass in the family of Categorial Dependency Grammars (CDG), based on a syntactic criterion on categorial types associated to words in the lexicon and study its learnability. This proposal relies on a linguistic principle and relates to a former non-constructive condition on iterated dependencies. We show that the projective CDG in this subclass are incrementally learnable in the limit from dependency structures. In contrast to previous proposals, our criterion is both syntactic and does not impose a (rigidity) bound on the number of categorial types associated to a word.

• Denis Béchet and Annie Foret. BibTeX Draft DOI URL
  Categorial Dependency Grammars with Iterated Sequences.
  In Maxime Amblard, Philippe de Groote, Sylvain Pogodalla, and Christian Retoré, editors, Logical Aspects of Computational Linguistics. Celebrating 20 Years of LACL (1996–2016) 9th International Conference, LACL 2016, Nancy, France, December 5–7, 2016. Proceedings, volume 10054 of Lecture Notes in Computer Science (LNCS), pages 34–51. Springer-Verlag, 2016. ISBN 978-3-662-53825-8.
  

  Some dependency treebanks use special sequences of dependencies where main arguments are mixed with separators. Classical Categorial Dependency Grammars (CDG) do not allow this construction because iterative dependency types only introduce the iterations of the same dependency. An extension of CDG is defined here that introduces a new construction for repeatable sequences of one or several dependency names. The learnability properties of the extended CDG when grammars are infered from a dependency treebank is also studied. It leads to the definition of new classes of grammars that are learnable in the limit from dependency structures.

• Ophélie Lacroix and Denis Béchet. BibTeX Draft URL
  A Three-Step Transition-Based System for Non-Projective Dependency Parsing.
  In COLING 2014, 25th International Conference on Computational Linguistics, Proceedings of the Conference: Technical Papers, August 23-29, 2014, Dublin, Ireland, pages 224–232, August 2014.
  

  This paper presents a non-projective dependency parsing system that is transition-based and operates in three steps. The three steps include one classical method for projective dependency parsing and two inverse methods predicting separately the right and left non-projective dependencies. Splitting the parsing allows to increase the scores on both projective and non-projective dependencies compared to state-of-the-art non-projective dependency parsing. Moreover, each step is performed in linear time.

• Ophélie Lacroix and Denis Béchet. BibTeX Draft
  Validation Issues induced by an Automatic Pre-Annotation Mechanism in the Building of Non-projective Dependency Treebanks.
  In Nicoletta Calzolari (Conference Chair), Khalid Choukri, Thierry Declerck, Hrafn Loftsson, Bente Maegaard, Joseph Mariani, Asuncion Moreno, Jan Odijk, and Stelios Piperidis, editors, Proceedings of the Ninth International Conference on Language Ressources and Evaluation (LREC 2014), Reykjavik, Iceland, May 26–31, 2014, pages 4082–4086. European Language Resources Association (ELRA), May 2014. ISBN 978-2-9517408-8-4.
  

  In order to build large dependency treebanks using the CDG Lab, a grammar-based dependency treebank development tool, an annotator usually has to fill a selection form before parsing. This step is usually necessary because, otherwise, the search space is too big for long sentences and the parser fails to produce at least one solution. With the information given by the annotator on the selection form the parser can produce one or several dependency structures and the annotator can proceed by adding positive or negative annotations on dependencies and launching iteratively the parser until the right dependency structure has been found. However, the selection form is sometimes difficult and long to fill because the annotator must have an idea of the result before parsing. The CDG Lab proposes to replace this form by an automatic pre-annotation mechanism. However, this model introduces some issues during the annotation phase that do not exist when the annotator uses a selection form. The article presents those issues and proposes some modifications of the CDG Lab in order to use effectively the automatic pre-annotation mechanism.

• Ophélie Lacroix, Denis Béchet, and Florian Boudin. BibTeX Draft
  Label Pre-annotation for Building Non-projective Dependency Treebanks for French.
  In Alexander Gelbukh, editor, Computational Linguistics and Intelligent Text Processing, 15th International Conference, CICLing 2014, Kathmandu, Nepal, April 6–12, 2014, Proceedings, pages 1–12, 2014. (poster).
  

  The current interest in accurate dependency parsing make it necessary to build dependency treebanks for French containing both projective and non-projective dependencies. In order to alleviate the work of the annotator, we propose to automatically pre-annotate the sentences with the labels of the dependencies ending on the words. The selection of the dependency labels reduces the ambiguity of the parsing. We show that a maximum entropy Markov model method reaches the label accuracy score of a standard dependency parser (MaltParser). Moreover, this method allows to find more than one label per word, i.e. the more probable ones, in order to improve the recall score. It improves the quality of the parsing step of the annotation process. Therefore, the inclusion of the method in the process of annotation makes the work quicker and more natural to annotators.

• Ramadan Alfared and Denis Béchet. BibTeX Draft URL
  On the Adequacy of Three POS Taggers and a Dependency Parser.
  In Alexander Gelbukh, editor, Computational Linguistics and Intelligent Text Processing, 13th International Conference, CICLing 2012, New Delhi, India, March 11–17, 2012, Proceedings, Part I, volume 7181 of Lecture Notes in Computer Science (LNCS), pages 104–116. Springer-Verlag, 2012. ISBN 978-3-642-28603-2.
  

  A POS-tagger can be used in front of a parser to reduce the number of combinations of possible dependency trees which, in the majority, give spurious analyses. In the paper we compare the results of the addition of three morphological taggers to the parser of the CDG Lab. The experimental results show that these models perform better than the model which do not use a morphological tagger at the cost of loosing some correct analyses. In fact, the adequacy of these solutions is mainly based on the compatibility between the lexical units defined by the taggers and the dependency grammar.

• Denis Béchet, Alexander Dikovsky, and Annie Foret. BibTeX Draft DOI
  Two models of learning iterated dependencies.
  In Philippe de Groote and Mark-Jan Nederhof, editors, Formal Grammar, 15th and 16th International Conferences, FG 2010, Copenhagen, Denmark, August 2010, FG 2011, Lubljana, Slovenia, August 2011, Revised Selected Papers, volume 7395 of Lecture Notes in Computer Science (LNCS), pages 17–32. Springer-Verlag, 2012. ISBN 978-3-642-32023-1.
  

  We study the learnability problem in the family of Categorial Dependency Grammars (CDG), a class of categorial grammars defining unlimited dependency structures. CDG satisfying a reasonable condition on iterated (i.e., repeatable and optional) dependencies are shown to be incrementally learnable in the limit.

• Denis Béchet, Alexandre Dikovsky, and Annie Foret. BibTeX Draft DOI URL
  On Dispersed and Choice Iteration in Incrementally Learnable Dependency Types.
  In Sylvain Pogodalla and Jean-Philippe Prost, editors, Logical Aspects of Computational Linguistics, 6th International Conference, LACL 2011, Montpellier, France, June 29 -- July 1, 2011. Proceedings, volume 6736 of Lecture Notes in Artificial Intelligence (LNAI), pages 80–95. Springer-Verlag, 2011. ISBN 978-3-642-22220-7.
  

  We study learnability of Categorial Dependency Grammars (CDG), a family of categorial grammars expressing all kinds of projective, discontinuous and repeatable dependencies. For these grammars, it is known that they are not learnable from dependency structures. We propose two different ways of modelling the repeatable dependencies through iterated types and the two corresponding families of CDG which cannot distinguish between the dependencies repeatable at least K times and those repeatable \sf any number of times. For both we show that they are incrementally learnable in the limit from dependency structures.

• Denis Béchet, Alexandre Dikovsky, and Annie Foret. BibTeX Draft DOI URL
  Categorial Grammars with Iterated Types form a Strict Hierarchy of k-Valued Languages.
  In Béatrice Bouchou-Markhoff, Pascal Caron, Jean-Marc Champarnaud, and Denis Maurel, editors, Implementation and Application of Automata, 16th International Conference, CIAA 2011, Blois, France, July 13-16, 2011. Proceedings, volume 6807 of Lecture Notes in Computer Science (LNCS), pages 42–52. Springer, 2011. ISBN 978-3-642-22255-9.
  

  The notion of k-valued categorial grammars where a word is associated to at most k types is often used in the field of lexicalized grammars as a fruitful constraint for obtaining several properties like the existence of learning algorithms. This principle is relevant only when the classes of k-valued grammars correspond to a real hierarchy of languages. Such a property had been shown earlier for classical categorial grammars. This paper establishes the relevance of this notion when categorial grammars are enriched with iterated types.

• Ramadan Alfared, Denis Béchet, and Alexander Dikovsky. BibTeX Draft URL
  CDG Lab: a Toolbox for Dependency Grammars and Dependency Treebanks Development.
  In Kim Gerdes, Eva Hajičová, and Leo Wanner, editors, Proceedings of the 1st International Conference on Dependency Linguistics (Depling 2011), Barcelona, Spain, September 5–7 2011, 2011. Short paper, ISBN 978-84-615-1834-0.
  

  We present ``CDG LAB'', a toolkit for development of dependency grammars and treebanks. It uses the Categorial Dependency Grammars (\textttCDG) as a formal model of dependency grammars. CDG are very expressive. They generate unlimited dependency structures, are analyzed in polynomial time and are conservatively extendable by regular type expressions without loss of parsing efficiency. Due to these features, they are well adapted to definition of large scale grammars. CDG LAB supports the analysis of correctness of treebanks developed in parallel with evolving grammars.

• Denis Béchet, Alexander Dikovsky, and Annie Foret. BibTeX Draft URL
  Two models of learning iterated dependencies.
  In Markus Egg, Philippe de Groote, Laura Kallmeyer, and Mark-Jan Nederhof, editors, Proceedings of the 15th International Conference on Formal Grammar (FG10), Copenhagen, Denmark, August 7-8, 2010, pages 1–16, 2010.
  

  We study the learnability problem in the family of Categorial Dependency Grammars (CDG), a class of categorial grammars defining unlimited dependency structures. CDG satisfying a reasonable condition on iterated (i.e., repeatable and optional) dependencies are shown to be incrementally learnable in the limit.

• Denis Béchet, Alexander Dikovsky, Annie Foret, and Emmanuelle Garel. BibTeX Draft DOI URL
  Optional and Iterated Types for Pregroup Grammars.
  In Carlos Martìn-Vide, Friedrich Otto, and Henning Fernau, editors, Language and Automata Theory and Applications, Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008, Revised Papers, volume 5196 of Lecture Notes in Computer Science (LNCS), pages 88–100. Springer, 2008. ISBN 978-3-540-88281-7.
  

  Pregroup grammars are a context-free grammar formalism which may be used to describe the syntax of natural languages. However, this formalism is not able to naturally define types corresponding to optional and iterated arguments such as optional complements of verbs or verbs' adverbial modifiers. This paper introduces two constructions that make up for this deficiency.

• Denis Béchet and Annie Foret. BibTeX Draft DOI URL
  Fully Lexicalized Pregroup Grammars.
  In Daniel Leivant and Ruy de Queiroz, editors, Logic, Language, Information and Computation, 14th International Workshop, WoLLIC 2007, Rio de Janeiro, Brazil, July 2-5, 2007. Proceedings, volume 4576 of Lecture Notes in Computer Science (LNCS), pages 12–25. Springer, 2007. ISBN 978-3-540-73443-7.
  

  Pregroup grammars are a context-free grammar formalism introduced as a simplification of Lambek calculus. This formalism is interesting for several reasons: the syntactical properties of words are specified by a set of types like the other type-based grammar formalisms ; as a logical model, compositionality is easy ; a polytime parsing algorithm exists. However, this formalism is not completely lexicalized because each pregroup grammar is based on the free pregroup built from a set of primitive types together with a partial order, and this order is not lexical information. In fact, only the pregroup grammars that are based on primitive types with an order that is equality can be seen as fully lexicalized. We show here how we can transform, using a morphism on types, a particular pregroup grammar into another pregroup grammar that uses the equality as the order on primitive types. This transformation is at most quadratic in size (linear for a fixed set of primitive types), it preserves the parse structures of sentences and the number of types assigned to a word.

• Denis Béchet, Alexander Dikovsky, and Annie Foret. BibTeX Draft DOI URL
  Dependency Structure Grammar.
  In Philippe Blache, Edward Stabler, Joan Busquets, and Richard Moot, editors, Logical Aspects of Computational Linguistics, 5th International Conference, LACL 2005, Bordeaux, France, April 28–30, 2005. Proceedings, volume 3492 of Lecture Notes in Artificial Intelligence (LNAI), pages 18–34. Springer-Verlag, 2005. ISBN 978-3-540-25783-7.
  

  In this paper, we define Dependency Structure Grammars (DSG), which are rewriting rule grammars generating sentences together with their dependency structures, are more expressive than CF-grammars and non-equivalent to mildly context-sensitive grammars. We show that DSG are weakly equivalent to Categorial Dependency Grammars (CDG) recently introduced. In particular, these dependency grammars naturally express long distance dependencies and enjoy good mathematical properties.

• Denis Béchet and Annie Foret. BibTeX Draft DOI URL
  k-Valued Non-associative Lambek Grammars (Without Product) Form a Strict Hierarchy of Languages.
  In Philippe Blache, Edward Stabler, Joan Busquets, and Richard Moot, editors, Logical Aspects of Computational Linguistics, 5th International Conference, LACL 2005, Bordeaux, France, April 28–30, 2005. Proceedings, volume 3492 of Lecture Notes in Artificial Intelligence (LNAI), pages 1–16. Springer-Verlag, 2005. ISBN 978-3-540-25783-7.
  

  The notion of k-valued categorial grammars where a word is associated to at most k types is often used in the field of lexicalized grammars as a fruitful constraint for obtaining several properties like the existence of learning algorithms. This principle is relevant only when the classes of k-valued grammars correspond to a real hierarchy of languages. This paper establishes the relevance of this notion for two related grammatical systems. In the first part, the classes of k-valued non-associative Lambek grammars without product is proved to define a strict hierarchy of languages. The second part introduces the notion of generalized functor argument for non-associative Lambek calculus without product but allowing empty antecedent and establishes also that the classes of k-valued grammars without product form a strict hierarchy of languages.

• Denis Béchet and Annie Foret. BibTeX Draft URL
  On Rigid NL Lambek Grammars Inference from Generalized Functor-Argument Data.
  In James Rogers, editor, Proceedings of the 10th Conference on Formal Grammar and the 9th Meeting on Mathematics of Language (FG-MOL 2005), Edinburgh, Scotland, 5–7 August 2005, pages 71–80. CSLI Publications, 2005. ISSN 1935-1569.
  

  This paper is concerned with the inference of categorial grammars, a context-free grammar formalism in the field of computational linguistics. A recent result has shown that whereas they are not learnable from strings in the model of Gold, rigid and k-valued non-associative Lambek grammars are still learnable from generalized functor-argument structured sentences. We focus here on the algorithmic part of this result and provide an algorithm that can be seen as an extension of Buszkowski, Penn and Kanazawa's contributions for classical categorial grammars.

• Denis Béchet and Annie Foret. BibTeX Draft
  On Intermediate Structures for Non-Associative Lambek Grammars and Learnability.
  In M. Moortgat and V. Prince, editors, Proceedings of the International Conference on Categorial Grammars (CG2004), Montpellier, France, June 2004, pages 180–194, June 2004.
  

  This paper is concerned with learning categorial grammars in the model of Gold. We show that rigid and k-valued non-associative Lambek (NL) grammars are not learnable from well-bracketed sentences. In contrast to k-valued classical categorial grammars, k-valued Lambek grammars are not learnable from strings. This result was shown for several variants including the non-associative variant NL. Whereas k-valued Lambek NL grammars have been shown learnable from functor-argument structures, we show that non-learnability still holds for the languages of well-bracketed strings ; this result is obtained for two variants NL and NL∅ by exhibiting a limit point in the considered class. Such a result aims at clarifying the possible directions for future learning algorithms: it expresses the difficulty of learning categorial grammars from strings or intermediate structures and helps to draw the frontier between learnability and non-learnability.

• Denis Béchet, Alexander Dikovsky, Annie Foret, and Erwan Moreau. BibTeX Draft URL
  On Learning Discontinuous Dependencies from Positive Data.
  In Paola Monachesi, editor, Proceedings of the 9th International Conference on Formal Grammar (FGNancy), Nancy, France, 7-8 August 2004, pages 1–16. CSLI Publications, 2004. ISSN 1935-1569.
  

  This paper is concerned with learning in the model of Gold the \it Categorial Dependency Grammars (CDG), which express discontinuous (non-projective) dependencies. We show that rigid and k-valued CDG (without optional and iterative types) are learnable from strings. In fact, we prove that the languages of \it dependency nets coding rigid CDGs have finite elasticity, and we show a learning algorithm. As a standard corollary, this result leads to the learnability of rigid or k-valued CDGs (without optional and iterative types) from strings.

• Denis Béchet, Annie Foret, and Isabelle Tellier. BibTeX Draft DOI
  Learnability of Pregroup Grammars.
  In Georgios Paliouras and Yasubumi Sakakibara, editors, Grammatical Inference: Algorithms and Applications, 7th International Colloquium, ICGI 2004, Athens, Greece, October 11–13, 2004. Proceedings, volume 3264 of Lecture Note in Artificial Intelligence (LNAI), pages 65–76. Springer-Verlag, 2004. ISBN 978-3-540-23410-4.
  

  This paper investigates the learnability of Pregroup Grammars, a context-free grammar formalism recently defined in the field of computational linguistics. In a first theoretical approach, we provide learnability and non-learnability results in the sense of Gold for subclasses of Pregroup Grammars. In a second more practical approach, we propose an acquisition algorithm from a special kind of input called Feature-tagged Examples, that is based on sets of constraints.

• Denis Béchet. BibTeX Draft
  INCREMENTAL PARSING OF LAMBEK CALCULUS USING PROOF-NET INTERFACES.
  In ACL/SIGPARSE, editor, Proceedings of the Eigth International Workshop on Parsing Technologies, Nancy, France, April 2003, pages 31–42. INRIA, April 2003. ISBN 2-7261-1243-9.
  
  
• Denis Béchet and Annie Foret. BibTeX Draft DOI URL
  k-valued Non-Associative Lambek Categorial Grammars are not Learnable from Strings.
  In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL 2003), Sapporo, Japan, July 2003, pages 351–358. ACL, July 2003. ISBN 1-932432-09-4.
  
  
• Denis Béchet and Annie Foret. BibTeX Draft DOI
  k-Valued Non-Associative Lambek Grammars are Learnable from Function-Argument Structures.
  In Ruy de Queiroz, Elaine Pimentel, and Lucilia Figueiredo, editors, Electronic Notes in Theoretical Computer Science, pages 1–13. Elsevier, July 2003. ISSN 1571-0661.
  
  
• Denis Béchet. BibTeX Draft URL
  k-Valued Link Grammars are Learnable from Strings.
  In Gerald Penn, editor, Proceedings of the 8th conference on Formal Grammar (FG-2003 or FGVienna), Vienna, Austria, 16–17 August 2003, pages 3–12. CSLI Publications, August 2003. ISSN 1935-1569.
  

  Abstract The article is concerned with learning link grammars in the model of Gold. We show that rigid and k-valued link grammars are learnable from strings. In fact, we prove that the languages of link structured lists of words associated to rigid link grammars have finite elasticity and we show a learning algorithm. As a standard corollary, this result leads to the learnability of rigid or k-valued link grammars learned from strings.

• Denis Béchet. BibTeX Draft DOI
  Universal Interaction Systems with Only Two Agents.
  In Aart Middeldorp, editor, Rewriting Techniques and Applications, 12th International Conference, RTA 2001, Utrecht, The Netherlands, May 22–24, 2001. Proceedings, volume 2051 of Lecture Notes in Computer Science (LNCS), pages 3–14. Springer-Verlag, 2001. ISBN 978-3-540-42117-7.
  
  
• Denis Béchet and Philippe de Groote. BibTeX Draft DOI
  Constructing different phonological bracketings from a proof net.
  In Christian Retoré, editor, Logical Aspects of Computational Linguistics, First International Conference, LACL '96, Nancy, France, September 23-25, 1996. Selected Papers, volume 1328 of Lecture Notes in Artificial Intelligence (LNAI), pages 118–133. Springer-Verlag, 1997. ISBN 978-3-540-63700-4.
  
  
• Denis Bechet, Philippe de Groote, and Christian Retoré. BibTeX Draft DOI
  A complete axiomatisation of the inclusion of series-parallel partial orders.
  In Hubert Comon, editor, Rewriting Techniques and Applications, 8th International Conference, RTA-97, Sitges, Spain, June 2–5, 1997, Proceedings, volume 1232 of Lecture Notes in Computer Science (LNCS), pages 230–240. Springer-Verlag, 1997. ISBN 978-3-540-62950-4.
  
  
• Denis Béchet. BibTeX Draft DOI
  Removing Value Encoding using Alternative Values in Partial Evaluation of Strongly-Typed Languages.
  In Hanne Riis Nielson, editor, Programming Languages and Systems --- ESOP '96, 6th European Symposium on Programming Linköping, Sweden, April 22–24, 1996. Proceedings, volume 1058 of Lecture Notes in Computer Science (LNCS), pages 77–91. Springer-Verlag, 1996. ISBN 978-3-540-61055-7.
  
  
• Denis Béchet. BibTeX Draft
  Partial Evaluation of Interaction Nets.
  In Michel Billaud, Pierre Castéran, Marc-Michel Corsini, Kaninda Musumbu, and Antoine Rauzy, editors, Proceedings of WSA'92 Workshop on Static Analysis, Bordeaux, France, September 1992. Bigre vols 81–82, volume 81–82 of Bigre, pages 331–338. Atelier Irisa, IRISA, Campus de Beaulieu, Rennes, France, 1992.
  
  

French Conferences

• Denis Béchet and Ophélie Lacroix. BibTeX URL
  CDGFr, un corpus en dépendances non-projectives pour le français.
  In Actes de la 22e conférence sur le Traitement Automatique des Langues Naturelles, June 2015, Caen, France, pages 522–528. Association pour le Traitement Automatique des Langues, 2015. Short paper in French.
  

  The non-projective cases, as a part of the dependency parsing of French, are often disregarded, mainly because the tree-banks on which parsers are trained contain little or no non-projective dependencies. In this paper, we present a new freely available dependency treebank for French that includes a substantial number of non-projective dependencies. This corpus can be used to study and process non-projectivity more effectively within the context of French dependency parsing. Dans le cadre de l'analyse en dépendances du français, le phénomène de la non-projectivité est peu pris en compte, en majeure partie car les donneés sur lesquelles sont entraînés les analyseurs représentent peu ou pas ces cas particuliers. Nous présentons, dans cet article, un nouveau corpus en dépendances pour le français, librement disponible, contenant un nombre substantiel de dépendances non-projectives. Ce corpus permettra d'étudier et de mieux prendre en compte les cas de non-projectivité dans l'analyse du français.

• Ramadan Alfared, Denis Béchet, and Alexander Dikovsky. BibTeX Draft URL
  Calcul des cadres de sous catégorisation des noms déverbaux français (le cas du génitif).
  In Georges Antoniadis, Hervé Blanchon, and Gilles Sérasset, editors, Actes de la conférence conjointe JEP-TALN-RECITAL 2012, 4–8 Juin 2012, Grenoble, France, pages 71–84, 2012. In French.
  

  L'analyse syntaxique fine en dépendances nécessite la connaissance des cadres de sous-catégorisation des unités lexicales. Le cas des verbes étant bien étudié, nous nous intéressons dans cet article au cas des noms communs dérivés de verbes. Notre intérêt principal est de calculer le cadre de sous-catégorisation des noms déverbaux à partir de celui du verbe d'origine pour le français. Or, pour ce faire il faut disposer d'une liste représentative de noms déverbaux français. Pour calculer cette liste nous utilisons un algorithme simplifié de repérage des noms déverbaux, l'appliquons à un corpus et comparons la liste obtenue avec la liste Verbaction des déverbaux exprimant l'action ou l'activité du verbe. Pour les noms déverbaux ainsi obtenus et attestés ensuite par une expertise linguistique, nous analysons la provenance des groupes prépositionnels subordonnés des déverbaux dans des contextes différents en tenant compte du verbe d'origine. L'analyse est effectuée sur le corpus Paris 7 et est limitée au cas le plus fréquent du génitif, c'est-à-dire des groupes prépositionnels introduits par de, des, etc.

• Denis Béchet, Alexandre Dikovsky, and Annie Foret. BibTeX Draft
  Sur les itérations dispersées et les choix itérés pour l'apprentissage incrémental des types dans les grammaires de dépendances.
  In 7e Plateforme AFIA, Association Française pour l'Intelligence Artificielle, Chambéry, 17–20 mai 2011, pages 87–102. Presses Universitaires des Antilles et de la Guyane, Éditions Publibook, 2011. ISBN 978-27-483-6423-1.
  
  
• Denis Béchet and Annie Foret. BibTeX Draft
  Apprentissage des grammaires de Lambek rigides et d'arité bornée pour le traitement automatique des langues.
  In Actes de la Conférence d'Apprentissage 2003 (CAp'2003), pages 155–167. Presses Universitaires de Grenoble, June 2003. ISBN 2-7061-1144-5.
  
  
• Denis Béchet and Annie Foret. BibTeX Draft
  Remarques et perspectives sur les langages de prégroupe d'ordre 1/2.
  In Actes, Dixième conférence de Traitement Automatique des Langues Naturelles (TALN 2003), pages 309–314. ATALA, June 2003. (Poster).
  
  

Conferences without Proceedings

• Denis Béchet. BibTeX Slides URL
  Non-projective Axioms for Pregroup Grammars as Cut Eliminations.
  In Proceedings of the Workshop Joachim Lambek, Mathematics, Logic and Language, Chieti, Italy, 8–9 July, 2011, 2011.
  

  Grammars based on free pregroups are context free. Thus, for several complex syntactical constructions that are not projective, some types must include a way to cross part of the environment. To solve this problem, cut annotations on the types assigned to special words like clitics or adverbs can be introduced. These annotations that can be seen as a limited form of semantical interpretation replace two normal axiom links by a long distance axiom link. During this reduction, such new links can cross other axioms: they introduce non-projective axioms that are not possible with pregroup grammars.

• Denis Béchet and Annie Foret. BibTeX Draft URL
  PPQ : a pregroup parser using majority composition.
  In Timothy Fowler and Gerald Penn, editors, Proceedings of the ESSLLI 2009 Workshop on Parsing with Categorial Grammars, 20-24 July 2009, Bordeaux, France, pages 33–37, 2009.
  

  Pregroup grammars are a mathematical formalism in the spirit of categorial grammars. They are close to logical formalism like Lambek calculus but have a polynomial parsing algorithm. The paper presents a parser based on pregroup grammar that uses a tabular approach based on majority partial composition.

• Denis Béchet and Annie Foret. BibTeX Draft URL
  Une boîte a outils pour développer et utiliser les grammaires de prégroupe.
  In Eric de la Clergerie and Patrick Paroubek, editors, Actes de la journée ATALA ``Quels analyseurs syntaxiques pour le français ?'', Paris, France, octobre 2009, 2009. (in French).
  

  Les grammaires de prégroupes sont un formalisme dans l'esprit des grammaires catégorielles et du calcul de Lambek mais contrairement à ces dernières, elles sont analysables en temps polynomial. Nous présentons dans cet article une boîte à outils contenant un analyseur et un ensemble de programmes permettant de développer et d'utiliser des grammaires en particulier pour le français.

• Denis Béchet and Sylvain Lippi. BibTeX Draft DOI URL
  Hard combinators.
  In Ian Mackie and Detlef Plump, editors, Proceedings of the Fourth International Workshop on Computing with Terms and Graphs (TERMGRAPH 2007), Braga, Portugal, 31 March 2007, volume 203, Issue 1 of Electronic Notes in Theoretical Computer Science (ENTCS), pages 31–48. Elsevier, 2008. ISSN 1571-0661.
  

  We present a simple system of four symbols and seven rules that can be used to translate a subclass of graph relabeling systems called hard interaction nets.

• Denis Béchet and Sylvain Lippi. BibTeX Draft DOI URL
  Universal Boolean Systems.
  In Ian Mackie and Detlef Plump, editors, Proceedings of the Fourth International Workshop on Computing with terms and graphs, TERMGRAPH 2007, Braga, Portugal, 31 March 2007, volume 203, Issue 1 of Electronic Notes in Theoretical Computer Science (ENTCS), pages 19–30. Elsevier, 2008. ISSN 1571-0661.
  

  Boolean interaction systems and hard interaction systems define nets of interacting cells. They are based on the same local interaction principle between two cells as interaction nets but do not allow that the structure of nets may evolve. With boolean nets, it is not possible to create or destroy cells or links between existing cells. They are very similar to hardware circuits but based on an implicit rendez-vous information exchange mechanism. If we want to implement such systems using hardware circuits, it is important to define a set of universal combinators that reduces this task to the implementation of a fixed number of known agents. Here, we show how we can simulate every hard interaction system by a universal boolean interaction system composed of three combinators: a duplicator, a NAND gate and a three-state input/output channel.

• Annie Foret and Denis Béchet. BibTeX URL
  Analyses et Acquisition de Grammaires Catégorielles et de Prégroupes.
  In Daniela Bargelli, editor, Actes de l'atelier ``Grammaires de prégroupes et grammaires de types'' du 76ème Congrès de l'Acfas, Quebec, Canada, 5 mai 2008, 2008.
  
  
• Denis Béchet. BibTeX Slides URL
  A Parser for Pregroup Grammars Based on Partial Composition.
  In Daniela Bargelli and Annie Foret, editors, Proceedings of the Workshop on Lambek's formalisms, Toulouse, France, 9 June, 2007, 2007.
  
  
• Denis Béchet. BibTeX Slides URL
  Parsing Lambeck calculus using partial composition.
  In Proceedings of the Workshop on Logic and Linguistics, Marseille, France, February 2006, 2006.
  

  A proof of Lambek calculus or cyclic linear logic can be seen as a planar proof-net. In this context, we show that each proof-net can be transformed into a binary tree using a partial composition rule in such a way that, at each step, the complexity of the result of each partial composition does not increase. This result gives a direct parsing algorithm for Lambek grammars which is polytime wrt the length of the string (for a fixed grammar). Moreover, this kind of partial composition leads to a new approch for decomposing a sentences in subcomponents which is more associative than a traditional parse tree.

• Eric Poupard, Denis Béchet, and Annie Foret. BibTeX Draft
  Acquisition d'une grammaire catégorielle depuis un corpus d'arbre en français.
  In Actes de la Conférence d'Apprentissage 2006 (CAp'2006), 2006. (Poster --- Short version in French of TALN-2006-PBF-RR).
  
  
• Denis Béchet, Annie Foret, and Isabelle Tellier. BibTeX Slides
  Parsing pregroup grammars using partial composition.
  In Proceedings of the Workshop on Pregroups and Linear Logic 2005, Chieti, Italy, May 2005, 2005.
  
  
• Denis Béchet. BibTeX Draft
  Interface in linear logic: a finite system of generators (abstract).
  Journal of the Int. Group in Pure and Applied Logics, 4(3), 1996. Report of the Third Workshop on Logic, Language, Information and Computation, Salvador, Brazil, May 1996.
  
  
• Denis Béchet.
  Proof Transfornations in Linear Logic.
  Unpublished.
  
  

Other Presentations

• Denis Béchet and Le Nir, Yannick.
  Présentation de l'environnement pour les programmes d'acquistion de grammaires lexicalisées.
  
  
  
• Denis Béchet.
  Analyse syntaxique en largeur d'abord à l'aide des modules de la logique lineaire.
  
  
  
• Denis Béchet.
  Polynomial Description of the Interface of MLL Modules.
  Unpublished.
  
  

Ph.D. and Habilitations

• PhD : Denis Béchet. BibTeX PDF
  Les valeurs alternatives et la notion d'événement dans l'évaluation partielle.
  
  
  

Reports

• Eric Poupard, Denis Béchet, and Annie Foret.
  Categorial Grammar Acquisition from a French Treebank.
  (Long version in English of TALN-2006-PBF-CAP06).
  

  This paper shows how to construct a categorial grammar from a French Treebank. We first give an algorithm which translates the French Tree-bank developped at Paris 7 into functor-argument structures close to categorial grammar derivations. We then propose an adaptation of the RG-learning algorithm operating on functor-argument data. The two-phased process has been applied to a fragment of the corpus and we also report on this experiment which is a work in progess.

• Denis Béchet.
  Non-Associative Lambek Calculus as Ordered Categorial Grammars.
  Unpublished.
  
  
• Denis Béchet.
  Dag Edit: a dag editor.
  Documentation of Dag Edit, version 1.0.
  
  
• Denis Béchet.
  Polynomial Representation of Linear Logic Module Interface.
  
  
  
• Denis Béchet.
  Module Net: a module editor and prover.
  Documentation of Module Net, version 1.0.
  
  
• Denis Béchet. BibTeX Draft
  Second order connectives and proof transformations in linear logic.
  Master's Thesis 2001-06, June 2001.
  
  
• Yoann Arsicault and Denis Béchet.
  Un visualisateur de structures XML représentant des Dags.
  Program written by Denis Bechet but based on an unfinished program written by Yoann Arsicault during its master thesis.
  
  

??????

• Denis Béchet and Annie Foret. BibTeX DOI URL
  Categorial Dependency Grammars: Analysis and Learning.
  In Loukanova, Roussanka, Lumsdaine, Peter LeFanu, and Muskens, Reinhard, editors, Logic and Algorithms in Computational Linguistics 2021 (LACompLing2021), volume 1081 of Studies in Computational Intelligence, pages 31–56. Springer, Cham, 2023. Edited results of LACompLing2021, ISBN 978-3-031-21779-1.
  

  We give an overview on the family of Categorial Dependency Grammars (CDG), as computational grammars for language processing. CDG are a class of categorial grammars defining dependency structures. They can be viewed as a formal system, where types are attached to words, combining the classical categorial grammars' elimination rules with valency pairing rules that are able to define non-projective (discontinuous) dependencies. We discuss both formal aspects of CDG in terms of strength, derivability and complexity and practical issues and algorithms. We also point to some open problems, review results on CDG learnability and discuss CDG as large scale grammars with respect to Mel'čuk principles and to various hypotheses on training corpora.

• Denis Béchet and Annie Foret. BibTeX DOI URL
  On Categorial Grammatical Inference and Logical Information Systems.
  In Logic and Algorithms in Computational Linguistics 2018, Series: Advances in Intelligent Systems and Computing, Volume 860, pages 125-153. Springer International Publishing, October 2019.