基于SMT求解器学习加权自动机，更高效且自动机更小。
SMT-Based Active Learning of Weighted Automata
- 用SMT求解器替代传统方法，参数化支持多种代数结构。
- 在有限和无限代数上均能学到最小自动机，且交互次数更少。
- 适合需要紧凑模型和低交互成本的自动机学习场景。
我们提出一种基于SMT的主动学习算法，用于非确定性加权自动机（WFAs），作为Hankel/L*-型方法的实用且稳健替代方案。该算法在给定半环上参数化，若终止，则保证生成最小化的WFAs。我们证明了部分正确性，并给出了一个充分终止条件，特别地，对所有有限半环都保证终止。大量实验表明，该算法能在有限和无限半环上学习出众多最小化WFAs，显著优于朴素基线，在与最先进算法竞争中表现优异，且生成的自动机更小，与教师的交互更少。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。