Ultimate positivity is decidable for simple linear recurrence sequences
From MaRDI portal
Abstract: We consider the decidability and complexity of the Ultimate Positivity Problem, which asks whether all but finitely many terms of a given rational linear recurrence sequence (LRS) are positive. Using lower bounds in Diophantine approximation concerning sums of S-units, we show that for simple LRS (those whose characteristic polynomial has no repeated roots) the Ultimate Positivity Problem is decidable in polynomial space. If we restrict to simple LRS of a fixed order then we obtain a polynomial-time decision procedure. As a complexity lower bound we show that Ultimate Positivity for simple LRS is hard for co, i.e., the class of problems solvable in the universal theory of the reals (which lies between coNP and PSPACE).
Recommendations
- On the positivity problem for simple linear recurrence sequences
- Positivity problems for low-order linear recurrence sequences
- Positivity of third order linear recurrence sequences
- Decision problems for linear recurrence sequences
- The positivity problem for fourth order linear recurrence sequences is decidable
Cited in
(37)- Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
- Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
- Robust positivity problems for linear recurrence sequences: the frontiers of decidability for explicitly given neighbourhoods
- On the positivity problem for simple linear recurrence sequences
- Skolem and positivity completeness of ergodic Markov chains
- Positivity problems for low-order linear recurrence sequences
- On eventual non-negativity and positivity for the weighted sum of powers of matrices
- On robustness for the Skolem, positivity and ultimate positivity problems
- Algebraic model checking for discrete linear dynamical systems
- Positivity-hardness results on Markov decision processes
- Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
- Near-polynomial recursive sequences with algorithmically unsolvable problems
- scientific article; zbMATH DE number 7559115 (Why is no real title available?)
- On the Identity Problem for the Special Linear Group and the Heisenberg Group.
- Exact optimal values of step-size coefficients for boundedness of linear multistep methods
- Polynomial loops: beyond termination
- Model checking QCTL plus on quantum Markov chains
- A robust class of linear recurrence sequences
- scientific article; zbMATH DE number 7378586 (Why is no real title available?)
- Quantitative growth of linear recurrences
- Holonomic techniques, periods, and decision problems (invited talk)
- Linear dynamical systems with weight functions
- On the complexity of robust eventual inequality testing for C-finite functions
- Pumping lemmas for weighted automata
- Analyzing ultimate positivity for solvable systems
- scientific article; zbMATH DE number 7407788 (Why is no real title available?)
- scientific article; zbMATH DE number 7407779 (Why is no real title available?)
- First-order orbit queries
- Complexity of Restricted Variants of Skolem and Related Problems
- The threshold problem for hypergeometric sequences with quadratic parameters
- scientific article; zbMATH DE number 7559425 (Why is no real title available?)
- Beyond the Existential Theory of the Reals
- Computing the density of the positivity set for linear recurrence sequences
- scientific article; zbMATH DE number 7204378 (Why is no real title available?)
- What's decidable about discrete linear dynamical systems?
- On the Monniaux problem in abstract interpretation
- scientific article; zbMATH DE number 7788988 (Why is no real title available?)
This page was built for publication: Ultimate positivity is decidable for simple linear recurrence sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167849)
