88 citations · 281 across the 25 of their papers we have counts for
28 papers
Invariants for One-Counter Automata with Disequality Tests
Dmitry Chistikov, Jérôme Leroux, Henry Sinclair-Banks +1
We study the reachability problem for one-counter automata in which transitions can carry disequality tests. A disequality test is a guard that prohibits a specified counter value.…
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…
New Algorithms for Combinations of Objectives using Separating Automata
Ashwani Anand, Nathanaël Fijalkow, Aliénor Goubault-Larrecq +2
The notion of separating automata was introduced by Bojanczyk and Czerwinski for understanding the first quasipolynomial time algorithm for parity games. In this paper we show that…
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…