On polynomial recursive sequences

2020/02/20 by Cadilhac, Michaël, Mazowiecki, Filip, Paperman, Charles +2
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2002.08630

Abstract

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ⁿ is not polynomial recursive.

Related

• A Robust Class of Linear Recurrence Sequences
• On Learning Polynomial Recursive Programs
• Preliminary results about a wide class of recursive nonlnear sequences
• Sequences: Polynomial, C-finite, Holonomic, ...
• Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata