FPRD LabShare an approach

← Claims

Theorem · exact criterion

FPRD-SH-T03

Exact predecessor criterion for left invariance

Exact statement

A state partition π\pi is left-invariant exactly when initiality is saturated and every pair q,q′q,q' in one block has identical predecessor-block sets {π(r):r→σq}\{\pi(r):r\xrightarrow{\sigma}q\} for every letter σ\sigma.

StatusSelf-contained reformulation of the standard definition
External reviewNo documented external or specialist review of these FPRD results is recorded.

Context

Ordinary state merging controls forward transition existence; left invariance additionally requires the predecessor operation to descend to blocks.

Definitions

  • For a candidate projection π\pi, set Pred⁡σπ(q)={π(r):r→σq}\operatorname{Pred}^{\pi}_{\sigma}(q)=\{\pi(r):r\xrightarrow{\sigma}q\}.

Proof or evidence

Equality of these profiles is exactly right invariance after reversing all transitions, together with saturation of the initial set.

Predecessor criterion →

Verification notes

The criterion is implemented directly in the exhaustive small-automaton checker.

Limitations

  • The criterion decides left invariance of a fixed partition; it does not by itself find a partition.
  • No novelty is claimed for the equivalence with reversed right invariance.

Open work

Combine this criterion with Boolean block equations for larger SAT-checkable quotient certificates.