88 citations · 281 across the 25 of their papers we have counts for
14 papers · 1 filter
Compiling Petri Net Mutual Reachability in Presburger
Jérôme Leroux
Petri nets are a classical model of concurrency widely used and studied in formal verification with many applications in modeling and analyzing hardware and software, data bases, a…
On the Home-Space Problem for Petri Nets and its Ackermannian Complexity
Petr Jančar, Jérôme Leroux
A set of configurations is a home-space for a set of configurations of aPetri net if every configuration reachable from (any configuration in) can reach (some configura…
State Complexity of Protocols With Leaders
Jérôme Leroux
Population protocols are a model of computation in which an arbitrary number of anonymous finite-memory agents are interacting in order to decide by stable consensus a predicate. I…
The Reachability Problem for Petri Nets is Not Primitive Recursive
Jérôme Leroux
We provide an Ackermannian complexity lower bound for the reachability problem for checking programs, a model equivalent to Petri nets. Moreover in fixed dimension , we show…
Reachability in Two-Dimensional Vector Addition Systems with States: One Test is for Free
Jérôme Leroux, Grégoire Sutre
Vector addition system with states is an ubiquitous model of computation with extensive applications in computer science. The reachability problem for vector addition systems is ce…
Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
Jérôme Leroux, Sylvain Schmitz
The reachability problem in vector addition systems is a central question, not only for the static verification of these systems, but also for many inter-reducible decision problem…