Fixed-length recognition and information

Exact recognition cuts and deterministic memory

At a fixed position in a fixed-length input, two prefixes are interchangeable precisely when every legal remaining suffix gives the same answer. These future rows form the canonical layered recognizer, the smallest exact one-way message alphabet, and the exact information that any deterministic one-pass recognizer must preserve at that cut.

FPRD-D22 · definition

A cut records exact remaining behavior

Fix a finite nonempty alphabet $\Sigma$ , a total length $T\ge0$ , and a Boolean function $f:\Sigma^T\to\{0,1\}$ . At cut $i$ , the future row of a prefix $u\in\Sigma^i$ is

r_u:\Sigma^{T-i}\to\{0,1\},\qquad r_u(v)=f(uv).

Let $R_{T,i}$ be the set of distinct rows. Only reachable states, messages, and machine configurations count. Competing layered recognizers must be deterministic, exact, and strict: every input symbol advances from grade $i$ to grade $i+1$ .

This is a per-length model. It does not silently claim one uniform streaming machine for all lengths, nor does it identify row count with field or Boolean matrix rank.

FPRD-T42 · theorem

Future rows are the unique reduced layered states

Theorem. The grade- $i$ states $R_{T,i}$ , with transition $[u]\xrightarrow{a}[ua]$ , form a correct reachable reduced recognizer. Every other reachable correct strict layered recognizer has a unique grade-preserving surjection onto it.

Proof. Equal rows remain equal after one common letter, so the displayed transition is representative-independent. Map a competing reachable state to the future row of any prefix reaching it. If two such prefixes reach the same state, determinism and correctness force identical answers on every legal remaining suffix, so the map is well-defined. Prefix witnesses make it surjective; reachability makes it unique. Reducedness makes it injective. ∎

Therefore the exact minimum state count at grade $i$ is $|R_{T,i}|$ , the exact minimum strict width is $\max_i|R_{T,i}|$ , and every reachable reduced realization is uniquely grade-isomorphic to the canonical one. Bryant's reduced ordered decision diagrams are a useful comparison, but their skip-permitting category is not substituted for this adjacent-grade theorem.

FPRD-T43 · theorem

The same quotient is the exact one-way information

At cut $(T,m)$ , a deterministic one-way protocol has an encoder $e:\Sigma^m\to M$ and decoder $d:M\times\Sigma^{T-m}\to\{0,1\}$ with $d(e(u),v)=f(uv)$ .

Exact cost. The minimum reachable message alphabet has size $|R_{T,m}|$ . With fixed-length binary messages, the exact cost is $\lceil\log_2|R_{T,m}|\rceil$ . Every exact deterministic one-pass recognizer has at least that many complete reachable configurations and mutable bits at the cut; the per-length canonical row recognizer attains the bound.

The lower bound is semantic. Two prefixes sharing a message or a complete machine configuration must give the same answer on every legal suffix, hence must share a row. “Complete” includes every input-dependent datum capable of affecting later transitions or output. Yao's one-way communication model supplies the classical framework; the forced row factor and exact fixed-length rounding are the deductions proved here.

FPRD-T39 · Dyck instance

A saved typed stack gives the midpoint rows

For generalized Dyck words of total length $2N$ with $k\ge1$ bracket types and $\ell\ge0$ neutral letters, the live midpoint rows are indexed by reachable unmatched-opener stacks. When $\ell\ge1$ , every height through $N$ occurs; without neutrals only heights congruent to $N\bmod2$ occur.

\rho_{k,\ell}(0)=1,\qquad \rho_{k,\ell}(N)=1+ \begin{cases} \sum_{h=0}^{N}k^h,&\ell\ge1,\\ \sum_{j=0}^{\lfloor N/2\rfloor}k^{N-2j},&\ell=0, \end{cases} \quad(N\ge1).

The added one is the reachable all-zero failure row. Each live stack has a canonical closing suffix that accepts from it and not from another selected stack, so these rows are distinct. The exact deterministic midpoint-memory lower bound is the ceiling logarithm of $\rho_{k,\ell}(N)$ .

FPRD-T41 · controlled-Dyck instance

Finite control changes reachability, not the cut theorem

Add a finite total controller to the typed-stack dynamics. At a fixed cut, each start-reachable stack/controller configuration is observed through its exact remaining-length signature. Equal signatures form exactly the distinct controlled Hankel rows and therefore the unique reachable reduced strict layered recognizer.

Failure and a live configuration that cannot accept within the remaining length merge when both signatures are all false. This is a fixed-length semantic quotient, not a claim about globally minimum visibly pushdown automata.

Hostile and limiting cases

At $T=0$ , there is one empty-prefix row and the exact cost is zero bits.
The initial cut always has one reachable row. The final cut has one or two rows, according to whether both Boolean outputs occur.
A constant slice has one row and zero message bits.
An all-zero row counts as a state, message, and machine configuration even though it contributes no field-rank dimension.
Randomized, approximate, interactive, amortized, and variable-length protocols are outside the theorem.

Sources and evidence

Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers C-35(8), 1986, pp. 677–691. This is the reduced ordered-diagram comparison, not a proof of the strict-grade universal property.
Andrew C.-C. Yao, Some Complexity Questions Related to Distributive Computing (Preliminary Report), Proceedings of STOC 1979, pp. 209–213. This supplies the classical deterministic communication framework.
Tim Roughgarden, Communication Complexity (for Algorithm Designers), Foundations and Trends in Theoretical Computer Science11(3–4), 2016, pp. 217–404. This is background for row-based deterministic one-way lower bounds.

The exact factorization, uniqueness, and Dyck instantiations are FPRD deductions with no external-review or novelty claim. The independent checker enumerates 65,814 Boolean functions, 22,369,894 prefix pairs, 3,905,720 canonical transitions, and 11,358,802 literal Dyck row cells.