FPRD LabShare an approach

← Claims

Theorem

FPRD-T42

Canonical future-row recognizer

Exact statement

For every fixed-length Boolean recognition function, the recognizer whose grade-ii states are the distinct exact future rows RT,iR_{T,i} is correct, reachable, and reduced. Every reachable correct strict layered recognizer has a unique grade-preserving surjection onto it. Consequently rf(T,i)r_f(T,i) is the exact minimum state count at every grade, max⁡irf(T,i)\max_i r_f(T,i) is the exact minimum width, and every reachable reduced realization is uniquely grade-isomorphic to the canonical one.

StatusProved and internally audited
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

Future rows are the semantic information that a deterministic recognizer must retain at a fixed grade. The theorem turns this observation into a universal factorization and exact state minimum.

Definitions

  • The canonical transition is [u]→a[ua][u]\xrightarrow{a}[ua]; equality of future rows makes this representative-independent.
  • A reachable recognizer is reduced when distinct states in the same grade induce distinct future rows.

Hypotheses and scope

  • The fixed-length recognition-cut datum is as in FPRD-D22.
  • The competing recognizers are deterministic, strict, grade-preserving, correct on every word of length T, and restricted to their reachable states.

Proof or evidence

Map every reachable state to the future row of any prefix reaching it. If two prefixes reach the same state, determinism and correctness force agreement on every remaining suffix, so the map is well-defined. Every row has a prefix witness, making the map surjective; reachability makes it unique. The canonical recognizer attains equality at every grade. Reducedness makes the forced map injective and therefore an isomorphism.

Canonical cut classes and layered width →

Verification notes

The proof and the new independent audit agree on adjacent transitions, reachability, reducedness, forced factor maps, boundary cuts, and constant functions. The audit enumerates all 65,814 Boolean functions on binary words through length four and 3,905,720 representative-independence checks. Bryant's reduced ordered diagrams remain context, not a substitute for this strict-grade proof.

Limitations

  • The theorem concerns a fixed total length and symbol order.
  • Skip-permitting branching programs are a different category and may merge nonadjacent grades.
  • Uniqueness is asserted only after unreachable states are removed.

Open work

Map the theorem explicitly to fixed-order branching programs and distinguish strict layered width from skip-permitting diagram size.

Notes

This is a strict fixed-order general-alphabet layered theorem. Bryant's skip-permitting binary function graphs are a classical comparator, not a substitute proof for the per-grade result.