一句话：提出主动学习通用归约，并给出数环上加权自动机的多项式时间精确学习算法，输出近最小自动机。
本文研究加权自动机的主动学习问题。作者受近期将整数上加权自动机精确学习多项式归约到有理数上加权自动机的工作启发，提出一个通用的归约过程。该过程改进了范畴论自动机学习算法的效率，并对其在具体范畴中实例化时的实现复杂度提出新问题。第二个主要贡献是在数环，即代数数域中的整数环上，分析具体复杂度。假设给定数环的完整表示，作者得到 O_K 加权自动机的精确学习算法，其运行时间为目标自动机大小、最长反例长度对数、数域次数及判别式对数的多项式。算法产生的自动机最多比最小自动机多一个状态；作者还证明若要做得更好，则需要求解主理想问题，而该问题目前最好的算法是量子多项式时间。
We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted automata over integers to that for weighted automata over rationals (Buna-Marginean et al. 2024). Our procedure improves the efficiency of a category-theoretic automata learning algorithm, and poses new questions about the complexity of its implementation when instantiated to concrete categories.As our second main contribution, we address these complexity aspects in the concrete setting of learning weighted automata over number rings, that is, rings of integers in an algebraic number field. Assuming a full representation of a number ring ${{\mathcal{O}}_K}$, we obtain an exact learning algorithm of ${{\mathcal{O}}_K}$-weighted automata that runs in polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of the number field, and the logarithm of its discriminant. Our algorithm produces an automaton that has at most one more state than the minimal one, and we prove that doing better requires solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.
@inproceedings{paperbot8662,
title = {Learning Weighted Automata over Number Rings, Concretely and Categorically},
author = {Quentin Aristote and Sam van Gool and Daniela Petrişan and Mahsa Shirmohammadi},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00038}
}