Document Open Access Logo

A Robust Class of Linear Recurrence Sequences

Authors Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, Filip Mazowiecki

PDF

File

Thumbnail PDF
PDF
LIPIcs.CSL.2020.9.pdf
  • Filesize: 0.67 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • linear recurrence sequences
  • weighted automata
  • cost-register automata

Metrics

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

Abstract

We introduce a subclass of linear recurrence sequences which we call poly-rational sequences because they are denoted by rational expressions closed under sum and product. We show that this class is robust by giving several characterisations: polynomially ambiguous weighted automata, copyless cost-register automata, rational formal series, and linear recurrence sequences whose eigenvalues are roots of rational numbers.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CSL.2020.9

Author Details

Corentin Barloy
  • École Normale Supérieure de Paris, France
Nathanaël Fijalkow
  • CNRS, LaBRI, Bordeaux, France
  • The Alan Turing Institute of data science, London, United Kingdom
Nathan Lhote
  • University of Warsaw, Poland
Filip Mazowiecki
  • LaBRI, Université de Bordeaux, France

Funding

The second author was supported by the CODYS project ANR-18-CE40-0007.

Acknowledgements

We thank Théodore Lopez for reporting a maths typo in Lemma 10, S. Akshay for fruitful discussions, and the anonymous reviewers for their useful suggestions.

References

  1. S. Akshay, Nikhil Balaji, and Nikhil Vyas. Complexity of Restricted Variants of Skolem and Related Problems. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, pages 78:1-78:14, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.78.
  2. Shaull Almagor, Michaël Cadilhac, Filip Mazowiecki, and Guillermo A. Pérez. Weak Cost Register Automata Are Still Powerful. In Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings, pages 83-95, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8_7.
  3. 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.
  4. Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki. A Robust Class of Linear Recurrence Sequences. CoRR, abs/1908.03890, 2019. URL: http://arxiv.org/abs/1908.03890.
  5. Mireille Bousquet-Mélou. Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages. In STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings, pages 18-35, 2005. URL: https://doi.org/10.1007/978-3-540-31856-9_2.
  6. Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Theoretical Computer Science, 380(1-2):69-86, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02.055.
  7. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata. Springer, 1st edition, 2009. Google Scholar
  8. Nathanaël Fijalkow, Cristian Riveros, and James Worrell. Probabilistic Automata of Bounded Ambiguity. In Roland Meyer and Uwe Nestmann, editors, 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany, volume 85 of LIPIcs, pages 19:1-19:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2017.19.
  9. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete mathematics - a foundation for computer science (2. ed.). Addison-Wesley, 1994. Google Scholar
  10. Daniel Kirsten and Sylvain Lombardy. Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings, pages 589-600, 2009. URL: https://doi.org/10.4230/LIPIcs.STACS.2009.1850.
  11. Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur. Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoretical Computer Science, 327(3):349-373, 2004. URL: https://doi.org/10.1016/j.tcs.2004.02.049.
  12. 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.
  13. Filip Mazowiecki and Cristian Riveros. Maximal Partition Logic: Towards a Logical Characterization of Copyless Cost Register Automata. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, September 7-10, 2015, Berlin, Germany, pages 144-159, 2015. URL: https://doi.org/10.4230/LIPIcs.CSL.2015.144.
  14. Filip Mazowiecki and Cristian Riveros. Pumping Lemmas for Weighted Automata. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 50:1-50:14, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.50.
  15. Filip Mazowiecki and Cristian Riveros. Copyless cost-register automata: Structure, expressiveness, and closure properties. Journal of Computer and System Sciences, 100:1-29, 2019. URL: https://doi.org/10.1016/j.jcss.2018.07.002.
  16. Joël Ouaknine and James Worrell. On the Positivity Problem for Simple Linear Recurrence Sequences,. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 318-329, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_27.
  17. Joël Ouaknine and James Worrell. Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 330-341, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_28.
  18. Joël Ouaknine and James Worrell. On linear recurrence sequences and loop termination. SIGLOG News, 2(2):4-13, 2015. URL: https://doi.org/10.1145/2766189.2766191.
  19. Rachid Rebiha, Arnaldo Vieira Moura, and Nadir Matringe. On the Termination of Linear and Affine Programs over the Integers. CoRR, abs/1409.4230, 2014. URL: http://arxiv.org/abs/1409.4230.
  20. Marcel Paul Schützenberger. On the Definition of a Family of Automata. Information and Control, 4(2-3):245-270, 1961. URL: https://doi.org/10.1016/S0019-9958(61)80020-X.
  21. Terence Tao. Structure and randomness: pages from year one of a mathematical blog. American Mathematical Society Providence, RI, 2008. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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