When Categorial Grammars meet Regular Grammatical Inference - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

When Categorial Grammars meet Regular Grammatical Inference

Résumé

In this paper, we first study the connections between subclasses of AB-categorial grammars and finite state automata. Using this, we explain how learnability results for categorial grammars in Gold's model from structured positive examples translate into regular grammatical inference results from strings. A closer analysis of the generalization operator used in categorial grammar inference shows that it is strictly more powerful than the one used in usual regular grammatical inference, as it can lead outside the class of regular languages. Yet, we show that the result can still be represented by a new kind of finite-state generative model called a recursive automaton. We prove that every unidirectional categorial grammar, and thus every context-free language, can be represented by such a recursive automaton. We finally identify a new subclass of unidirectional categorial grammars for which learning from strings is not more expensive than learning from structures. A drastic simplification of Kanazawa's learning algorithm from strings for this class follows.
Fichier non déposé

Dates et versions

inria-00536698 , version 1 (16-11-2010)

Identifiants

  • HAL Id : inria-00536698 , version 1

Citer

Isabelle Tellier. When Categorial Grammars meet Regular Grammatical Inference. 5th International Conference on Logical Aspects of Computational Linguistics, 2005, Bordeaux, France. pp.317-332. ⟨inria-00536698⟩
67 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More