1 citations · 2 across the 9 of their papers we have counts for
3 papers · 1 filter
Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
Wojciech Czerwiński, Łukasz Orlikowski
In this work, we extend undecidability of language equivalence for two-dimensional Vector Addition System with States (VASS) accepting by coverability condition. We show that the p…
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…