FPRD LabShare an approach

← Claims

Theorem

FPRD-T41

Canonical layered recognizers for controlled Dyck languages

Exact statement

For any finite controlled-Dyck system, total length TT, and cut mm, the reachable exact-length future signatures are exactly the distinct rows of the controlled Hankel cut. They form the unique reachable reduced deterministic layered recognizer up to layerwise isomorphism and have minimum cardinality at every layer. At T=2NT=2N and m=Nm=N, the minimum midpoint width is the number of distinct rows of the square controlled Hankel window.

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

Context

Controlled Dyck languages add finite regular control to typed stack behavior. At a fixed remaining length, each reachable stack-controller configuration is observed only through its Boolean responses to suffixes of that length.

Definitions

  • A finite controlled-Dyck system combines a finite controller with visible push, matching-pop, and neutral actions plus an absorbing failure state.
  • The exact signature Ej(x)=(o(x⋅v))∣v∣=jE_j(x)=(o(x\cdot v))_{|v|=j} records the acceptance response of state xx to every suffix of length jj.
  • All reached configurations with an all-false exact signature belong to one zero row, whether they are failed or merely unable to accept at the selected remaining length.

Hypotheses and scope

  • The controller, stack alphabet, and visible action partition are finite.
  • The total length, cut, and deterministic layered category are fixed.
  • Only reachable states are compared, and reducedness means distinct exact future signatures.

Proof or evidence

A literal Hankel row for prefix u is coordinatewise equal to the exact signature of the state reached by u. Appending one symbol shifts to the next exact signature, producing a canonical layered recognizer. Any competing reachable state maps to the signature of a prefix reaching it; determinism and correctness make this well-defined, prefix witnesses make it surjective, and reducedness makes it an isomorphism.

Exact rows and universal layered minimum →

Verification notes

The M24 proof and closure audit check global reachability, failure and live-zero merging, exact versus bounded signatures, nonsquare cuts, midpoint specialization, controller-state redundancy, and named mutation cases. The later M25 proof independently recovers the same fixed-length universal property in the general cut category.

Limitations

  • The theorem does not assert global minimum control-state size for arbitrary visibly pushdown automata.
  • Exact-length signatures are different from the at-most-length bounded signatures used in the inverse-limit construction.
  • No external or specialist review is documented.

Open work

Provide one nonsquare cut example and keep fixed-length layered minimality separate from global visibly-pushdown state minimization.

Notes

Exact-length signatures are separate from T40's at-most-length signatures. The theorem is fixed-total-length layered minimization, not unrestricted VPA state minimization.