Document Open Access Logo

On Rational Recursive Sequences

Authors Lorenzo Clemente , Maria Donten-Bury , Filip Mazowiecki, Michał Pilipczuk

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.24.pdf
  • Filesize: 1.04 MB
  • 21 pages

Document Identifiers

Author Details

Lorenzo Clemente
  • University of Warsaw, Poland
Maria Donten-Bury
  • University of Warsaw, Poland
Filip Mazowiecki
  • University of Warsaw, Poland
Michał Pilipczuk
  • University of Warsaw, Poland

Funding

This work is a result of research conducted within projects no. 2017/26/D/ST6/00201 (Lorenzo Clemente) and 2017/26/E/ST1/00231 (Maria Donten-Bury) financed by National Science Centre, Poland, as well as a part of projects INFSYS (Lorenzo Clemente and Filip Mazowiecki) and BOBR (Michał Pilipczuk) that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreements no. 950398 and 948057, respectively).

Acknowledgements

We thank Szymon Toruńczyk for helpful discussions.

Cite AsGet BibTex

Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki, and Michał Pilipczuk. On Rational Recursive Sequences. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.24

Abstract

We study the class of rational recursive sequences (ratrec) over the rational numbers. A ratrec sequence is defined via a system of sequences using mutually recursive equations of depth 1, where the next values are computed as rational functions of the previous values. An alternative class is that of simple ratrec sequences, where one uses a single recursive equation, however of depth k: the next value is defined as a rational function of k previous values. We conjecture that the classes ratrec and simple ratrec coincide. The main contribution of this paper is a proof of a variant of this conjecture where the initial conditions are treated symbolically, using a formal variable per sequence, while the sequences themselves consist of rational functions over those variables. While the initial conjecture does not follow from this variant, we hope that the introduced algebraic techniques may eventually be helpful in resolving the problem. The class ratrec strictly generalises a well-known class of polynomial recursive sequences (polyrec). These are defined like ratrec, but using polynomial functions instead of rational ones. One can observe that if our conjecture is true and effective, then we can improve the complexities of the zeroness and the equivalence problems for polyrec sequences. Currently, the only known upper bound is Ackermanian, which follows from results on polynomial automata. We complement this observation by proving a PSPACE lower bound for both problems for polyrec. Our lower bound construction also implies that the Skolem problem is PSPACE-hard for the polyrec class.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • recursive sequences
  • polynomial automata
  • zeroness problem
  • equivalence problem

Metrics

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

Related Versions

