Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11422532_20 | LACL |
Keywords | Field | DocType |
regular grammatical inference result,categorial grammar inference,usual regular grammatical inference,finite-state generative model,ab-categorial grammar,finite state automaton,categorial grammar,unidirectional categorial grammar,regular language,recursive automaton,grammatical inference,context free language,finite state automata | Context-sensitive grammar,Tree-adjoining grammar,Context-free language,Context-free grammar,Grammar induction,Computer science,Indexed grammar,Algorithm,Combinatory categorial grammar,Categorial grammar,Natural language processing,Artificial intelligence | Conference |
Volume | ISSN | ISBN |
3492 | 0302-9743 | 3-540-25783-7 |
Citations | PageRank | References |
2 | 0.47 | 8 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| isabelle tellier | 1 | 84 | 20.31 |