Learning Minimal Deterministic Automata from Inexperienced Teachers

Speaker

Daniel Neider (Informatik 7)
Title Learning Minimal Deterministic Automata from Inexperienced Teachers
When 16.01.2013, 10:00
Where Room 5052
Abstract A prominent learning algorithm is Angluin’s LΞ algorithm, which allows to learn a minimal deterministic automaton using so-called membership and equivalence queries addressed to a teacher. In many applications, however, a teacher might be unable to answer some of the membership queries because parts of the object to learn are not completely specified, not observable, it is too expensive to resolve these queries, etc. Then, these queries may be answered inconclusively. In this paper, we survey different algorithms to learn minimal deterministic automata in this setting in a coherent fashion. Moreover, we provide modifications and improvements for these algorithms, which are enabled by recent developments.