Abstract
We generalize a former algorithm for regular language identification from stochastic samples to the case of tree languages or, equivalently, string languages where structural information is available. We also describe a method to compute efficiently the relative entropy between the target grammar and the inferred one, useful for the evaluation of the inference.
Work partially supported by the Spanish CICYT under grant TIC97-0941.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Aho, A.V. & Ullman, J.D. (1972): “The theory of parsing, translation and compiling. Volume I: Parsing”. Prentice-Hall, Englewood Cliffs, NJ.
Angluin, D. (1982): Inference of reversible languages. Journal of the Association for Computing Machines 29, 741–765.
Calera, J. & Carrasco, R.C: (1998): Computing the relative entropy between regular tree languages. Submitted for publication.
Carrasco, R.C. (1997): “Inferencia de lenguajes rationales estocásticos”. Ph.D. dissertation. Universidad de Alicante.
Carrasco, R.C. (1998): Accurate computation of the relative entropy between stochastic regular grammars. Theoretical Informatics and Applications. To appear.
Carrasco, R.C. & Oncina, J. (1994): Learning stochastic regular grammars by means of a state merging method in “Grammatical Inference and Applications” (R.C. Carrasco and J. Oncina, Eds.). Lecture Notes in Artificial Intelligence 862, Springer-Verlag, Berlin.
Cover, T.M. & Thomas, J.A. (1991): Elements of Information Theory. John Wiley and Sons, New York.
Hoeffding, W. (1963): Probability inequalities for sums of bounded random variables. American Statistical Association Journal 58, 13–30.
Hopcroft, J.E. & Ullman, J.D. (1979): “Introduction to automata theory, languages and computation”. Addison Wesley, Reading, Massachusetts.
Oncina, J. &. García, P. (1994): Inference of rational tree sets. Universidad Politécnica de Valencia, Internal Report DSIC-ii-1994-23.
Sakakibara, Y. (1992): Efficient learning of context-free grammars from positive structural examples. Information and Computation 97, 23–60.
Stolcke, A. & Omohundro, S. (1993): Hidden Markov model induction by Bayesian model merging in “Advances in Neural Information Processing Systems 5” (C.L. Giles, S.J. Hanson and J.D. Cowan, Eds.). Morgan-Kaufman, Menlo Park, California.
Wetherell, C.S. (1980): Probabilistic Languages: A Review and Some Open Questions ACM Computing Survey 12 361–379
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carrasco, R.C., Oncina, J., Calera, J. (1998). Stochastic inference of regular tree languages. In: Honavar, V., Slutzki, G. (eds) Grammatical Inference. ICGI 1998. Lecture Notes in Computer Science, vol 1433. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054075
Download citation
DOI: https://doi.org/10.1007/BFb0054075
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64776-8
Online ISBN: 978-3-540-68707-8
eBook Packages: Springer Book Archive