12 papers
Conjectural Decidability of the Skolem Problem
Florian Luca, Joël Ouaknine, James Worrell
The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term. This problem, whose decidability has been open for many decades, aris…
On the -adic Skolem Problem
Piotr Bacik, Joël Ouaknine, David Purser +1
The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) has a zero term. Showing decidability of this problem is equivalent to giving an effective pro…
On the Decidability of Monadic Theories of Arithmetic Predicates
Valérie Berthé, Toghrul Karimov, Joris Nieuwveld +3
We investigate the decidability of the monadic second-order (MSO) theory of the structure , for various unary predicates $P_1,\ldots,P…
Termination Analysis of Linear-Constraint Programs
Amir M. Ben-Amram, Samir Genaim, Joël Ouaknine +1
This paper provides an overview of techniques in termination analysis for programs with numerical variables and transitions defined by linear constraints. This subarea of program a…
On the Complexity of the Skolem Problem at Low Orders
Piotr Bacik, Joël Ouaknine, James Worrell
The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) over the integers has a zero term, that is, whether there e…
Multiple Reachability in Linear Dynamical Systems
Toghrul Karimov, Edon Kelmendi, Joël Ouaknine +1
We consider reachability decision problems for linear dynamical systems: Given a linear map on , together with source and target sets, determine whether there is a p…