On the Complexity of the Skolem Problem at Low Orders
Abstract
The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) \(\langle u_n \rangle_{n=0}^\infty\) over the integers has a zero term, that is, whether there exists \(n\) such that \(u_n = 0\). Decidability of the problem is open in general, with the most notable positive result being a decision procedure for LRS of order at most \(4\).
Fields of Study & Subjects
Limits and Structures in Graph Theory
semigroups and automata theory
Advanced Graph Theory Research
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 5255–5269
- Publication date
- 1 January 2026
- Language
- EN