@article{Cadilhac:Mazowiecki:Paperman:Pilipczuk:Senizergues:ToCS:2021,
    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 bn = n!. Our main result is that the sequence un = nn is not polynomial recursive.},
    Author = {Cadilhac, Micha{\"e}l and Mazowiecki, Filip and Paperman, Charles and Pilipczuk, Micha{{\l}} and S{\'e}nizergues, G{\'e}raud},
    Date = {2021/06/02},
    File = {On Polynomial Recursive Sequences - Cadilhac2021\_Article\_OnPolynomialRecursiveSequences.pdf},
    ISBN = {1433-0490},
    Journal = {Theory of Computing Systems},
    Title = {On Polynomial Recursive Sequences},
    URL = {https://doi.org/10.1007/s00224-021-10046-9},
    Year = {2021},
    bdsk-url-1 = {https://doi.org/10.1007/s00224-021-10046-9},
    date-added = {2021-10-21 10:19:04 +0200},
    date-modified = {2023-05-25 11:21:22 +0200},
    id = {Cadilhac2021},
    doi = {10.1007/s00224-021-10046-9}
}

@article{Cadilhac:Mazowiecki:Paperman:Pilipczuk:Senizergues:ToCS:2021, 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 bn = n!. Our main result is that the sequence un = nn is not polynomial recursive.}, Author = {Cadilhac, Micha{\"e}l and Mazowiecki, Filip and Paperman, Charles and Pilipczuk, Micha{{\l}} and S{\'e}nizergues, G{\'e}raud}, Date = {2021/06/02}, File = {On Polynomial Recursive Sequences - Cadilhac2021_Article_OnPolynomialRecursiveSequences.pdf}, ISBN = {1433-0490}, Journal = {Theory of Computing Systems}, Title = {On Polynomial Recursive Sequences}, URL = {https://doi.org/10.1007/s00224-021-10046-9}, Year = {2021}, bdsk-url-1 = {https://doi.org/10.1007/s00224-021-10046-9}, date-added = {2021-10-21 10:19:04 +0200}, date-modified = {2023-05-25 11:21:22 +0200}, id = {Cadilhac2021}, doi = {10.1007/s00224-021-10046-9} }