# On Learning Polynomial Recursive Programs

arXiv: https://arxiv.org/abs/2310.14725 · HTML: https://mlsanity.com/paper/2310.14725/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2023.

## Built on by (most cited first, 1 of 1)

- [SMT-Based Active Learning of Weighted Automata](https://mlsanity.com/paper/2605.07758/) (2026)

## Abstract (arXiv)

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.