2 citations · 3 across the 5 of their papers we have counts for
6 papers
Reachability in 3-VAS
Łukasz Kamiński, Sławomir Lasota
We settle the exact complexity of the reachability problem in (stateless) vector addition systems (VAS) in fixed low dimension. In dimensions 2-4 it has only been known to be sandw…
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…
Reachability in Symmetric VASS
Łukasz Kamiński, Sławomir Lasota
We investigate the reachability problem in symmetric vector addition systems with states (VASS), where transitions are invariant under a group of permutations of coordinates. One e…
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…
New Lower Bounds for Reachability in Vector Addition Systems
Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota +2
We investigate the dimension-parametric complexity of the reachability problem in vector addition systems with states (VASS) and its extension with pushdown stack (pushdown VASS).…