Paper: k-Valued Non-Associative Lambek Categorial Grammars Are Not Learnable From Strings

ACL ID P03-1045
Title k-Valued Non-Associative Lambek Categorial Grammars Are Not Learnable From Strings
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2003
Authors
  • Denis Bechet (INRIA, Le Chesnay France; IRISA, Rennes France)
  • Annie Foret (University of Rennes 1, Rennes France; IRISA, Rennes France)

This paper is concerned with learning cat- egorial grammars in Gold’s model. In contrast to k-valued classical categorial grammars, k-valued Lambek grammars are not learnable from strings. This re- sult was shown for several variants but the question was left open for the weak- est one, the non-associative variant NL. We show that the class of rigid and k- valued NL grammars is unlearnable from strings, for each k; this result is obtained by a specific construction of a limit point in the considered class, that does not use product operator. Another interest of our construction is that it provides limit points for the whole hier- archy of Lambek grammars, including the recent pregroup grammars. Such a result aims at clarifying the pos- sible directions for future learning algo- rithms: i...