# Bi-reachability in Petri nets with data

arXiv: https://arxiv.org/abs/2405.16176 · HTML: https://mlsanity.com/paper/2405.16176/

## Key facts

- Cited by 1 papers 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 (most cited first, 7 of 7)

- [Automata theory in nominal sets](https://mlsanity.com/paper/1402.0897/) (2014)
- [Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension](https://mlsanity.com/paper/1903.08575/) (2019)
- [Demystifying Reachability in Vector Addition Systems](https://mlsanity.com/paper/1503.00745/) (2015)
- [Equivariant ideals of polynomials](https://mlsanity.com/paper/2402.17604/) (2024)
- [Vector Addition System Reversible Reachability Problem](https://mlsanity.com/paper/1301.4874/) (2013)
- [VASS reachability in three steps](https://mlsanity.com/paper/1812.11966/) (2018)
- [Orbit-finite linear programming](https://mlsanity.com/paper/2302.00802/) (2023)

## Built on by (most cited first, 1 of 1)

- [Reachability in Symmetric VASS](https://mlsanity.com/paper/2506.23578/) (2025)

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