{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T12:38:24Z","timestamp":1774355904278,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T00:00:00Z","timestamp":1622592000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T00:00:00Z","timestamp":1622592000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the expressive power of <jats:italic>polynomial recursive sequences<\/jats:italic>, 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 <jats:italic>b<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> = <jats:italic>n<\/jats:italic>!. Our main result is that the sequence <jats:italic>u<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> = <jats:italic>n<\/jats:italic><jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> is not polynomial recursive.<\/jats:p>","DOI":"10.1007\/s00224-021-10046-9","type":"journal-article","created":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T14:23:30Z","timestamp":1622643810000},"page":"593-614","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On Polynomial Recursive Sequences"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9828-9129","authenticated-orcid":false,"given":"Micha\u00ebl","family":"Cadilhac","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4535-6508","authenticated-orcid":false,"given":"Filip","family":"Mazowiecki","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6658-5238","authenticated-orcid":false,"given":"Charles","family":"Paperman","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7891-1988","authenticated-orcid":false,"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5800-2506","authenticated-orcid":false,"given":"G\u00e9raud","family":"S\u00e9nizergues","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,2]]},"reference":[{"key":"10046_CR1","doi-asserted-by":"publisher","unstructured":"Almagor, S., Boker, U., Kupferman, O.: What\u2019s decidable about weighted automata?. In: Automated Technology for Verification and Analysis, 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011. Proceedings, pp 482\u2013491 (2011). https:\/\/doi.org\/10.1007\/978-3-642-24372-1_37","DOI":"10.1007\/978-3-642-24372-1_37"},{"issue":"3","key":"10046_CR2","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0097-3165(73)90072-1","volume":"15","author":"R Alter","year":"1973","unstructured":"Alter, R., Kubota, K.K.: Prime and prime power divisibility of Catalan numbers. J. Combinat. Theory Ser. A 15(3), 243\u2013256 (1973). http:\/\/www.sciencedirect.com\/science\/article\/pii\/0097316573900721. https:\/\/doi.org\/10.1016\/0097-3165(73)90072-1","journal-title":"J. Combinat. Theory Ser. A"},{"key":"10046_CR3","doi-asserted-by":"publisher","unstructured":"Alur, R., Cern\u00fd, P.: Expressiveness of streaming string transducers. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, pp 1\u201312 (2010). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2010.1","DOI":"10.4230\/LIPIcs.FSTTCS.2010.1"},{"key":"10046_CR4","doi-asserted-by":"publisher","unstructured":"Alur, R., D\u2019Antoni, L., Deshmukh, J.V., Raghothaman, M., Yuan, Y.: Regular functions and cost register automata. In: 28th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013, pp 13\u201322 (2013). https:\/\/doi.org\/10.1109\/LICS.2013.65","DOI":"10.1109\/LICS.2013.65"},{"issue":"S1","key":"10046_CR5","doi-asserted-by":"publisher","first-page":"S132","DOI":"10.1121\/1.2017061","volume":"65","author":"JK Baker","year":"1979","unstructured":"Baker, J.K.: Trainable grammars for speech recognition. J. Acoust. Soc. Am. 65(S1), S132\u2013S132 (1979)","journal-title":"J. Acoust. Soc. Am."},{"key":"10046_CR6","doi-asserted-by":"publisher","unstructured":"Barloy, C., Fijalkow, N., Lhote, N., Mazowiecki, F.: A robust class of linear recurrence sequences. In: 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, January 13-16, 2020, Barcelona, Spain, pp 9:1\u20139:16 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2020.9","DOI":"10.4230\/LIPIcs.CSL.2020.9"},{"key":"10046_CR7","doi-asserted-by":"publisher","unstructured":"Benedikt, M., Duff, T., Sharad, A., Worrell, J.: Polynomial automata: Zeroness and applications. In: 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pp 1\u201312 (2017). https:\/\/doi.org\/10.1109\/LICS.2017.8005101","DOI":"10.1109\/LICS.2017.8005101"},{"key":"10046_CR8","doi-asserted-by":"publisher","unstructured":"Bhattiprolu, V., Gordon, S., Viswanathan, M.: Extending Parikh\u2019s theorem to weighted and probabilistic context-free grammars. In: Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Berlin, Germany, September 5-7, 2017, Proceedings, pp 3\u201319 (2017). https:\/\/doi.org\/10.1007\/978-3-319-66335-7_1","DOI":"10.1007\/978-3-319-66335-7_1"},{"issue":"1-2","key":"10046_CR9","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2007.02.055","volume":"380","author":"M Droste","year":"2007","unstructured":"Droste, M., Gastin, P.: Weighted automata and weighted logics. Theor. Comput. Sci. 380(1-2), 69\u201386 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.02.055","journal-title":"Theor. Comput. Sci."},{"key":"10046_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5","volume-title":"Handbook of Weighted Automata","author":"M Droste","year":"2009","unstructured":"Droste, M., Kuich, W., Vogler, H.: Handbook of Weighted Automata, 1st edn. Springer, Berlin (2009)","edition":"1st edn."},{"issue":"1","key":"10046_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00224-013-9489-5","volume":"54","author":"J Fert\u00e9","year":"2014","unstructured":"Fert\u00e9, J., Marin, N., S\u00e9nizergues, G.: Word-mappings of level 2. Theory Comput. Syst. 54(1), 111\u2013148 (2014). https:\/\/doi.org\/10.1007\/s00224-013-9489-5","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"10046_CR12","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/j.apal.2005.12.004","volume":"141","author":"S Fratani","year":"2006","unstructured":"Fratani, S., S\u00e9nizergues, G.: Iterated pushdown automata and sequences of rational numbers. Ann. Pure Appl. Logic 141(3), 363\u2013411 (2006). https:\/\/doi.org\/10.1016\/j.apal.2005.12.004","journal-title":"Ann. Pure Appl. Logic"},{"key":"10046_CR13","doi-asserted-by":"publisher","unstructured":"Ganty, P., Guti\u00e9rrez, E.: The Parikh property for weighted context-free grammars. In: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, pp 32:1\u201332:20 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2018.32","DOI":"10.4230\/LIPIcs.FSTTCS.2018.32"},{"key":"10046_CR14","doi-asserted-by":"crossref","unstructured":"Gerhold, S.: On some non-holonomic sequences. Electr. J. Comb. 11(1). http:\/\/www.combinatorics.org\/Volume_11\/Abstracts\/v11i1r87.html (2004)","DOI":"10.37236\/1840"},{"key":"10046_CR15","unstructured":"Halava, V., Harju, T., Hirvensalo, M., Karhum\u00e4ki, J.: Skolem\u2019s problem-on the border between decidability and undecidability. Technical report, Technical report 683 turku centre for computer science (2005)"},{"key":"10046_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-0445-3","volume-title":"The Concrete Tetrahedron - Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Texts & Monographs in Symbolic Computation","author":"M Kauers","year":"2011","unstructured":"Kauers, M., Paule, P.: The Concrete Tetrahedron - Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Texts & Monographs in Symbolic Computation. Springer, Berlin (2011). https:\/\/doi.org\/10.1007\/978-3-7091-0445-3"},{"key":"10046_CR17","doi-asserted-by":"publisher","unstructured":"Kreutzer, S., Riveros, C.: Quantitative monadic second-order logic. In: 28th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013, pp 113\u2013122 (2013). https:\/\/doi.org\/10.1109\/LICS.2013.16","DOI":"10.1109\/LICS.2013.16"},{"key":"10046_CR18","volume-title":"Algebra. Graduate Texts in Mathematics","author":"S Lang","year":"2002","unstructured":"Lang, S.: Algebra. Graduate Texts in Mathematics. Springer, Berlin (2002)"},{"key":"10046_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2018.07.002","volume":"100","author":"F Mazowiecki","year":"2019","unstructured":"Mazowiecki, F., Riveros, C.: Copyless cost-register automata: Structure, expressiveness, and closure properties. J. Comput. Syst. Sci. 100, 1\u201329 (2019). https:\/\/doi.org\/10.1016\/j.jcss.2018.07.002","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10046_CR20","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/2766189.2766191","volume":"2","author":"J Ouaknine","year":"2015","unstructured":"Ouaknine, J., Worrell, J.: On linear recurrence sequences and loop termination. SIGLOG News 2(2), 4\u201313 (2015). https:\/\/dl.acm.org\/citation.cfm?id=2766191","journal-title":"SIGLOG News"},{"key":"10046_CR21","doi-asserted-by":"publisher","unstructured":"S\u00e9nizergues, G.: Sequences of level 1, 2, 3,..., k,... In: Computer Science - Theory and Applications, Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007, Proceedings, pp 24\u201332 (2007). https:\/\/doi.org\/10.1007\/978-3-540-74510-5_6","DOI":"10.1007\/978-3-540-74510-5_6"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10046-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10046-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10046-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T21:16:07Z","timestamp":1724447767000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10046-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,2]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10046"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10046-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,2]]},"assertion":[{"value":"24 April 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}