Complexity of Restricted Variants of Skolem and Related Problems
DOI10.4230/LIPICS.MFCS.2017.78zbMATH Open1441.68061OpenAlexW2773589705MaRDI QIDQ5111295FDOQ5111295
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/
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Recurrences (11B37)
Cites Work
- Computational Complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computer Aided Verification
- On the Positivity Problem for Simple Linear Recurrence Sequences,
- Termination of Integer Linear Programs
- Reducibility among combinatorial problems
- A problem that is easier to solve on the unit-cost algebraic RAM
- The Generalized Vandermonde Matrix
- Reachability problems for Markov chains
- Approximate Verification of the Symbolic Dynamics of Markov Chains
- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- Title not available (Why is that?)
- Decision problems for linear recurrence sequences
- On Termination of Integer Linear Loops
- Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
- Post correspondence problem for short words
- On the termination of integer loops
- The Polyhedron-Hitting Problem
- Title not available (Why is that?)
Cited In (7)
- On eventual non-negativity and positivity for the weighted sum of powers of matrices
- On robustness for the Skolem, positivity and ultimate positivity problems
- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- Decision problems for linear recurrence sequences
- A robust class of linear recurrence sequences
- The continuous Skolem-Pisot problem
- Title not available (Why is that?)
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)
