Complexity of Restricted Variants of Skolem and Related Problems

DOI10.4230/LIPICS.MFCS.2017.78MaRDI QIDQ5111295zbMATH OpenOpenAlexFDO

Authors S. Akshay, Nikhil Balaji, Nikhil Vyas

Publication date 26 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/8130/pdf/LIPIcs-MFCS-2017-78.pdf/

zbMATH Keywords

linear recurrence sequencesNP-completenessprogram terminationSkolem problem

Mathematics Subject Classification ID

Recurrences (11B37) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Decision problems for linear recurrence sequences
• The continuous Skolem-Pisot problem
• Effective results on the Skolem problem for linear recurrence sequences
• Positivity problems for low-order linear recurrence sequences
• On the Skolem problem and some related questions for parametric families of linear recurrence sequences

Cites work

• A problem that is easier to solve on the unit-cost algebraic RAM
• Approximate verification of the symbolic dynamics of Markov chains
• Computational Complexity
• Computer Aided Verification
• Decision problems for linear recurrence sequences
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 1973372 (Why is no real title available?)
• On regularity of unary probabilistic automata
• On termination of integer linear loops
• On the positivity problem for simple linear recurrence sequences
• On the Skolem problem for continuous linear dynamical systems
• On the termination of integer loops
• Post correspondence problem for short words
• Reachability problems for Markov chains
• Reducibility among combinatorial problems
• Termination of Integer Linear Programs
• The Generalized Vandermonde Matrix
• The polyhedron-hitting problem
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• Ultimate positivity is decidable for simple linear recurrence sequences

Cited in

(12)

• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• On eventual non-negativity and positivity for the weighted sum of powers of matrices
• A robust class of linear recurrence sequences
• scientific article; zbMATH DE number 1735935 (Why is no real title available?)
• On the Skolem problem for continuous linear dynamical systems
• Decision problems for linear recurrence sequences
• Decision problems for linear recurrences involving arbitrary real numbers
• Skolem and positivity completeness of ergodic Markov chains
• On robustness for the Skolem, positivity and ultimate positivity problems
• On the Skolem problem and the Skolem conjecture
• Polynomial loops: beyond termination
• The continuous Skolem-Pisot problem

This page was built for publication: Complexity of Restricted Variants of Skolem and Related Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111295)