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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00536698
Contributor : Isabelle Tellier <>
Submitted on : Tuesday, November 16, 2010 - 5:32:25 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM

Identifiers

  • HAL Id : inria-00536698, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

205