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.
Proceedings of CONCUR 18, LIPIcs 118, 2018. 25 pages.
PDF
© 2018 Shaull Almagor, Brynmor Chapman, Mehran Hosseini,
Joël Ouaknine, and James Worrell.