David Purser

Highlights Conference 2025 Conference Abstract

Resolving Nondeterminism by Chance

• David Purser

Highlights Conference 2024 Conference Abstract

Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata

• David Purser

We study the determinisation and unambiguisation problems of weighted automata over the field of rationals: Given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton? Recent results by Bell and Smertnig show that the problem is decidable, however they do not provide any complexity bounds. We show that both problems are in PSPACE for polynomially-ambiguous weighted automata. Joint work with Ismaël Jecker and Filip Mazowiecki.

Highlights Conference 2023 Conference Abstract

The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)

• David Purser

We show that the big-O problem for max-plus automata, i. e. weighted automata over the semiring (N ∪ {-∞}, max, +), is decidable and PSPACE-complete. The big-O (or affine domination) problem asks whether, given two max-plus automata computing functions f and g, there exists a constant c such that f ≤ cg + c. This is a relaxation of the containment problem asking whether f ≤ g, which is undecidable. Our decidability result uses Simon's forest factorisation theorem, and relies on detecting specific elements, that we call witnesses, in a finite semigroup closed under two special operations: stabilisation and flattening. Joint work with Laure Daviaud. Contributed talk given by David Purser

MFCS Conference 2022 Conference Paper

Skolem Meets Schanuel

• Yuri Bilu
• Florian Luca
• Joris Nieuwveld
• Joël Ouaknine
• David Purser
• James Worrell 0001

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 corresponding computational question, the Skolem Problem, asks to determine whether a given linear recurrence sequence has a zero term. Although the Skolem-Mahler-Lech Theorem is almost 90 years old, decidability of the Skolem Problem remains open. The main contribution of this paper is an algorithm to solve the Skolem Problem for simple linear recurrence sequences (those with simple characteristic roots). Whenever the algorithm terminates, it produces a stand-alone certificate that its output is correct - a set of zeros together with a collection of witnesses that no further zeros exist. We give a proof that the algorithm always terminates assuming two classical number-theoretic conjectures: the Skolem Conjecture (also known as the Exponential Local-Global Principle) and the p-adic Schanuel Conjecture. Preliminary experiments with an implementation of this algorithm within the tool Skolem point to the practical applicability of this method.

Highlights Conference 2022 Conference Abstract

The Boundedness and Zero Isolation Problems for Weighted Automata over Nonnegative Rationals

• David Purser

We consider linear cost-register automata (equivalent to weighted automata) over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems of boundedness and zero isolation ask whether there is a sequence of words that converge to infinity and to zero, respectively. We aim to settle the decidability status for both problems. In the general model both problems are undecidable so we focus on restrictions to the model. In the case of copyless linear restriction we show that the boundedness problem is decidable. As for the zero isolation problem we show undecidability already for copyless CRA---note copyless CRA are not necessarily linear but are a subclass of linear CRA (non-copyless). For decidability, we need to further restrict the class. We obtain a model, where zero isolation becomes equivalent to universal coverability of orthant vector addition systems (OVAS), a new model in the VAS family interesting on its own. In standard VAS runs are considered only in the positive orthant, while in OVAS every orthant has its own set of vectors that can be applied in that orthant. Assuming Schanuel’s conjecture is true, we prove decidability of universal coverability for three-dimensional OVAS, which implies decidability of zero isolation in a model with at most three independent registers. On the other hand the OVAS coverability problem is undecidable. Joint work with Wojciech Czerwiński, Engel Lefaucheux, Filip Mazowiecki, and Markus Whiteland.

Highlights Conference 2021 Conference Abstract

Porous invariants

• David Purser

We introduce the notion of porous invariants for multipath (or branching/nondeterministic) affine loops over the integers; that is, invariants defined using Presburger arithmetic/semi-linear sets and subclasses. These invariants are not necessarily convex, and can in fact contain infinitely many ‘holes’. Nevertheless, we show that in many cases such invariants can be automatically synthesised, and moreover can be used to settle (non-)reachability questions for various interesting classes of affine loops and target sets. Joint work with Engel Lefaucheux, Joël Ouaknine, and James Worrell

Highlights Conference 2018 Conference Abstract

Bisimilarity Distances for Approximate Differential Privacy

• David Purser

ABSTRACT. Differential privacy is a widely studied notion of privacy for various models of computation. Technically, it is based on measuring differences between generated probability distributions. We study epsilon, delta-differential privacy in the setting of Labelled Markov Chains. While the exact differences relevant to epsilon, delta-differential privacy are not computable in this framework, we propose a computable bisimilarity distance that yields a sound technique for measuring delta, the parameter that quantifies deviation from pure differential privacy. We show that the distance is always rational, the associated threshold problem is in NP, and the distance can be computed exactly with polynomially many calls to an NP oracle.