DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2024.31

Bi-Reachability in Petri Nets with Data

Authors: Łukasz Kamiński and Sławomir Lasota

Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)

Abstract

We investigate Petri nets with data, an extension of plain Petri nets where tokens carry values from an infinite data domain, and executability of transitions is conditioned by equalities between data values. We provide a decision procedure for the bi-reachability problem: given a Petri net and its two configurations, we ask if each of the configurations is reachable from the other. This pushes forward the decidability borderline, as the bi-reachability problem subsumes the coverability problem (which is known to be decidable) and is subsumed by the reachability problem (whose decidability status is unknown).

Cite as

Łukasz Kamiński and Sławomir Lasota. Bi-Reachability in Petri Nets with Data. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kaminski_et_al:LIPIcs.CONCUR.2024.31,
  author =	{Kami\'{n}ski, {\L}ukasz and Lasota, S{\l}awomir},
  title =	{{Bi-Reachability in Petri Nets with Data}},
  booktitle =	{35th International Conference on Concurrency Theory (CONCUR 2024)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-339-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{311},
  editor =	{Majumdar, Rupak and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.31},
  URN =		{urn:nbn:de:0030-drops-208038},
  doi =		{10.4230/LIPIcs.CONCUR.2024.31},
  annote =	{Keywords: Petri nets, Petri nets with data, reachability, bi-reachability, reversible reachability, mutual reachability, orbit-finite sets}
}

Search Results

Documents authored by Kamiński, Łukasz

Bi-Reachability in Petri Nets with Data

Abstract

Cite as

Thanks for your feedback!

Could not send message