Correctness and Performance of an Incremental Learning Algorithm for Finite Automata
2011 (English)Conference paper, Poster (Other academic)
We present a new algorithm IDS for incremental learning of deterministic finite automata (DFA). This algorithm is based on the concept of distinguishing sequences introduced in (Angluin, 1981). We give a rigorous proof that two versions of this learning algorithm correctly learn in the limit. Finally we present an empirical performance analysis that compares these two algorithms, focussing on learning times and different types of learning queries. We conclude that IDS is an efficient algorithm for software engineering applications of automata learning, such as testing and model inference.
Place, publisher, year, edition, pages
incremental learning, learning in the limit, distinguishing sequences, DFA learning
IdentifiersURN: urn:nbn:se:kth:diva-119089OAI: oai:DiVA.org:kth-119089DiVA: diva2:609697
Third Asian Conference on Machine Learning
QC 201303122013-03-062013-03-062013-03-12Bibliographically approved