2026-07-22T21:28:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12524 2024-03-06T10:50:21Z ddc:004 open_access

On Polynomial Recursive Sequences Cadilhac, Michaël Mazowiecki, Filip Paperman, Charles Pilipczuk, Michał Sénizergues, Géraud recursive sequences expressive power weighted automata higher-order pushdown automata 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michaël Cadilhac and Filip Mazowiecki and Charles Paperman and Michał Pilipczuk and Géraud Sénizergues 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.117 urn:nbn:de:0030-drops-125240 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.117 eng https://creativecommons.org/licenses/by/3.0/legalcode