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

Jasper Laumen, Leonne Snel, Frits Vaandrager (✉) · 2026

Read An L # L^{\#} Based Algorithm for Active Learning of Minimal Separating Automata by Jasper Laumen, Leonne Snel, Frits Vaandrager (✉) (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15294.txt.

Introduction

Jasper Laumen, Leonne Snel, and Frits Vaandrager propose a simple active-learning algorithm, drawn by L-sharp, for learning minimal separating automata. A deterministic finite machine splits two disjoint tongues by taking every word of one and refusing every word of the other. Such learners serve network-invariant learning, part-based checking rules, log-derived state machines, and bug-pattern notes. Tests show the new method a lot beats old active learners on random and industrial benchmarks.

Catalog record

CREATORJasper Laumen, Leonne Snel, Frits Vaandrager (✉)
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75614
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.15294

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An L # L^{\#} Based Algorithm for Active Learning of Minimal Separating Automata Jasper Laumen, Leonne Snel, Frits Vaandrager (✉) Abstract A DFA separates two disjoint languages L 1 L_{1} and L 2 L_{2} if it accepts every word in L 1 L_{1} and rejects every word in L 2 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 # L^{\#} , that learns a minimal separating DFA for disjoint languages L 1 L_{1} and L 2 L_{2} if one exists. Experiments show that our algorithm significantly outperforms existing active learning algorithms on both randomly generated and industrial benchmarks. 1 Introduction Let L_{1} and L_{2} be disjoint languages over some alphabet \Sigma . We say that a deterministic finite automaton (DFA) \mathcal{A} separates L_{1} and L_{2} if it accepts every word in L_{1} and rejects every word in L_{2} , that is, L_{1}\subseteq L(\mathcal{A}) and L_{2}\cap L(\mathcal{A})=\emptyset , with L(\mathcal{A}) the language accepted by \mathcal{A} . A minimal separating DFA is a separating DFA that has the least number of states among all separating DFAs. Algorithms for finding a minimal (or small) separating DFA have many applications, e.g. for computing network invariants [ 14 ] , contextual assumptions in compositional verification [ 6 ] , minimal DFAs that are consistent with a set of positively and negatively classified samples [ 8 ] , and bug pattern descriptions [ 36 ] . Finding a minimal separating DFA is nontrivial: for regular languages L_{1} and L_{2} , the decision problem “Does a separating DFA with k states exist?” is NP-hard [ 27 , 13 ] . If languages L_{1} and L_{2} are context-free, then the decision problem whether there exists a separating DFA is already undecidable [ 20 ] . SAT and SMT solvers may be used to compute minimal separating DFAs if L_{1} and L_{2} are regular [ 23 ] . However, in applications the minimal DFAs for L_{1} and L_{2} are typically big, whereas a minimal separating DFA \mathcal{A} is small. Since solvers are unable to handle such large instances of an NP-hard problem, researchers have resorted to the use of active learning algorithms for the construction of a separating DFA. Different types of queries have been used, also depending on the characteristics of the applications. A natural setting for learning separating DFAs is obtained by considering a slight variation of the Minimally Adequate Teacher (MAT) framework of [ 1 ] in which a learner tries to identify a minimal separating DFA by posing two types of queries to a teacher [ 20 , 21 ] : • A membership query w\in\Sigma^{*} . In response, the teacher answers “ + ” if w\in L_{1} , “ - ” if w\in L_{2} , and “don’t care” (or “don’t now”, “maybe”, etc), denoted by \square , in any other case. • A validity query for a hypothesis DFA \mathcal{H} . In response, the teacher answers “yes” if \mathcal{H} separates L_{1} and L_{2} , and otherwise returns a counterexample, that is, a sequence w such that w\in L_{1}\setminus L(\mathcal{H}) or w\in L_{2}\cap L(\mathcal{H}) . A first active learning algorithm for learning a minimal separating DFA for regular languages L_{1} and L_{2} using membership and validity queries was proposed by Grinchtein et al. [ 14 ] . Their algorithm, which is inspired by earlier work of Pena & Oliveira [ 26 ] , adapts Angluin’s L^{*} algorithm [ 1 ] by extending the observation table with don’t care values ( \square ) besides accept ( + ) and reject values ( - ), and uses the algorithm of Biermann & Feldman [ 4 ] to construct a DFA that is consistent with the observation table. Chen et al. [ 6 ] presented an L^{*} -based algorithm using 3DFAs that significantly outperformed the algorithm of Grinchtein et al. [ 14 ] . Their algorithm also uses membership queries, but instead of validity queries it poses the (strictly more powerful) containment queries : • A containment query for a hypothesis DFA \mathcal{H} has one of the following four types: (i) L_{1}\subseteq L(\mathcal{H}) , (ii) L(\mathcal{H})\subseteq L_{1} , (iii) \overline{L_{2}}\subseteq L(\mathcal{H}) , and (iv) L(\mathcal{H})\subseteq\overline{L_{2}} . The teacher returns “yes” if the containment holds, and provides a counterexample otherwise. Leucker & Neider [ 20 ] presented a survey of learning algorithms for separating DFAs, suggested some improvements of the algorithms of [ 14 , 6 ] , but did not explore any implementation or benchmarking. Recently, however, Yaacov et al. [ 36 ] implemented an improvement of the algorithm of [ 6 ] suggested by Leucker & Neider [ 20 ] , and used it for producing compact and informative bug descriptions for a collection of industrial benchmarks taken from [ 18 ] . However, in order to make their approach sufficiently scalable, they used the state merging algorithm RPNI [ 25 ] (rather than SAT/SMT solving as suggested in [ 20 ] ) to obtain small (rather than minimal) separating DFAs. Moeller et al. [ 21 ] adapted Angluin’s L^{*} algorithm for learning minimal separating DFAs using membership and validity queries, and evaluated their L^{*}_{\square} algorithm on the benchmark collection of Oliveira & Silva [ 24 ] and some smaller benchmarks of Lee et al. [ 19 ] . Their implementation can only handle about half of the benchmarks of [ 24 ] , due to scalability issues. An interesting new type of queries was recently proposed by Walinga et al. [ 35 ] . They consider the problem of learning a state machine from an amount of log data that is so big that conventional state merging algorithms cannot handle it. In order to solve this problem, they use database technology to efficiently query a large dataset stored on disk, and pose database queries of the following form: • A database query is a triple (w,n,k) with w\in\Sigma^{*} and n,k\in\mathbb{N} . The teacher returns at most k (classified) words of length at most n with w as a prefix. Note that database queries are incomparable to membership, validity and containment queries. The DAALder algorithm of [ 35 ] uses database queries to grow a prefix-tree acceptor (PTA) in a manner inspired by the L^{\#} algorithm [ 31 ] . The state merging tool FlexFringe [ 34 ] is then used to turn this PTA into a small state machine. DAALder is evaluated on benchmarks with artificial trace data. The main result of this article is L^{\#}_{\Box} , a new and simple algorithm inspired by L^{\#} [ 31 , 32 ] , for learning a minimal separating DFA using membership and validity queries. Our algorithm is based on the following key ideas: 1. By storing query results in an observation tree (PTA) and using apartness of basis states as the main driver for membership queries, our algorithm has more options to make progress with learning than L^{*} -based algorithms, which are limited by the prefixes and suffices in an observation table; this helps when the teacher gives

Read the complete text