7 citations · 21 across the 10 of their papers we have counts for
12 papers
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…
History-deterministic Vector Addition Systems
Sougata Bose, David Purser, Patrick Totzke
We consider history-determinism, a restricted form of non-determinism, for Vector Addition Systems with States (VASS) when used as acceptors to recognise languages of finite words.…
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…
Model Checking Linear Dynamical Systems under Floating-point Rounding
Engel Lefaucheux, Joël Ouaknine, David Purser +1
We consider linear dynamical systems under floating-point rounding. In these systems, a matrix is repeatedly applied to a vector, but the numbers are rounded into floating-point re…
The boundedness and zero isolation problems for weighted automata over nonnegative rationals
Wojciech Czerwiński, Engel Lefaucheux, Filip Mazowiecki +2
We consider linear cost-register automata (equivalent to weighted automata) over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems of…
Skolem Meets Schanuel
Yuri Bilu, Florian Luca, Joris Nieuwveld +3
The celebrated Skolem-Mahler-Lech Theorem states that the set of zeros of a linear recurrence sequence is the union of a finite set and finitely many arithmetic progressions. The c…