When Categorial Grammars meet Regular Grammatical Inference

Abstract : 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.
Type de document :
Communication dans un congrès
Philippe Blache, Edward P. Stabler, Joan Busquets and Richard Moot. 5th International Conference on Logical Aspects of Computational Linguistics, 2005, Bordeaux, France. Springer, 3492, pp.317-332, 2005, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00536698
Contributeur : Isabelle Tellier <>
Soumis le : mardi 16 novembre 2010 - 17:32:25
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

  • HAL Id : inria-00536698, version 1

Collections

Citation

Isabelle Tellier. When Categorial Grammars meet Regular Grammatical Inference. Philippe Blache, Edward P. Stabler, Joan Busquets and Richard Moot. 5th International Conference on Logical Aspects of Computational Linguistics, 2005, Bordeaux, France. Springer, 3492, pp.317-332, 2005, Lecture Notes in Computer Science. 〈inria-00536698〉

Partager

Métriques

Consultations de la notice

156