Abstract
We consider the problem of learning deterministic even linear languages from positive examples. By a “deterministic” even linear language we mean a language generated by an LR(k) even linear grammar. We introduce a natural subclass of LR(k) even linear languages, called LR(k) in the strong sense, and show that this subclass is learnable in the limit from positive examples. Furthermore, we propose a learning algorithm that identifies this subclass in the limit with almost linear time in updating conjectures. As a corollary, in terms of even linear grammars, we have a learning algorithm for k-reversible languages that is more efficient than the one proposed by Angluin[Ang82].
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Angluin. Inference of reversible languages. Journal of the Association for Computing Machinery, Vol. 29, No. 3, pp. 741–765, 1982.
V. Amar and G. Putzolu. On a family of linear grammars. Information and Control, Vol. 7, No. 3, pp. 283–291, 1964.
Z. Galil and G. F. Italiano. Data structures and algorithms for disjoint set union problems. ACM Computing Surveys, Vol. 23, No. 3, pp. 319–344, 1991.
E. M. Gold. Language identification in the limit. Information and Control, Vol. 10, No. 5, pp. 447–474, 1967.
M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley 1978.
B. Lewin. Genes V. Oxford University Press, 1994.
E. Mäkinen. A note on the grammatical inference problem for even linear languages. Report A-1994-9, University of Tampere, 1994. To appear in Fundamenta Informaticae.
Y. Takada. Grammatical inference for even linear languages based on control sets. Information Processing Letters, Vol. 28, No. 4, pp. 193–199, 1988.
Y. Takada. A hierarchy of languages families learnable by regular language learning. Research Report ISIS-RR-94-15E, ISIS, Fujitsu Laboratories Ltd., 1994. To appear in Information and Computation.
R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the Association for Computing Machinery, Vol. 22, No. 2, pp. 215–225, 1975.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koshiba, T., Mäkinen, E., Takada, Y. (1995). Learning strongly deterministic even linear languages from positive examples. In: Jantke, K.P., Shinohara, T., Zeugmann, T. (eds) Algorithmic Learning Theory. ALT 1995. Lecture Notes in Computer Science, vol 997. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60454-5_27
Download citation
DOI: https://doi.org/10.1007/3-540-60454-5_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60454-9
Online ISBN: 978-3-540-47470-8
eBook Packages: Springer Book Archive