Query Learning of Regular Tree Languages: How to Avoid Dead States
2007 (English)In: Theory of Computing Systems, ISSN 1432-4350, Vol. 40, no 2, 163-185 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2007. Vol. 40, no 2, 163-185 p.
IdentifiersURN: urn:nbn:se:umu:diva-9267DOI: 10.1007/s00224-005-1233-3OAI: oai:DiVA.org:umu-9267DiVA: diva2:148938