License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.128
URN: urn:nbn:de:0030-drops-141973
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14197/
Go to the corresponding LIPIcs Volume Portal

Czerwiński, Wojciech ; Lasota, Sławomir ; Orlikowski, Łukasz

Improved Lower Bounds for Reachability in Vector Addition Systems

pdf-format:
LIPIcs-ICALP-2021-128.pdf (0.8 MB)

Abstract

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 stagnation, a non-elementary lower bound has been shown recently: the problem needs a tower of exponentials of time or space, where the height of tower is linear in the input size. We improve on this lower bound, by increasing the height of tower from linear to exponential. As a side-effect, we obtain better lower bounds for vector addition systems of fixed dimension.

BibTeX - Entry

@InProceedings{czerwinski_et_al:LIPIcs.ICALP.2021.128,
  author =	{Czerwi\'{n}ski, Wojciech and Lasota, S{\l}awomir and Orlikowski, {\L}ukasz},
  title =	{{Improved Lower Bounds for Reachability in Vector Addition Systems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{128:1--128:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14197},
  URN =		{urn:nbn:de:0030-drops-141973},
  doi =		{10.4230/LIPIcs.ICALP.2021.128},
  annote =	{Keywords: Petri nets, vector addition systems, reachability problem}
}

Keywords: Petri nets, vector addition systems, reachability problem
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI