Abstract
We generalize an inference algorithm by Angluin, that learns a regular string language from a “minimally adequate teacher”, to regular tree languages. This improves a similar algorithm proposed by Sakakibara. In particular, we show how our algorithm can be used to avoid dead states, thus answering a question by Sakakibara.
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
Dana Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75:87–106, 1987.
W.S. Brainerd. The minimalization of tree automata. Information and Computation, 13:484–491, 1968.
Frank Drewes. Tree-based picture generation. Theoretical Computer Science, 246:1–51, 2000.
Joost Engelfriet. Graph grammars and tree transducers. In S. Tison, editor, Proc. CAAP 94, volume 787 of Lecture Notes in Computer Science, pages 15–37. Springer, 1994.
L.S. Levy and A.K. Joshi. Skeletal structural descriptions. Information and Control, 39:192–211, 1978.
Yasubumi Sakakibara. Learning context-free grammars from structural data in polynomial time. Theoretical Computer Science, 76:223–242, 1990.
James W. Thatcher and Jesse B. Wright. Generalized finite automata theory with an application to a decision-problem of second-order logic. Mathematical Systems Theory, 2:57–81, 1968.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Drewes, F., Högberg, J. (2003). Learning a Regular Tree Language from a Teacher. In: Ésik, Z., Fülöp, Z. (eds) Developments in Language Theory. DLT 2003. Lecture Notes in Computer Science, vol 2710. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45007-6_22
Download citation
DOI: https://doi.org/10.1007/3-540-45007-6_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40434-7
Online ISBN: 978-3-540-45007-8
eBook Packages: Springer Book Archive