FPRD-RDV-D01 · model

Finite markings and orbit-finite rules

Fix a data domain $\mathcal A$ with carrier $A$ and finitely many places$[d]$. A marking is a finite multiset over $A\times[d]$, equivalently a monomial in variables indexed by those pairs.

A finite list of representative rules generates all their data renamings under embeddings of the data structure. Reversibility means every rule is usable in both directions. That symmetry is essential: polynomial ideals allow generators with either sign and therefore cannot remember the orientation of a directed rewrite system. If the data structure is homogeneous, every isomorphism between finite induced substructures extends to an automorphism, so embeddings and automorphisms generate the same renamed finite rules.

FPRD-RDV-T01 · published theorem

Reachability has an exact ideal certificate

For representative transitions $(u_i,v_i)$, let

A path proves the forward direction by telescoping: a contextual step $gu\leftrightarrow gv$contributes $g(v-u)$. The reverse implication is the Mayr–Meyer binomial-ideal theorem for symmetric commutative rewriting, transferred to the embedding-equivariant setting by Ghosh and Lasota.

FPRD-RDV-T02 · finite-generation theorem

The stated WQO gives a finite global basis

A monomial over $A$ is a finite induced substructure whose elements carry natural-number exponent labels. Under homogeneity, label-increasing embedding is exactly monomial divisibility modulo data renaming.

Theorem 2 of Ghosh–Lasota therefore says that if the domain is also totally ordered, every embedding-equivariant ideal in$K[\mathcal A]$ has a finite equivariant basis for every Noetherian commutative coefficient ring $K$. This applies to the transition ideal.

Existence of a finite basis is not yet an algorithm for finding one, nor does it bound a shortest certificate for a particular query. Decidability also needs computable orbit operations, embedding tests, and a terminating Gröbner construction.

FPRD-RDV-T03 · strengthened theorem

A stronger effective case is decidable

The hypothesis includes three algorithmic ingredients:

• effective oligomorphism and computable orbit operations;
• a compatible computable total order, or an effective reduct of one;
• labelled monomial divisibility is a WQO for every WQO label set.

Under these conditions the authors compute an equivariant Gröbner basis, decide ideal membership, and apply the result to reversible data Petri nets.

FPRD-RDV-B01 · open boundary

The missing labelled-WQO implication

A natural-number-labelled WQO is weaker on its face than the two-coordinate condition used by the core Gröbner construction:

The inspected sources do not establish this implication in the required generality, so the weaker hypothesis set remains open in this record.

Two concrete routes remain: prove the lifting for homogeneous ordered finite-signature structures, or exploit the binomial form of reversible reachability to avoid the full polynomial Gröbner machinery.

FPRD-RDV-X01 · hostile example

The Rado graph does not satisfy the two displayed hypotheses

The pure Rado graph has no distinguished invariant linear-order relation. Adding a generic order does not repair the WQO hypothesis: the age of the ordered random graph contains every finite ordered graph, including an arbitrarily ordered chordless cycle $C_n$ for each$n\ge4$. A chordless cycle has no proper induced subgraph that is a cycle, so these form an infinite antichain.

This agrees with the later paper's stronger hostile result: its infinite-path criterion makes equivariant ideal membership undecidable for the pure Rado-graph action. Dense rational order, by contrast, remains a valid positive example.