一句话：引入 P-finite 自动机，并证明其可在 Angluin 的 MAT 精确学习模型中多项式时间学习。
论文研究递归程序与自动机的可学习性，提出 P-finite 自动机：它是加权自动机的推广，转移权重可多项式的依赖于输入字长度，也可视为一种简单尾递归程序，其中递归调用参数可非线性地引用记录递归次数的变量。该命名源于一元字母表上 P-finite 自动机计算满足多项式系数线性递推的 P-finite 序列。核心结果证明，P-finite 自动机在 Angluin 的 MAT 精确学习模型中可多项式时间学习，推广了 DFA 和域上加权自动机可在 MAT 模型多项式时间学习的经典结果。
We introduce the class of P-finite automata. These are a generalisation of weighted automata, in which the weights of transitions can depend polynomially on the length of the input word. P-finite automata can also be viewed as simple tail-recursive programs in which the arguments of recursive calls can non-linearly refer to a variable that counts the number of recursive calls. The nomenclature is motivated by the fact that over a unary alphabet P-finite automata compute so-called P-finite sequences, that is, sequences that satisfy a linear recurrence with polynomial coefficients. Our main result shows that P-finite automata can be learned in polynomial time in Angluin’s MAT exact learning model. This generalises the classical results that deterministic finite automata and weighted automata over a field are respectively polynomial-time learnable in the MAT model.
@article{paperbot2620,
title = {On Learning Polynomial Recursive Programs},
author = {Alex Buna-Marginean and Vincent Cheval and Mahsa Shirmohammadi and James Worrell},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {POPL},
year = {2024},
doi = {10.1145/3632876}
}