Learnability of Pregroup Grammars

Denis Béchet (1) , Annie Foret (2) , Isabelle Tellier (3)

1 LINA - Laboratoire d'Informatique de Nantes Atlantique
2 LIS - Logical Information Systems
3 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction

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.

Keywords: Learning from positive examples; Pregroup grammars; Computational linguistics; parsing; Categorial Grammars; constraints

Domains: Machine Learning [cs.LG]; Document and Text Processing

Denis Béchet, Annie Foret, Isabelle Tellier. Learnability of Pregroup Grammars. Studia Logica, 2007, 87, pp.225-252. ⟨10.1007/s11225-007-9085-2⟩. ⟨inria-00191112⟩