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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angluin, D.: Inference of Reversible Languages. Journal of the ACM 3, 741–765 (1982)
Hillel, Y.B., Gaifman, C., Shamir, E.: On Categorial and Phrase Structure Grammars. Bulletin of the Research Council of Israel 9F (1960)
Besombes, J., Marion, J.-Y.: newblock Learning Reversible Categorial Grammars from Structures newblock proceedings of Categorial Grammars 148–163 (2004)
Buszkowki, W., Penn, G.: Categorial grammars determined from linguistic data by unification. Studia Logica, 431–454 (1990)
Costa Florêncio, C.: Consistent identification in the limit of any of the classes k-valued is NP-hard. In: de Groote, P., Morrill, G., Retoré, C. (eds.) LACL 2001. LNCS (LNAI), vol. 2099, pp. 125–134. Springer, Heidelberg (2001)
Costa-Florencio, C.: Consistent identification in the limit of rigid grammars from strings is NP-hard. In: Adriaans, P.W., Fernau, H., van Zaanen, M. (eds.) ICGI 2002. LNCS (LNAI), vol. 2484, pp. 49–62. Springer, Heidelberg (2002)
Denis, F., Lemay, A., Terlutte, A.: Some language classes identifiable in the limit from positive data. In: proceedings of the ICGI: Algorithms and Applications. LNCS (LNAI), vol. 2484, pp. 63–76 (2002)
Dupont, P., Miclet, L., Vidal, E.: What is the search space of the regular inference. proceedings of ICGI. LNCS, vol. 862, pp. 25–37 (1994)
Gold, E.M.: Language identification in the limit. Information and Control 10, 447–474 (1967)
Huet, G., Retore, C.: Survey of a few fundamental representation structures for computational linguistics. In: ESSLI 2002 lecture (2002)
Joshi, A., Schabes, Y.: Tree-Adjoining Grammars. In: Handbook of Formal Languages, vol. 3, pp. 69–120. Springer, Heidelberg (1997)
Kanazawa, M.: Learnable Classes of Categorial Grammars. CSLI Publications, Stanford (1998)
Oncina, J., Garcia, P.: Identifying regular languages in polynomial time. In: Advances in Structural and Syntactic Pattern Recognition, vol. 5, pp. 99–108. World Scientific, Singapore (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tellier, I. (2005). When Categorial Grammars Meet Regular Grammatical Inference. In: Blache, P., Stabler, E., Busquets, J., Moot, R. (eds) Logical Aspects of Computational Linguistics. LACL 2005. Lecture Notes in Computer Science(), vol 3492. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11422532_20
Download citation
DOI: https://doi.org/10.1007/11422532_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25783-7
Online ISBN: 978-3-540-31953-5
eBook Packages: Computer ScienceComputer Science (R0)