5 papers · 1 filter
Bridging the Gap Between Plain VASS and Branching VASS
Clotilde Bizière, Jérôme Leroux, Grégoire Sutre
Vectors addition systems with states (VASS), a model equivalent to Petri nets, are finite-state machines with finitely many counters ranging over the natural numbers. The decidable…
Solving the Reachability Problem for Branching Vector Addition Systems via Semilinear Inductive Invariants
Clotilde Bizière, Jérôme Leroux, Grégoire Sutre
In this paper, we solve the reachability problem for branching vector addition systems (BVAS), a long standing open problem. Our approach is based on semilinear inductive invariant…
A Forward-Only Construction of Semilinear Inductive Invariants for VAS
Clotilde Bizière, Jérôme Leroux, Grégoire Sutre
The reachability problem for Vector Addition Systems (VAS) is a central decision problem in the theory of infinite-state systems, first solved by Kosaraju and Mayr in the 1980s. An…
On the Reachability Problem for Two-Dimensional Branching VASS
Clotilde Bizière, Thibault Hilaire, Jérôme Leroux +1
Vectors addition systems with states (VASS), or equivalently Petri nets, are arguably one of the most studied formalisms for the modeling and analysis of concurrent systems. A cent…
Locality Theorems in Semiring Semantics
Clotilde Bizière, Erich Grädel, Matthias Naaf
Semiring semantics of first-order logic generalises classical Boolean semantics by permitting truth values from a commutative semiring, which can model information such as costs or…