2026-08-07T18:21:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20803 2024-08-29T05:40:58Z ddc:004 open_access

Bi-Reachability in Petri Nets with Data Kamiński, Łukasz Lasota, Sławomir Petri nets Petri nets with data reachability bi-reachability reversible reachability mutual reachability orbit-finite sets 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Łukasz Kamiński and Sławomir Lasota 2024 Is Part Of LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2024.31 urn:nbn:de:0030-drops-208038 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode