5 papers
Greedy Vector Balancing
Wojciech CzerwiÅski, Daniel Dadush, Ekin Ergen +3
In online vector balancing, vectors arrive one by one from a given set and the goal is to assign signs in an online manner so as to m…
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 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 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 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…