Document Open Access Logo

Effective Divergence Analysis for Linear Recurrence Sequences

Authors Shaull Almagor, Brynmor Chapman, Mehran Hosseini, Joël Ouaknine, James Worrell

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2018.42.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Shaull Almagor
  • Department of Computer Science, Oxford University, UK
Brynmor Chapman
  • MIT CSAIL
Mehran Hosseini
  • Department of Computer Science, Oxford University, UK
Joël Ouaknine
  • Max Planck Institute for Software Systems, Germany & , Department of Computer Science, Oxford University, UK
James Worrell
  • Department of Computer Science, Oxford University, UK

Funding

  • Ouaknine, Joël: Supported by ERC grant AVS-ISS (648701)
  • Worrell, James: Supported by EPSRC Fellowship EP/N008197/1

Cite As Get BibTex

Shaull Almagor, Brynmor Chapman, Mehran Hosseini, Joël Ouaknine, and James Worrell. Effective Divergence Analysis for Linear Recurrence Sequences. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CONCUR.2018.42

Abstract

We study the growth behaviour of rational linear recurrence sequences. We show that for low-order sequences, divergence is decidable in polynomial time. We also exhibit a polynomial-time algorithm which takes as input a divergent rational linear recurrence sequence and computes effective fine-grained lower bounds on the growth rate of the sequence.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Algebraic algorithms
  • Theory of computation → Logic and verification
Keywords
  • Linear recurrence sequences
  • Divergence
  • Algebraic numbers
  • Positivity

Metrics

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

Related Versions

References

  1. S. Akshay, Timos Antonopoulos, Joël Ouaknine, and James Worrell. Reachability problems for Markov chains. Inf. Process. Lett., 115(2):155-158, 2015. Google Scholar
  2. Alan Baker and Gisbert Wüstholz. Logarithmic forms and group varieties. J. reine angew. Math, 442(19-62):3, 1993. Google Scholar
  3. W. J. Baumol. Economic Dynamics. An Introduction. Macmillan, 1970. Google Scholar
  4. Jacek Bochnak, Michel Coste, and Marie-Françoise Roy. Real algebraic geometry, volume 36. Springer Science &Business Media, 2013. Google Scholar
  5. Mark Braverman. Termination of integer linear programs. In Computer Aided Verification, 18th International Conference, CAV 2006, Seattle, WA, USA, August 17-20, 2006, Proceedings, pages 372-385, 2006. Google Scholar
  6. John W.S. Cassels. An Introduction to Diophantine Approximation. Cambridge University Press, 1965. Google Scholar
  7. Henri Cohen. A course in computational algebraic number theory, volume 138. Springer Science &Business Media, 2013. Google Scholar
  8. Thomas W Cusick and Mary E Flahive. The Markoff and Lagrange spectra. Number 30 in Mathematical Surveys and Monographs. American Mathematical Soc., 1989. Google Scholar
  9. Graham Everest, Alfred J. van der Poorten, Igor E. Shparlinski, and Thomas Ward. Recurrence Sequences, volume 104 of Mathematical surveys and monographs. American Mathematical Society, 2003. Google Scholar
  10. J.-H. Evertse. On sums of S-units and linear recurrences. Compositio Math., 53(2):225-244, 1984. Google Scholar
  11. David W Masser. Linear relations on algebraic groups. New Advances in Transcendence Theory, pages 248-262, 1988. Google Scholar
  12. M. Mignotte. A note on linear recursive sequences. J. Austral. Math. Soc., 20(2):242-244, 1975. Google Scholar
  13. Ivan Morton Niven. Diophantine approximations. Courier Corporation, 2008. Google Scholar
  14. 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. Google Scholar
  15. Joël Ouaknine and James Worrell. Positivity problems for low-order linear recurrence sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 366-379, 2014. Google Scholar
  16. 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. Google Scholar
  17. Joël Ouaknine and James Worrell. On linear recurrence sequences and loop termination. SIGLOG News, 2(2):4-13, 2015. Google Scholar
  18. James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part i: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of symbolic computation, 13(3):255-299, 1992. Google Scholar
  19. T. N. Shorey and C. L. Stewart. On the Diophantine equation ax^2t + bx^ty + cy² = d and pure powers in recurrence sequences. Math. Scand., 52(1):24-36, 1983. Google Scholar
  20. Alfred Tarski. A decision method for elementary algebra and geometry. Bulletin of the American Mathematical Society, 59, 1951. Google Scholar
  21. A. J. van der Poorten and H. P. Schlickewei. Additive relations in fields. J. Austral. Math. Soc. Ser. A, 51(1):154-170, 1991. Google Scholar
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