























Abstract: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.
| Comments: | Appearing in CAV 2026 |
| Subjects: | Formal Languages and Automata Theory (cs.FL); Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.07758 [cs.FL] |
| (or arXiv:2605.07758v1 [cs.FL] for this version) | |
| https://doi.org/10.48550/arXiv.2605.07758 arXiv-issued DOI via DataCite (pending registration) |
From: Tiago Ferreira [view email]
[v1]
Fri, 8 May 2026 14:01:29 UTC (1,932 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。