1 citations · 1 across the 4 of their papers we have counts for
6 papers · 1 filter
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…
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…
On the Decidability of Presburger Arithmetic Expanded with Powers
Toghrul Karimov, Florian Luca, Joris Nieuwveld +2
We prove that for any integers , the existential fragment of the first-order theory of the structure $\langle \mathbb{Z}; 0,1,<, +, α^{\mathbb{N}}, β^{\mathbb{N}}\rang…
The Monadic Theory of Toric Words
Valérie Berthé, Toghrul Karimov, Joël Ouaknine +2
For which unary predicates is the MSO theory of the structure decidable? We survey the state of the art, leadin…
The 2-Dimensional Constraint Loop Problem is Decidable
Quentin Guilmant, Engel Lefaucheux, Joël Ouaknine +1
A linear constraint loop is specified by a system of linear inequalities that define the relation between the values of the program variables before and after a single execution of…