Replay fan-out: small completed slices can hide large residual memory

1. Continuation-exposed replay profiles

Let $L\subseteq\Sigma^*$, let $P\subseteq\Sigma^*$ be a family of prefixes of one fixed length, and let $Z=(z_1,\ldots,z_t)$ be a finite family of continuations. The continuation-exposed replay profile of $p\in P$ on $Z$ is

$$\rho_Z(p)=\bigl(\mathbf 1_L(pz_1),\ldots,\mathbf 1_L(pz_t)\bigr).$$

Each coordinate is one completed computation. If that computation has a replay support, write $R(p,z_j)$ for its source portion inside the prefix. Two different quantities must be kept separate:

• the pointwise replay width $\max_j|R(p,z_j)|$; and
• the future-exposed union $E_Z(p)=\bigcup_jR(p,z_j)$.

The first asks how much old information one completed execution used. The second asks how many different old coordinates the selected futures can expose.

2. Selector lemma

Lemma. Suppose that for every bit vector $b=(b_1,\ldots,b_t)\in\{0,1\}^t$ there is a prefix $p_b$, and for each $j$ there is a continuation $z_j$, such that

$$\mathbf 1_L(p_bz_j)=b_j.$$

Then the $2^t$ prefixes $p_b$ have pairwise distinct left residuals. Every exact deterministic one-pass recognizer therefore has at least $2^t$ distinct configurations after these prefixes and needs at least $t$ bits at that cut.

This remains true if every completed run $p_bz_j$ has a replay support of one source cell.

Proof

The restriction of the residual $p_b^{-1}L$ to the test family $Z$ is exactly the vector $b$. Distinct bit vectors disagree on some coordinate $j$, so $z_j$ separates the corresponding residuals. If two prefixes reached the same deterministic configuration, every common continuation would have the same answer, contradicting that separator. A set of $2^t$ configurations requires at least $t$ bits. The last statement is compatible with the argument because it concerns the support of each coordinate separately, not the number of coordinates selected across all continuations. $\square$

3. A unit-slice language with exponential residual fan-out

For every nonempty binary word $w=w_1\cdots w_n$, let

$$\operatorname{mid}(w)=w_{\lceil n/2\rceil}, \qquad M=\{w\in\{0,1\}^+:\operatorname{mid}(w)=1\}.$$

Treat the length of the completed word as public shape data. Its membership observer computes $\lceil n/2\rceil$ and queries that one input cell. Thus every completed word has source replay width one.

Fix $r\ge1$. For $b=b_1\cdots b_r\in\{0,1\}^r$, define

$$p_b=0^r b_1\cdots b_r, \qquad z_j=0^{2j-1}\quad(1\le j\le r).$$

The total length of $p_bz_j$ is $2r+2j-1$, so

$$\left\lceil\frac{|p_bz_j|}{2}\right\rceil=r+j.$$

Consequently

$$\mathbf 1_M(p_bz_j)=b_j.$$

The selector lemma now gives $2^r$ pairwise distinct residuals among prefixes of length $2r$. Each selected completion reads one old cell, but the $r$ continuations expose $r$ independently variable old cells and recover the entire bit vector.

Theorem (replay fan-out separation). The middle-bit language $M$ has the following properties for every $r\ge1$:

1. every completed nonempty input has source replay width one;
2. a family of $r$ continuations exposes $r$ distinct old coordinates from suitable length-$2r$ prefixes;
3. those continuations realize all $2^r$ response profiles; and
4. every exact deterministic one-pass recognizer has at least $2^r$ configurations after some length-$2r$ cut.

In particular, a uniform bound on completed replay-slice cardinality does not bound residual diversity or deterministic one-pass memory.

4. What the separation means for FPRD

FPRD-T150 is pointwise: after one execution is fixed, its backward slice is a stable replay certificate. The theorem above shows why that fact alone cannot produce a stationary compressor. A prefix must be ready for a family of possible future observers. Even when each future selects one old coordinate, the family can select many coordinates and recover an exponentially large response table.

This separates three resources:

$$\text{completed slice width} \quad\neq\quad \text{future-exposed coordinate count} \quad\neq\quad \text{cost of transporting addresses stationarily}.$$

The first two are exactly separated here. The third remains model-dependent. A persistent pointer system can sometimes transport an unbounded address family with a bounded number of roots and local updates, so this theorem is not a lower bound against scaffolding automata or PEGs and does not resolve FPRD-C02.

The next useful invariant must therefore describe the transport orbit of replay roots: which old coordinates future continuations may select, how those coordinates are named, and whether their names can be updated by one bounded stationary rule.

The persistent-selector calibration now gives an explicit positive case: unary query suffixes select any stored payload bit using a degree-two, distance-two scaffold with one allocation per letter. Exponential residual diversity coexists with bounded update cost, not bounded total storage. The one-bit payload certificate is distinct from the full scaffold dependency trace. This is a different language from the middle-bit example and uses standard persistent-stack machinery.

5. Comparator boundary

The residual separation is an elementary Myhill–Nerode argument. Its shape is also the deterministic one-way INDEX lower bound: a prefix stores a bit vector and a continuation selects a coordinate. INDEX reductions are standard in streaming lower bounds; Jain and Nayak use an augmented Index problem to prove streaming space bounds for parenthesis recognition.

This note makes no novelty claim for the selector argument or the middle-bit language. Its role is narrower: it connects those established lower-bound patterns to execution-specific replay slices and identifies exactly why bounded slice width is insufficient for the stationary-presentation problem.

• Michael O. Rabin and Dana Scott, “Finite Automata and Their Decision Problems,” IBM Journal of Research and Development 3(2), 1959. https://doi.org/10.1147/rd.32.0114
• Rahul Jain and Ashwin Nayak, “The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited,” 2010. https://arxiv.org/abs/1004.3165