Positivity problems for low-order linear recurrence sequences
From MaRDI portal
Abstract: We consider two decision problems for linear recurrence sequences (LRS) over the integers, namely the Positivity Problem (are all terms of a given LRS positive?) and the Ultimate Positivity Problem} (are all but finitely many terms of a given LRS positive?). We show decidability of both problems for LRS of order 5 or less, with complexity in the Counting Hierarchy for Positivity, and in polynomial time for Ultimate Positivity. Moreover, we show by way of hardness that extending the decidability of either problem to LRS of order 6 would entail major breakthroughs in analytic number theory, more precisely in the field of Diophantine approximation of transcendental numbers.
Recommendations
- On the positivity problem for simple linear recurrence sequences
- Ultimate positivity is decidable for simple 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
(72)- The complexity of synchronizing Markov decision processes
- Exact optimal values of step-size coefficients for boundedness of linear multistep methods
- Unbounded-time safety verification of guarded LTI models with inputs by abstract acceleration
- On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
- An extension of holonomic sequences: C^2-finite sequences
- On eventual non-negativity and positivity for the weighted sum of powers of matrices
- A comparison of algorithms for proving positivity of linearly recurrent sequences
- Algebraic model checking for discrete linear dynamical systems
- Recurrence relations, succession rules and the positivity problem
- Positivity of second order linear recurrent sequences
- When can we detect that a P-finite sequence is positive?
- Difference Equation Theory Meets Mathematical Finance
- Positivity of linear transformations of mean-starshaped sequences
- Continuous-time orbit problems are decidable in polynomial-time
- Reachability problems for Markov chains
- Decision problems for linear recurrence sequences
- scientific article; zbMATH DE number 6154366 (Why is no real title available?)
- Effective divergence analysis for linear recurrence sequences
- Undecidable cases of model checking probabilistic temporal-epistemic logic (extended abstract)
- Sequence positivity through numeric analytic continuation: uniqueness of the Canham model for biomembranes
- Ultimate periodicity problem for linear numeration systems
- scientific article; zbMATH DE number 7559471 (Why is no real title available?)
- The big-O problem for labelled Markov chains and weighted automata
- On Reachability Problems for Low-Dimensional Matrix Semigroups
- Termination of linear loops over the integers
- On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
- The big-O problem
- Complexity of Restricted Variants of Skolem and Related Problems
- On Petri nets with hierarchical special arcs
- Decision problems for linear recurrences involving arbitrary real numbers
- On the positivity problem for simple linear recurrence sequences
- Ultimate positivity is decidable for simple linear recurrence sequences
- Point lattices and oscillating recurrence sequences†
- On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
- Termination of linear loops under commutative updates
- What's decidable about discrete linear dynamical systems?
- scientific article; zbMATH DE number 7788988 (Why is no real title available?)
- scientific article; zbMATH DE number 7724240 (Why is no real title available?)
- Computing error bounds for asymptotic expansions of regular P-recursive sequences
- Model checking linear dynamical systems under floating-point rounding
- MDPs as distribution transformers: affine invariant synthesis for safety objectives
- Clustering in the Lazard method for cylindrical algebraic decomposition
- Positivity certificates for \(P\)-recursive sequences
- Hypergeometric-type sequences
- Skolem and positivity completeness of ergodic Markov chains
- On robustness for the Skolem, positivity and ultimate positivity problems
- Positivity-hardness results on Markov decision processes
- On the complexity of robust eventual inequality testing for C-finite functions
- Computing the density of the positivity set for linear recurrence sequences
- The monadic theory of toric words
- On C^2-finite sequences
- Holonomic techniques, periods, and decision problems (invited talk)
- Linear dynamical systems with weight functions
- On Skolem-hardness and saturation points in Markov decision processes
- The threshold problem for hypergeometric sequences with quadratic parameters
- Positivity proofs for linear recurrences through contracted cones
- Nonnegativity problems for matrix semigroups
- Robust positivity problems for linear recurrence sequences: the frontiers of decidability for explicitly given neighbourhoods
- Positive moments forever: undecidable and decidable cases
- Linear dynamical systems with continuous weight functions
- Convex language semantics for nondeterministic probabilistic automata
- A faster-than relation for semi-Markov decision processes
- Polynomial loops: beyond termination
- Stochastic processes with expected stopping time
- Decision problems for second-order holonomic recurrences
- Positivity proofs for linear recurrences with several dominant eigenvalues
- Deciding robust instances of an escape problem for dynamical systems in Euclidean space
- On expansions of monadic second-order logic with dynamical predicates
- On piecewise affine reachability with Bellman operators
- Resolving nondeterminism by chance
- Analyzing ultimate positivity for solvable systems
- Positivity of third order linear recurrence sequences
This page was built for publication: Positivity problems for low-order linear recurrence sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5383986)
