9 papers
Monadic Presburger Predicates have Robust Population Protocols
Philipp Czerner, Javier Esparza, Vincent Fischer +3
Population protocols are a model of distributed computation in which a collection of indistinguishable finite-state agents interact randomly in pairs to decide a predicate of their…
Reachability in VASS Extended with Integer Counters
Clotilde Bizière, Wojciech Czerwiński, Roland Guttenberg +5
We consider a variant of VASS extended with integer counters, denoted VASS+Z. These are automata equipped with N and Z counters; the N-counters are required to remain nonnegative a…
Exploring VASS Parameterised by Geometric Dimension
Wojciech Czerwiński, Roland Guttenberg, Łukasz Orlikowski +2
The geometric dimension of a Vector Addition System with States (VASS) is the dimension of the vector space generated by cycles in the VASS; this parameter refines the standard…
PVASS Reachability is Decidable
Roland Guttenberg, Eren Keskin, Roland Meyer
Reachability in pushdown vector addition systems with states (PVASS) is among the longest standing open problems in Theoretical Computer Science. We show that the problem is decida…
Reachability and Related Problems in Vector Addition Systems with Nested Zero Tests
Roland Guttenberg, Wojciech Czerwiński, Sławomir Lasota
Vector addition systems with states (VASS), also known as Petri nets, are a popular model of concurrent systems. Many problems from many areas reduce to the reachability problem fo…
The Black Ninjas and the Sniper: On Robustness of Population Protocols
Benno Lossin, Philipp Czerner, Javier Esparza +2
Population protocols are a model of distributed computation in which an arbitrary number of indistinguishable finite-state agents interact in pairs to decide some property of their…