SMT-Based Active Learning of Weighted Automata
For researchers in automata learning and formal methods, this offers a practical and robust alternative to Hankel/L*-style methods for weighted automata.
The paper presents an SMT-based active learning algorithm for nondeterministic weighted automata that is parametric in a given semiring and guaranteed to produce minimal WFAs upon termination. Experiments show it outperforms a naive baseline and is competitive with state-of-the-art, producing smaller automata with fewer teacher interactions.
We present an SMT-based active learning algorithm for nondeterministic weighted automata (WFAs) as a practical and robust alternative to Hankel/L*-style methods. Our algorithm is parametric in a given semiring and, if it terminates, guaranteed to produce minimal WFAs. We prove partial correctness and provide a sufficient termination condition, which in particular implies termination for all finite semirings. Our extensive experimental evaluation shows that our algorithm is capable of learning numerous minimal WFAs over both finite and infinite semirings, vastly outperforms a naive baseline, and is competitive with a state-of-the-art algorithm while producing significantly smaller automata and requiring less interaction with the teacher.