Zobrazeno 1 - 5
of 5
pro vyhledávání: '"Orlikowski, Łukasz"'
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). Up to now, the problem is known to be $\mathcal{F}_k$-hard for VASS of
Externí odkaz:
http://arxiv.org/abs/2310.09008
We study the complexity of the reachability problem for Vector Addition Systems with States (VASSes) in fixed dimensions. We provide four lower bounds improving the currently known state-of-the-art: 1) \np-hardness for unary flat $4$-VASSes (VASSes i
Externí odkaz:
http://arxiv.org/abs/2203.04243
Vector Addition Systems and equivalent Petri nets are a well established models of concurrency. The central algorithmic problem for Vector Addition Systems with a long research history is the reachability problem asking whether there exists a run fro
Externí odkaz:
http://arxiv.org/abs/2104.13866
Publikováno v:
ICALP
We investigate computational complexity of the reachability problem for vector addition systems (or, equivalently, Petri nets), the central algorithmic problem in verification of concurrent systems. Concerning its complexity, after 40 years of stagna
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::55d0d692d1114fcf8d7d5217ded789b3
https://doi.org/10.4230/lipics.icalp.2021.128
https://doi.org/10.4230/lipics.icalp.2021.128
Publikováno v:
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
LICS '22: 37th Annual (ACM/IEEE) Symposium on Logic in Computer Science
LICS '22: 37th Annual (ACM/IEEE) Symposium on Logic in Computer Science
We study the complexity of the reachability problem for Vector Addition Systems with States (VASSes) in fixed dimensions. We provide four lower bounds improving the currently known state-of-the-art: 1) \np-hardness for unary flat $4$-VASSes (VASSes i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9f4aed06c2b9686adf2a67c518688282