1 citations · 1 across the 3 of their papers we have counts for
3 papers
A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
Yousef Shakiba, Henry Sinclair-Banks, Georg Zetzsche
In many kinds of infinite-state systems, the coverability problem has significantly lower complexity than the reachability problem. In order to delineate the border of computationa…
The Tractability Border of Reachability in Simple Vector Addition Systems with States
Dmitry Chistikov, Wojciech Czerwiński, Filip Mazowiecki +3
Vector Addition Systems with States (VASS), equivalent to Petri nets, are a well-established model of concurrency. The central algorithmic challenge in VASS is the reachability pro…
Coverability in 2-VASS with One Unary Counter is in NP
Filip Mazowiecki, Henry Sinclair-Banks, Karol Węgrzycki
Coverability in Petri nets finds applications in verification of safety properties of reactive systems. We study coverability in the equivalent model: Vector Addition Systems with…