License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.5
URN: urn:nbn:de:0030-drops-109493
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10949/
Go to the corresponding LIPIcs Volume Portal

Leroux, Jérôme

Petri Net Reachability Problem (Invited Talk)

pdf-format:
LIPIcs-MFCS-2019-5.pdf (0.2 MB)

Abstract

Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes. The central algorithmic problem for Petri nets is reachability: whether from the given initial configuration there exists a sequence of valid execution steps that reaches the given final configuration. The complexity of the problem has remained unsettled since the 1960s, and it is one of the most prominent open questions in the theory of verification. In this presentation, we overview decidability and complexity results over the last fifty years about the Petri net reachability problem.

BibTeX - Entry

@InProceedings{leroux:LIPIcs:2019:10949,
  author =	{J{\'e}r{\^o}me Leroux},
  title =	{{Petri Net Reachability Problem (Invited Talk)}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{5:1--5:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10949},
  URN =		{urn:nbn:de:0030-drops-109493},
  doi =		{10.4230/LIPIcs.MFCS.2019.5},
  annote =	{Keywords: Petri net, Reachability problem, Formal verification, Concurrency}
}

Keywords: Petri net, Reachability problem, Formal verification, Concurrency
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

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