Learning a Regular Tree Language from a Teacher

摘要

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 Sakak-ibara. In particular, we show how our algorithm can be used to avoid dead states, thus answering a question by Sakakibara.