We consider the complexity of deciding the truth of first-order existential sentences of linear
arithmetic with divisibility over both the integers and the p-adic numbers. We show that if an …

We study the decidability and complexity of the reachability problem in parametric timed
automata. The problem was introduced 20 years ago by Alur, Henzinger, and Vardi in [1] …

We prove that language equivalence of deterministic one-counter automata is NL-complete.
This improves the superpolynomial time complexity upper bound shown by Valiant and …

Parametric timed automata (PTA) have been introduced by Alur, Henzinger, and Vardi as an
extension of timed automata in which clocks can be compared against parameters. The …

Abstract Two decades ago, Alur, Henzinger, and Vardi introduced the reachability problem
for parametric timed automata. Their main results are that reachability is decidable for timed …

We consider two-player games with reachability objectives played on transition systems of
succinct one-counter machines, that is, machines where the counter is incremented or …

In the past decade, there has been an unprecedented rise in the incorporation of cyber-
physical systems used to perform complex tasks. Verifying these systems is necessary to …

We consider the model-checking problem for freeze LTL on one-counter automata (OCA).
Freeze LTL extends LTL with the freeze quantifier, which allows one to store different …

We study a class of reachability problems in weighted graphs with constraints on the
accumulated weight of paths. The problems we study can equivalently be formulated in the …

Counting abilities in finite automata are traditionally provided by two orthogonal extensions:
adding a single counter that can be tested for zeroness at any point, or adding ℤ-valued …