Abstract
We generalize an inference algorithm by Angluin, that learns a regular string language from a "minimally adequate teacher", to regular tree languages. The (deterministic bottom-up) finite tree automaton constructed by the learning algorithm is the minimal partial one recognizing the unknown language. This improves a similar algorithm proposed by Sakakibara by avoiding dead states both in the resulting automaton and the learning phase, which also leads to a considerable improvement with respect to efficiency.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Drewes, F., Högberg, J. Query Learning of Regular Tree Languages: How to Avoid Dead States. Theory Comput Syst 40, 163–185 (2007). https://doi.org/10.1007/s00224-005-1233-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-005-1233-3