4 papers
Languages of Boundedly-Ambiguous Vector Addition Systems with States
Wojciech Czerwiński, Łukasz Orlikowski
The aim of this paper is to deliver broad understanding of a class of languages of boundedly-ambiguous VASS, that is k-ambiguous VASS for some natural k. These are languages of Vec…
Reachability in 3-VASS is Elementary
Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota +1
The reachability problem in 3-dimensional vector addition systems with states (3-VASS) is known to be PSpace-hard, and to belong to Tower. We significantly narrow down the complexi…
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…
Reachability in One-Dimensional Pushdown Vector Addition Systems is Decidable
Clotilde Bizière, Wojciech Czerwiński
We consider the model of one-dimensional Pushdown Vector Addition Systems (1-PVAS), a fundamental computational model simulating both recursive and concurrent behaviours. Our main…