Back to Search
Start Over
On polynomial recursive sequences
- Publication Year :
- 2020
-
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^n is not polynomial recursive.
- Subjects :
- Computer Science - Formal Languages and Automata Theory
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2002.08630
- Document Type :
- Working Paper