  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.
