An L^# Based Algorithm for Active Learning of Minimal Separating Automata

2026/05/14 by Jasper Laumen, Leonne Snel, Frits Vaandrager · 1 voice
Computer Science · #cs.FL

paper · pdf · doi:10.48550/arxiv.2605.15294

Abstract

A DFA separates two disjoint languages L₁ and L₂ if it accepts every word in L₁ and rejects every word in L₂. 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₁ and L₂ if one exists. Experiments show that our algorithm significantly outperforms existing active learning algorithms on both randomly generated and industrial benchmarks.

Citations

• Automata Models for Effective Bug Pattern Description
• Database-assisted automata learning
• Active Learning of Mealy Machines with Timers
• Scalable Tree-based Register Automata Learning
• Provengo: A Tool Suite for Scenario Driven Model-Based Testing
• Bisimilar States in Uncertain Structures
• A New Approach for Active Automata Learning Based on Apartness
• Learning regular sets from queries and counterexamples
• On the Synthesis of Finite-State Machines from Samples of Their Behavior

Discussions

• Jasper Laumen, Leonne Snel, Frits Vaandrager: An $L^{\#}$ Based Algorithm for Active Learning of Minimal Separating Automata https://arxiv.org/abs/2605.15294 https://arxiv.org/pdf/2605.15294 https://a [bsky, 0 points, 0 comments]

Related

• A New Approach for Active Automata Learning Based on Apartness
• DFAMiner: Mining minimal separating DFAs from labelled samples
• Learning Several Languages from Labeled Strings: State Merging and Evolutionary Approaches
• Deciding minimal distinguishing DFAs is NP-complete
• SMT-Based Active Learning of Weighted Automata