On polynomial recursive sequences
Résumé
We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is $b_n=n!$. Our main result is that the sequence $u_n=n^n$ is not polynomial recursive.
Origine : Fichiers produits par l'(les) auteur(s)