FPRD LabShare an approach

← Claims

Theorem · external algebraic reduction

FPRD-RDV-T01

Reversible reachability is equivariant ideal membership

Exact statement

For an orbit-finitely presented reversible system with transition binomials vi−uiv_i-u_i, source and target monomials s,ts,t satisfy s↔∗ts\leftrightarrow^* t exactly when t−st-s belongs to the ideal generated by all embedding-renamed vi−uiv_i-u_i. On a homogeneous data structure, the same finite renamings can be realized by automorphisms.

StatusPublished theorem; reduction reconstructed in the FPRD exposition
External reviewThe underlying theorem appeared at LICS 2024. No external review of the FPRD exposition is recorded.

Context

A rewrite step contributes a monomial context times a renamed transition difference; a path therefore telescopes to an ideal certificate.

Hypotheses and scope

  • Rules are symmetric.
  • Every rule and marking has finite support.
  • The source action is by embeddings; homogeneity is needed only when that action is replaced by automorphisms.

Proof or evidence

The forward direction is telescoping. The reverse direction is the binomial-ideal theorem for symmetric commutative rewriting, lifted equivariantly by the cited source.

Exact ideal-membership reduction →

Verification notes

The embedding action was restored in the theorem statement. An independent Buchberger implementation agreed with reversible reachability on 7,120 finite queries; the directed hostile control fails exactly as expected.

Limitations

  • Ideal membership becomes an algorithm only when a suitable basis can be computed.

Open work

Seek a specialist check of the automorphism-versus-embedding presentation used on the page.