Complexity of Restricted Variants of Skolem and Related Problems
DOI10.4230/LIPICS.MFCS.2017.78zbMATH Open1441.68061OpenAlexW2773589705MaRDI QIDQ5111295FDOQ5111295
Nikhil Vyas, S. Akshay, Nikhil Balaji
Publication date: 26 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8130/pdf/LIPIcs-MFCS-2017-78.pdf/
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 (5)
- 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
- A robust class of linear recurrence sequences
- Title not available (Why is that?)
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 👍 👎
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)
