Document Open Access Logo

On Polynomial Recursive Sequences

Authors Michaël Cadilhac , Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, Géraud Sénizergues

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.117.pdf
  • Filesize: 0.7 MB
  • 17 pages

Document Identifiers

Author Details

Michaël Cadilhac
  • DePaul University, Chicago, IL, USA
Filip Mazowiecki
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbücken, Germany
Charles Paperman
  • Université de Lille, Villeneuve d'Ascq, France
Michał Pilipczuk
  • University of Warsaw, Poland
Géraud Sénizergues
  • Université de Bordeaux, France

Funding

  • Pilipczuk, Michał: This work is a part of project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement No. 677651.

Acknowledgements

We thank Maria Donten-Bury for suggesting the proof of Theorem 11 presented here. This proof replaced our previous more elaborate and less transparent argument. We also thank James Worrell, David Purser and Markus Whiteland for helpful comments. The research for this work was carried out in part at the Autobóz Research Camp in 2019 in Firbush, Scotland. Finally, we thank the participants of the automata seminar at the University of Warsaw for an insightful discussion on the class of rational recursive sequences (considered in Section 7).

Cite As Get BibTex

Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, and Géraud Sénizergues. On Polynomial Recursive Sequences. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 117:1-117:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.117

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ⁿ is not polynomial recursive.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • recursive sequences
  • expressive power
  • weighted automata
  • higher-order pushdown automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Shaull Almagor, Udi Boker, and Orna Kupferman. What’s decidable about weighted automata? In Automated Technology for Verification and Analysis, 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011. Proceedings, pages 482-491, 2011. URL: https://doi.org/10.1007/978-3-642-24372-1_37.
  2. Ronald Alter and K. K. Kubota. Prime and prime power divisibility of Catalan numbers. Journal of Combinatorial Theory, Series A, 15(3):243-256, 1973. URL: https://doi.org/10.1016/0097-3165(73)90072-1.
  3. Rajeev Alur and Pavol Cerný. 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, pages 1-12, 2010. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1.
  4. Rajeev Alur, Loris D'Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan. 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, pages 13-22, 2013. URL: https://doi.org/10.1109/LICS.2013.65.
  5. James K Baker. Trainable grammars for speech recognition. The Journal of the Acoustical Society of America, 65(S1):S132-S132, 1979. Google Scholar
  6. Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki. A robust class of linear recurrence sequences. In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, January 13-16, 2020, Barcelona, Spain, pages 9:1-9:16, 2020. URL: https://doi.org/10.4230/LIPIcs.CSL.2020.9.
  7. Michael Benedikt, Timothy Duff, Aditya Sharad, and James Worrell. Polynomial automata: Zeroness and applications. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1-12, 2017. URL: https://doi.org/10.1109/LICS.2017.8005101.
  8. Vijay Bhattiprolu, Spencer Gordon, and Mahesh Viswanathan. Extending Parikh’s 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, pages 3-19, 2017. URL: https://doi.org/10.1007/978-3-319-66335-7_1.
  9. Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Theor. Comput. Sci., 380(1-2):69-86, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02.055.
  10. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata. Springer, 1st edition, 2009. Google Scholar
  11. Julien Ferté, Nathalie Marin, and Géraud Sénizergues. Word-mappings of level 2. Theory Comput. Syst., 54(1):111-148, 2014. URL: https://doi.org/10.1007/s00224-013-9489-5.
  12. S. Fratani and Géraud Sénizergues. Iterated pushdown automata and sequences of rational numbers. Ann. Pure Appl. Logic, 141(3):363-411, 2006. URL: https://doi.org/10.1016/j.apal.2005.12.004.
  13. Pierre Ganty and Elena Gutiérrez. 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, pages 32:1-32:20, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.32.
  14. Stefan Gerhold. On some non-holonomic sequences. Electr. J. Comb., 11(1), 2004. URL: http://www.combinatorics.org/Volume_11/Abstracts/v11i1r87.html.
  15. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki. Skolem’s problem-on the border between decidability and undecidability. Technical report, Technical Report 683, Turku Centre for Computer Science, 2005. Google Scholar
  16. Manuel Kauers and Peter Paule. The Concrete Tetrahedron - Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Texts & Monographs in Symbolic Computation. Springer, 2011. URL: https://doi.org/10.1007/978-3-7091-0445-3.
  17. Stephan Kreutzer and Cristian Riveros. 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, pages 113-122, 2013. URL: https://doi.org/10.1109/LICS.2013.16.
  18. Serge Lang. Algebra. Graduate Texts in Mathematics. Springer, 2002. Google Scholar
  19. Filip Mazowiecki and Cristian Riveros. Copyless cost-register automata: Structure, expressiveness, and closure properties. J. Comput. Syst. Sci., 100:1-29, 2019. URL: https://doi.org/10.1016/j.jcss.2018.07.002.
  20. Joël Ouaknine and James Worrell. On linear recurrence sequences and loop termination. SIGLOG News, 2(2):4-13, 2015. URL: https://dl.acm.org/citation.cfm?id=2766191.
  21. Géraud Sénizergues. 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, pages 24-32, 2007. URL: https://doi.org/10.1007/978-3-540-74510-5_6.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact