Correctness and Performance of an Incremental Learning Algorithm for Finite Automata
2010 (English)Report (Other academic)
We present a new algorithm IDSfor 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 IDSis an efficient algorithm for software engineering applications of automata learning, such as testing and model inference.
Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology , 2010. , 19 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-37678OAI: oai:DiVA.org:kth-37678DiVA: diva2:434775
QC 201108162011-08-162011-08-162011-08-22Bibliographically approved