References

  1. 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.
  2. Corentin Barloy and Lorenzo Clemente. Bidimensional linear recursive sequences and universality of unambiguous register automata. In Markus Bläser and Benjamin Monmege, editors, Proc. of STACS'21, volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1-8:15, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Google Scholar
  3. 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.
  4. M. Benedikt, T. Duff, A. Sharad, and J. Worrell. Polynomial automata: Zeroness and applications. In Proc. of LICS'17, pages 1-12, June 2017. URL: https://doi.org/10.1109/LICS.2017.8005101.
  5. Vincent D. Blondel and Natacha Portier. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. Linear Algebra and its Applications, 351-352:91-98, 2002. Fourth Special Issue on Linear Systems and Control. URL: https://doi.org/10.1016/S0024-3795(01)00466-9.
  6. Adrien Boiret, Radoslaw Piórkowski, and Janusz Schmude. Reducing transducer equivalence to register automata problems solved by "Hilbert Method". In Sumit Ganguly and Paritosh Pandya, editors, Proc. of FSTTCS'18, volume 122 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1-48:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.48.
  7. Mikołaj Bojańczyk. The Hilbert method for transducer equivalence. ACM SIGLOG News, 6(1):5-17, February 2019. URL: https://doi.org/10.1145/3313909.3313911.
  8. Mikołaj Bojańczyk and Wojciech Czerwiński. An automata toolbox, February 2018. URL: https://www.mimuw.edu.pl/~bojan/paper/automata-toolbox-book.
  9. Mikołaj Bojańczyk and Janusz Schmude. Some remarks on deciding equivalence for graph-to-graph transducers. In Javier Esparza and Daniel Kráľ, editors, Proc. of MFCS'20, volume 170 of LIPIcs, pages 19:1-19:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.19.
  10. Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud. Weakly-unambiguous parikh automata and their link to holonomic series. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, Proc. of ICALP'20, volume 168 of LIPIcs, pages 114:1-114:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.114.
  11. Alin Bostan and Antonio Jiménez-Pastor. On the exponential generating function of labelled trees. Comptes Rendus. Mathématique, 358(9-10):1005-1009, 2020. Google Scholar
  12. N. Bourbaki. Algebra II. Elements of Mathematics. Springer Verlag Berlin Heidelberg, 2003. Google Scholar
  13. Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, and Géraud Sénizergues. On polynomial recursive sequences. Theory of Computing Systems, pages 1-22, 2021. Google Scholar
  14. N. Chomsky and M. P. Schützenberger. The algebraic theory of context-free languages. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Systems, volume 35 of Studies in Logic and the Foundations of Mathematics, pages 118-161. Elsevier, 1963. URL: https://doi.org/10.1016/S0049-237X(08)72023-8.
  15. Lorenzo Clemente. On the complexity of the universality and inclusion problems for unambiguous context-free grammars. In Laurent Fribourg and Matthias Heizmann, editors, Proceedings 8th International Workshop on Verification and Program Transformation and 7th Workshop on Horn Clauses for Verification and Synthesis, Dublin, Ireland, 25-26th April 2020, volume 320 of EPTCS, pages 29-43. Open Publishing Association, 2020. URL: https://doi.org/10.4204/EPTCS.320.2.
  16. J. Denef and L. Lipshitz. Decision problems for differential equations. Journal of Symbolic Logic, 54(3):941-950, 1989. URL: https://doi.org/10.2307/2274755.
  17. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata. Springer, 1st edition, 2009. Google Scholar
  18. David S. Dummit and Richard M. Foote. Abstract Algebra. Wiley, 3rd edition, 2003. URL: http://gen.lib.rus.ec/book/index.php?md5=36e6532b72807b9ef6b27e52e8c62ccc.
  19. Vojtěch Forejt, Petr Jančar, Stefan Kiefer, and James Worrell. Language equivalence of probabilistic pushdown automata. Information and Computation, 237:1-11, 2014. Google Scholar
  20. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki. Skolem’s problem - on the border between decidability and undecidability, 2005. Google Scholar
  21. T. Harju and J. Karhumäki. The equivalence problem of multitape finite automata. Theoretical Computer Science, 78(2):347-355, 1991. URL: https://doi.org/10.1016/0304-3975(91)90356-7.
  22. 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.
  23. Leonard Lipshitz. D-finite power series. Journal of Algebra, 122(2):353-373, 1989. URL: https://doi.org/10.1016/0021-8693(89)90222-6.
  24. Kurt Mahler. Lectures on Transcendental Numbers. Lecture Notes in Mathematics 546. Springer-Verlag Berlin Heidelberg, 1st edition, 1976. Google Scholar
  25. J. Müller-Quade and R. Steinwandt. Basic algorithms for rational function fields. Journal of Symbolic Computation, 27(2):143-170, 1999. URL: https://doi.org/10.1006/jsco.1998.0246.
  26. Masayoshi Nagata. Theory of Commutative Fields. Translations of Mathematical Monographs, Vol. 125. American Mathematical Society, 1993. URL: http://gen.lib.rus.ec/book/index.php?md5=249c3cba331671e0fd3c692d01b54b94.
  27. Joël Ouaknine and James Worrell. On linear recurrence sequences and loop termination. ACM SIGLOG News, 2(2):4-13, April 2015. URL: https://doi.org/10.1145/2766189.2766191.
  28. Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  29. Azaria Paz. Introduction to probabilistic automata. Academic Press, 1971. Google Scholar
  30. Arto Salomaa and Marti Soittola. Automata-theoretic aspects of formal power series. Texts and Monographs in Computer Science. Springer, 1978. URL: https://doi.org/10.1007/978-1-4612-6264-0.
  31. Bruno Salvy. D-finiteness: Algorithms and applications. In Proc. of ISAAC'05, pages 2-3, New York, NY, USA, 2005. ACM. URL: https://doi.org/10.1145/1073884.1073886.
  32. Marcel Paul Schützenberger. On the definition of a family of automata. Information and Control, 4(2-3):245-270, 1961. Google Scholar
  33. Helmut Seidl, Sebastian Maneth, and Gregor Kemper. Equivalence of deterministic top-down tree-to-string transducers is decidable. J. ACM, 65(4):21:1-21:30, April 2018. URL: https://doi.org/10.1145/3182653.
  34. Richard P. Stanley and Sergey Fomin. Enumerative combinatorics, volume 2 of Cambridge studies in advanced mathematics. Cambridge University Press, 1 edition, 2001. Google Scholar
  35. Joris van der Hoeven. Computing with d-algebraic power series. Applicable Algebra in Engineering, Communication and Computing, 30(1):17-49, 2019. URL: https://doi.org/10.1007/s00200-018-0358-y.
  36. Tzeng Wen-Guey. On path equivalence of nondeterministic finite automata. Information Processing Letters, 58(1):43-46, 1996. URL: https://doi.org/10.1016/0020-0190(96)00039-7.
  37. James Worrell. Revisiting the equivalence problem for finite multitape automata. In Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, and David Peleg, editors, Proc. of ICALP'13, pages 422-433, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  38. Doron Zeilberger. A holonomic systems approach to special functions identities. Journal of Computational and Applied Mathematics, 32(3):321-368, 1990. URL: https://doi.org/10.1016/0377-0427(90)90042-X.
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 Imprint Privacy Contact