Replay certificates and residual memory
Replay fan-out
A completed computation can depend on one old input cell while the prefix still has to preserve many cells for different possible futures. The gap is exponential: unit replay slices can coexist with distinct residual behaviors at one cut. Cut-response factorization and a sharp readable-cone theorem then measure how much of that future family a fixed scaffold can distinguish within a finite horizon. A final theorem shows why cardinality alone cannot turn that bound into a separation from every scaffold.
FPRD-D41 · continuation-exposed replay
One completed slice is not the future family
Fix continuations . The replay profile of a prefix is
Each coordinate has its own completed replay support. Its size measures pointwise replay width. The unionmeasures how many old coordinates the selected futures can expose. These are different resources.
Selector lemma
Coordinate queries force distinct residuals
Suppose prefixes are indexed by every , and continuation returns the selected bit:
The residual of , restricted to these tests, is exactly . Distinct vectors therefore have distinct residuals. Any exact deterministic one-pass recognizer needs at least configurations at the cut, or at least bits. This remains true when each selected completion queries only one old cell.
FPRD-T151 · exact separation
The middle bit gives unit slices and exponential fan-out
Let contain the nonempty binary words whose symbol at position is one. Once the completed length is known, membership queries exactly one input cell.
For , set and. Then
The continuations expose independently variable old cells one at a time. Their response profiles realize all bit vectors, even though every completed run has replay width one.
FPRD-D42 · cut-response dimension
Every cut is a one-way communication problem
Let be a finite family of pasts, a finite family of possible continuations, and the required answer. The complete response row of a past is
A deterministic cut summary is a message from the past to a decoder that later receives . Its answer must be for every pair. The cut-response dimension is. For a language, take . With every continuation present, row equality is exactly equality of right residuals.
FPRD-T152 · exact factorization theorem
Distinct response rows are exactly the retained information
The minimum number of exact deterministic summary states is precisely the number of distinct response rows:
Indeed, two pasts assigned the same summary must give the same answer to every continuation, so they must have equal rows. In the other direction, the row itself is a sufficient summary. This is the exact deterministic one-way communication cost of the cut.
Consequently, if every presentation at resource bound has at most distinguishable cut states, exact realization requires. This is a model-independent transfer rule. The hard model-specific task is proving a capacity bound that survives re-encoding and persistent sharing.
Linear observers give an exact dimension
Let pasts be and continuations be linear tests. If the observer family spans an dimensional subspace, then its response map has exactly rows. Its kernel is the annihilator of that span, so this is immediate from rank-nullity.
Coordinate tests each read one source bit but jointly force n retained bits. One full-parity test reads all n source bits but forces only one retained bit. Pointwise replay support and stationary answer information can diverge in both directions.
The cut theorem controls retained information only. The unary selector below shows that n retained bits may still be maintained with constant scaffold degree and constant descriptor distance. Thus pointwise support, cut information, and local update cost are three separate FPRD coordinates.
The exact checker covers 74,954 Boolean response matrices, rejects 4,066,394 undersized encodings, and verifies all 65,812 binary linear-observer families in dimensions one through four. False replacements of observer rank by largest support or by raw observer count fail 32,028 and 64,365 times respectively.
- Self-contained theorem and proof
- Exact finite checker
- Recorded checker output
- Yao: communication complexity
- Jain and Nayak: Index in streaming lower bounds
The factorization and linear-rank facts are classical. FPRD uses them here as a bridge theorem and makes no novelty claim for those ingredients. No external or specialist review is recorded.
FPRD-T153 · finite-horizon scaffold capacity
A finite continuation can read only a bounded old cone
Fix a Loff–Moreira–Reis scaffolding automaton of degree, distance, working alphabet, and finite control. For a continuation horizon, define
The current control state and the radius- unfolded neighbourhood of the cut top determine the answer to every continuation of length at most . Physical sharing outside that unfolded view cannot affect those answers.
Why each new symbol adds k − 1
A radius- view of a fresh top first follows one fresh port. That port names an endpoint at old distance at most . Only further old edges remain, so old radius suffices. Induction over the continuation gives the displayed formula.
The radius is uniformly sharp. A degree-one chain can hide one decisive bit exactly at depth; two prefixes then agree through radius but a length-h continuation separates them.
An explicit response-row ceiling
Put . If counts abstract unfolded views, including the missing view, then
FPRD-T152 now gives a concrete capacity bound: every horizon-h cut of this automaton has at most distinct response rows. Its response dimension is at most.
The checker exhausts 13,056 old scaffolds and 4,253,184 one-step extensions in degree-one and degree-two domains. It also verifies 24 sharpness witnesses covering distances one through four and horizons one through six.
- Complete proof and scope
- Exact structural checker
- Recorded checker output
- Loff, Moreira, and Reis: scaffolding automata and PEGs
This bounds one fixed automaton parameter tuple. It does not yet separate a language from every scaffolding automaton or PEG, since another machine may use larger fixed degree, distance, alphabet, or finite control. No literature-priority or external-review claim is made.
FPRD-T154 · lower-bound method barrier
Raw row counting cannot outrun every scaffold envelope
Let the input alphabet have size. Even before choosing a language, the number of Boolean response rows on all continuations of length at most is at most
Compare this with one fixed T153 parameter choice for the alphabet:
Here and for positive h. The recurrencegives . Meanwhile, including the unary case. Therefore
No language can make raw finite-horizon Boolean row count exceed every numerical upper envelope furnished by T153. A parameter-uniform lower bound must preserve structure inside the response tables, not only count their rows.
The distinction that keeps the theorem honest
counts abstract unfolded views and may count views unreachable by any particular machine. The inequality does not construct a recognizer, show that the chosen tuple realizes every response table, or imply that every language is a PEG language. It closes only the direct proof pattern “semantic row lower bound exceeds the generic T153 bound for all parameter tuples.”
The next invariant must retain advance compatibility between cuts, coherence between horizons, algebraic restrictions, reachable-view constraints, or the local cost of transporting and merging persistent demands. Those structures can be scarce even when the ambient set of abstract views is enormous.
The audit checks the exact recurrence on 40 cases and the symbolic exponent inequality on 16,448 cases. Lower-degree and fixed-radius mutants fail 8,510 and 16,383 times respectively.
The counting ingredients are elementary. This is a methodological theorem about the T152-T153 route, with no literature-priority or external-review claim.
Stationary-presentation boundary
The missing resource is transport, not final slice size
FPRD-T150 proves that one execution's backward slice is stable. FPRD-T151 shows why that cannot by itself yield a stationary compressor, FPRD-T152 gives the exact retained information at a chosen cut, and FPRD-T153 bounds that information for every fixed scaffold parameter tuple and finite horizon. FPRD-T154 now shows that the generic bound cannot become a parameter-uniform separation through row cardinality alone.
The cut theorem measures the middle quantity exactly. The third is model-dependent. FPRD-T153 supplies one such bound for the native scaffold model, but only after its degree, distance, alphabet, control size, and future horizon are fixed. The remaining target is a structured response invariant that constrains how rows evolve, compose, and become reachable, or a comparable structural capacity theorem for projected frontier presentations in FPRD-C02.
Positive calibration · persistent stacks
Exponential residuals, bounded local updates
A related selector language makes the positive boundary explicit:
Each zero after the separator steps back one stored bit. Any two distinct length-n data prefixes are separated by some suffix, so they give distinct residuals. Nevertheless, a degree-two, distance-two scaffold recognizes S with exactly one new node per symbol.
Port 0 of the current root names the stack head. Port 1 of each data node names its tail. Reading a data bit creates a node labelled by that bit with ports (SELF, old path 0). Reading # creates a wrapper with ports (old path 0, MISSING). Each query zero creates a wrapper with ports (old path 01, MISSING). Finite control rejects malformed input; in query mode it accepts exactly when the selected head is labelled one. Missing paths stay missing.
Induction proves the invariant: before #, the head chain is the data word in reverse order; after j query zeros, its first j cells have been dropped, or it is empty. All old nodes remain unchanged. Both the next head and its acceptance label are visible within distance two of the old root.
Bounded update cost is not bounded total memory. The archive still retains the data bits. With the input shape fixed, a final answer depends on one payload bit, but that is not the complete dependency trace of constructing and navigating the scaffold.
A restricted general rule
If a finite query controller inspects and drops at most c stack cells per symbol, its bounded decision tree becomes one transition table. Dropping j cells installs the fixed descriptor. Degree two and distance suffice, with one fresh wrapper per symbol. Here c is fixed; the query phase permits no pushes, unbounded scans, or arbitrary address jumps.
This is standard persistent-stack machinery, not a new recognizability result. It isolates the timing constraint: selecting depth j is paid for by j query symbols. It does not give constant-time access to a binary-encoded address, recognize the middle-bit language above, or maintain an arbitrary projected pushdown frontier.
The literal row interpreter agrees with an independent language oracle on all 88,573 words through length ten, checks 18,434 selector queries, and detects 502 failures when the pop descriptor is deliberately replaced by a stay descriptor.
Evidence and comparison
Exact finite audit; classical lower-bound shape
The executable audit enumerates every bit vector through. It checks 8,190 prefixes, 90,114 unit-slice selections, 90,114 single-bit mutations, and 8,190 distinct response profiles.
The proof is an elementary Myhill–Nerode argument with the same shape as deterministic one-way INDEX: a prefix stores a vector and the continuation selects a coordinate. This page makes no novelty claim for that lower-bound pattern or for the middle-bit language. Its contribution is the FPRD calibration: bounded completed-slice width is not the stationary-memory invariant.