Query learning of regular tree languages: How to avoid dead states
F Drewes, J Högberg - Theory of Computing Systems, 2007 - Springer
F Drewes, J Högberg
Theory of Computing Systems, 2007•SpringerWe 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.
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.
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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果