2026-07-22T07:03:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9580 2024-03-06T10:44:46Z ddc:004 open_access

Effective Divergence Analysis for Linear Recurrence Sequences Almagor, Shaull Chapman, Brynmor Hosseini, Mehran Ouaknine, Joël Worrell, James Linear recurrence sequences Divergence Algebraic numbers Positivity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shaull Almagor and Brynmor Chapman and Mehran Hosseini and Joël Ouaknine and James Worrell 2018 Is Part Of LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2018.42 urn:nbn:de:0030-drops-95802 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.42 eng https://creativecommons.org/licenses/by/3.0/legalcode