An $L^{\#}$ Based Algorithm for Active Learning of Minimal Separating Automata
For researchers needing to learn small separating automata in applications like network invariants and compositional verification, this algorithm offers a more efficient solution.
The paper proposes an active learning algorithm for minimal separating DFAs, inspired by L#, and shows it significantly outperforms existing algorithms on random and industrial benchmarks.
A DFA separates two disjoint languages $L_1$ and $L_2$ if it accepts every word in $L_1$ and rejects every word in $L_2$. Algorithms for active learning of small separating DFAs have many applications, e.g., for learning network invariants, learning contextual assumptions in compositional verification, learning state machines from large amounts of log data, and learning bug pattern descriptions. We propose a simple active learning algorithm, inspired by $L^{\#}$, that learns a minimal separating DFA for disjoint languages $L_1$ and $L_2$ if one exists. Experiments show that our algorithm significantly outperforms existing active learning algorithms on both randomly generated and industrial benchmarks.