IDS: An Incremental Learning Algorithm for Finite Automata

2012/06/13 by Muddassar Azam Sindhu, Sindhu, Muddassar A., Karl Meinke +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Search Problems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1206.2691

openalex publication_date 2012/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• DFAMiner: Mining minimal separating DFAs from labelled samples
• DeepDFA: Automata Learning through Neural Probabilistic Relaxations
• Learning Several Languages from Labeled Strings: State Merging and Evolutionary Approaches
• Inference of Deterministic Finite Automata via Q-Learning
• On Learning Polynomial Recursive Programs