mlsanityData to 14 Oct 2026

Bi-reachability in Petri nets with data

arXiv 2405.16176 ↗First posted 25 May 2024cs.CL cs.FL cs.LOcited by 1

Not on the map. Why?

Abstract (arXiv)

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).

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 7 of its 29 references that are in the map. First posted on arXiv 25 May 2024.

Builds on

7 of 29 references.

References · 7

  1. 2014Automata theory in nominal setscited by 5
  2. 2019Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimensioncited by 5
  3. 2015Demystifying Reachability in Vector Addition Systemscited by 4
  4. 2024Equivariant ideals of polynomialscited by 2
  5. 2013Vector Addition System Reversible Reachability Problemcited by 1
  6. 2018VASS reachability in three stepscited by 1
  7. 2023Orbit-finite linear programmingcited by 1

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Reachability in Symmetric VASScited by 1