FPRD LabShare an approach

← Claims

Theorem

FPRD-T39

Exact midpoint memory for generalized Dyck languages

Exact statement

For generalized Dyck words of length 2N2N with kk bracket types and ℓ\ell neutral symbols, let Ak,ℓ(N)=∑h=0NkhA_{k,\ell}(N)=\sum_{h=0}^N k^h when ℓ≥1\ell\ge1, and Ak,0(N)=∑j=0⌊N/2⌋kN−2jA_{k,0}(N)=\sum_{j=0}^{\lfloor N/2\rfloor}k^{N-2j}. The exact number of reachable midpoint future rows is ρk,ℓ(0)=1\rho_{k,\ell}(0)=1 and ρk,ℓ(N)=Ak,ℓ(N)+1\rho_{k,\ell}(N)=A_{k,\ell}(N)+1 for N≥1N\ge1. Hence every exact deterministic one-pass recognizer needs at least ⌈log⁡2ρk,ℓ(N)⌉\lceil\log_2\rho_{k,\ell}(N)\rceil midpoint bits; the standard typed-stack recognizer matches this asymptotically.

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

Context

At the midpoint, a valid prefix is summarized by its unmatched opener stack. Neutrals permit every height through N; without neutrals, only heights congruent to N modulo two occur. Irreparable failure supplies one additional all-zero row when N is positive.

Definitions

  • A generalized Dyck word uses typed openers and matching closers; neutral symbols leave the stack unchanged.
  • Ak,ℓ(N)A_{k,\ell}(N) counts the live typed stacks reachable after exactly NN symbols.
  • ρk,ℓ(N)\rho_{k,\ell}(N) adds the reachable failure row when N≥1N\ge1.

Hypotheses and scope

  • Inputs have total length exactly 2N and the memory cut is after N symbols.
  • Recognition is exact, deterministic, and one pass.
  • The lower bound counts complete mutable configurations, including an absorbing failure configuration.

Proof or evidence

Every reachable live stack has a canonical length-N prefix and a padded canonical completion. The resulting prefix-versus-completion submatrix is the identity, so distinct stacks have distinct future rows. A malformed prefix supplies one zero row for N at least one. Two distinct rows cannot share a deterministic midpoint configuration. A typed stack plus failure flag gives the matching asymptotic upper bound.

Common-midpoint rows and deterministic configurations →

Verification notes

The proof and closure audit separately check neutral padding, parity without neutrals, the zero-row correction, exact ceiling rounding, ranks over several fields, and a one-pass simulator. The new independent interpreter checks 11,358,802 literal midpoint row cells across 24 hostile parameter cases.

Limitations

  • The classical deterministic linear lower bound for multiple bracket types is not claimed as new.
  • The explicit stack encoding is asymptotically, not bit-for-bit, optimal in every parameter regime.
  • The theorem is for exact fixed-length midpoint recognition, not arbitrary streaming promises.

Open work

Add a small table for one bracket type, two bracket types, and the neutral-free parity restriction.

Notes

The deterministic two-type linear lower bound is classical. M23 proves the exact residual-shadow, Hankel, and midpoint-width bridge, including the logarithmic one-type and neutral/parity cases, exact ceiling rounding, and a readout-correct typed-stack realization.