5 papers
On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic
Piotr Bacik, Joris Nieuwveld, Joël Ouaknine +3
We consider expansions of Presburger arithmetic with families of monadic polynomial predicates. (Examples of such predicates are the set of perfect squares, or the set of integers…
On the Subspace Orbit Problem and the Simultaneous Skolem Problem
Piotr Bacik, Anton Varonka
The Orbit Problem asks whether the orbit of a point under a matrix reaches a given target set. When the target is a single point, the problem was shown to be decidable in polynomia…
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…
Completing the picture for the Skolem Problem on order-4 linear recurrence sequences
Piotr Bacik
For almost a century, the decidability of the Skolem Problem - that is, the problem of finding whether a given linear recurrence sequence (LRS) has a zero term - has remained open.…
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…