论文标题
在多项式递归序列上
On polynomial recursive sequences
论文作者
论文摘要
我们研究多项式递归序列的表达能力，这是众所周知的线性递归序列的非线性扩展。这些序列自然出现在对加权自动机的非线性扩展的研究中，其中（非表达性结果都转化为类别的分离。多项式递归序列的典型示例是B_N = N！。我们的主要结果是序列u_n = n^n不是多项式递归。
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.
