IDS: An Incremental Learning Algorithm for Finite Automata
This work addresses incremental learning of finite automata for software engineering applications, but it is incremental as it builds on existing concepts like distinguishing sequences.
The authors tackled the problem of incremental learning of deterministic finite automata (DFA) by introducing a new algorithm called IDS, which is based on distinguishing sequences and is proven to correctly learn in the limit, with empirical analysis showing it is efficient for software engineering applications like testing and model inference.
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 (Angluin81). 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.