2 citations · 3 across the 7 of their papers we have counts for
13 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…
The Expressive Power of Uniform Population Protocols with Logarithmic Space
Philipp Czerner, Vincent Fischer, Roland Guttenberg
Population protocols are a model of computation in which indistinguishable mobile agents interact in pairs to decide a property of their initial configuration. Originally introduce…
Verification of Population Protocols with Unordered Data
Steffen van Bergerem, Roland Guttenberg, Sandra Kiefer +3
Population protocols are a well-studied model of distributed computation in which a group of anonymous finite-state agents communicates via pairwise interactions. Together they dec…
Flattability of Priority Vector Addition Systems
Roland Guttenberg
Vector addition systems (VAS), also known as Petri nets, are a popular model of concurrent systems. Many problems from many areas reduce to the reachability problem for VAS, which…
Verification of Population Protocols with Unordered Data is undecidable
Roland Guttenberg
We consider the new extension of population protocols with unordered data and show that the corresponding well-specification problem and therefore also other verification problems…
Geometry of Reachability sets of Vector Addition Systems
Roland Guttenberg, Mikhail Raskin, Javier Esparza
Vector Addition Systems (VAS), aka Petri nets, are a popular model of concurrency. The reachability set of a VAS is the set of configurations reachable from the initial configurati…
Fast and Succinct Population Protocols for Presburger Arithmetic
Philipp Czerner, Roland Guttenberg, Martin Helfrich +1
In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate as input, outputs a leaderless population protocol…
Decision Power of Weak Asynchronous Models of Distributed Computing
Philipp Czerner, Roland Guttenberg, Martin Helfrich +1
Esparza and Reiter have recently conducted a systematic comparative study of models of distributed computing consisting of a network of identical finite-state automata that coopera…