Document Open Access Logo

Involved VASS Zoo (Invited Talk)

Author Wojciech Czerwiński

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2022.5.pdf
  • Filesize: 0.58 MB
  • 13 pages

Document Identifiers

Author Details

Wojciech Czerwiński
  • University of Warsaw, Poland

Funding

  • Czerwiński, Wojciech: Supported by the ERC grant INFSYS, agreement no. 950398.

Cite AsGet BibTex

Wojciech Czerwiński. Involved VASS Zoo (Invited Talk). In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CONCUR.2022.5

Abstract

We briefly describe recent advances on understanding the complexity of the reachability problem for vector addition systems (or equivalently for vector addition systems with states - VASSes). We present a zoo of a few involved VASS examples, which illustrate various aspects of hardness of VASSes and various techniques of proving lower complexity bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel computing models
Keywords
  • vector addition systems
  • reachability problem
  • low dimensions
  • examples

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase, and Pierre McKenzie. Reachability in two-dimensional vector addition systems with states is PSpace-complete. In Proceedings of LICS 2015, pages 32-43, 2015. Google Scholar
  2. Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jérôme Leroux, and Filip Mazowiecki. The reachability problem for Petri nets is not elementary. In Proceedings of STOC 2019, pages 24-33. ACM, 2019. Google Scholar
  3. Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jérôme Leroux, and Filip Mazowiecki. Reachability in fixed dimension vector addition systems with states. In Proceedings of CONCUR 2020, pages 48:1-48:21, 2020. Google Scholar
  4. Wojciech Czerwinski and Lukasz Orlikowski. Reachability in vector addition systems is Ackermann-complete. In Proceedings of FOCS 2021, pages 1229-1240, 2021. Google Scholar
  5. Wojciech Czerwinski and Lukasz Orlikowski. Lower bounds for the reachability problem in fixed dimensional vasses. CoRR, abs/2203.04243, 2022. Google Scholar
  6. Matthias Englert, Ranko Lazic, and Patrick Totzke. Reachability in two-dimensional unary vector addition systems with states is NL-complete. In Proceedings of LICS 2016, pages 477-484, 2016. Google Scholar
  7. Diego Figueira, Santiago Figueira, Sylvain Schmitz, and Philippe Schnoebelen. Ackermannian and Primitive-Recursive Bounds with Dickson’s Lemma. In Proceedings of LICS 2011, pages 269-278, 2011. Google Scholar
  8. Christoph Haase, Stephan Kreutzer, Joël Ouaknine, and James Worrell. Reachability in succinct and parametric one-counter automata. In Proceedings of CONCUR 2009, pages 369-383, 2009. Google Scholar
  9. John E. Hopcroft and Jean-Jacques Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theor. Comput. Sci., 8:135-159, 1979. Google Scholar
  10. S. Rao Kosaraju. Decidability of reachability in vector addition systems (preliminary version). In Proceedings of STOC 1982, pages 267-281, 1982. Google Scholar
  11. Jean-Luc Lambert. A structure to decide reachability in Petri nets. Theor. Comput. Sci., 99(1):79-104, 1992. Google Scholar
  12. Slawomir Lasota. Improved Ackermannian Lower Bound for the Petri Nets Reachability Problem. In Proceedings of STACS 2022, volume 219 of LIPIcs, pages 46:1-46:15, 2022. Google Scholar
  13. Jérôme Leroux. The reachability problem for petri nets is not primitive recursive. In Proceedings of FOCS 2021, pages 1241-1252, 2021. Google Scholar
  14. Jérôme Leroux. The reachability problem for petri nets is not primitive recursive. CoRR, abs/2104.12695, 2021. Google Scholar
  15. Jérôme Leroux and Sylvain Schmitz. Demystifying reachability in vector addition systems. In Proceedings of LICS 2015, pages 56-67, 2015. Google Scholar
  16. Jérôme Leroux and Sylvain Schmitz. Reachability in vector addition systems is primitive-recursive in fixed dimension. In Proceedings of LICS 2019, pages 1-13. IEEE, 2019. Google Scholar
  17. Richard J. Lipton. The reachability problem requires exponential space. Technical report, Yale University, 1976. Google Scholar
  18. Ernst W. Mayr. An algorithm for the general Petri net reachability problem. In Proceedings of STOC 1981, pages 238-246, 1981. Google Scholar
  19. Charles Rackoff. The covering and boundedness problems for vector addition systems. Theor. Comput. Sci., 6:223-231, 1978. Google Scholar
  20. Sylvain Schmitz. Complexity hierarchies beyond elementary. ACM Trans. Comput. Theory, 8(1):3:1-3:36, 2016. Google Scholar
  21. Richard Zurawski and MengChu Zhou. Petri nets and industrial applications: A tutorial. IEEE Trans. Ind. Electron., 41(6):567-583, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact