Effective Divergence Analysis for Linear Recurrence Sequences

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.

Published in CONCUR 2018

Cited by in corpus (3)

• An Effective Framework for Constructing Exponent Lattice Basis of Nonzero Algebraic Numbers
• Cost Analysis of Nondeterministic Probabilistic Programs
• Forecasting with Multiple Seasonality