2 papers
cs.LO2026
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…
cs.FL2025
The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
Laure Daviaud, David Purser, Marie Tcheng
We show that the big-O problem for max-plus automata is decidable and PSPACE-complete. The big-O (or affine domination) problem asks whether, given two max-plus automata computing…