The paper "An L# Based Algorithm for Active Learning of Minimal Separating Automata" by Jasper Laumen, Leonne Snel and Frits Vaandrager will appear in the Proceedings of the 38th International Conference on Computer Aided Verification (CAV 2026), July 26-29 2026, Lisbon, Portugal. A full version is available at https://arxiv.org/abs/2605.15294
The paper proposes a simple active learning algorithm, inspired by L#, that learns a minimal separating DFA for disjoint languages L1 and L2, if one exists. Experiments show that our algorithm significantly outperforms existing active learning algorithms on both randomly generated and industrial benchmarks. 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.
