A persistent selector with exponential residual fan-out

This is a positive calibration for FPRD-T151, not a new language separation or a solution of FPRD-C02. It is an explicit instance of the Lab’s persistent-stack compilation machinery.

Language and observations

Over the alphabet {0,1,#}, define

$$S=\{x\#0^j:x\in\{0,1\}^+,\ 0\le j<|x|,\ x_{|x|-j}=1\}.$$

The query suffix asks for the bit j places back from the last data bit. For fixed data length n and fixed suffix #0^j, membership depends on exactly one of the n payload bits. This is a one-bit payload certificate with shape held fixed, not a one-cell replay trace of the whole scaffold execution. Syntax validation, pointer construction, and pointer traversal are separate work.

For each n, all 2^n data prefixes have distinct residuals: if x and y differ at position i, the common suffix #0^(n-i) separates them. Thus every exact deterministic one-pass implementation has at least 2^n configurations after the data prefix. The lower bound counts the entire configuration, including persistent storage.

An explicit degree-two, distance-two scaffold

Each input letter appends one immutable node with ports 0 and 1. The initial node has two missing ports. Finite control records one of DATA, QUERY, or DEAD, together with the current acceptance bit. The label alphabet is {B0,B1,W}; B0 and B1 label data nodes, W labels wrappers.

From the current top, port 0 names the current stack head. From a data node, port 1 names the next older data node. A descriptor is either SELF, MISSING, or a fixed port word evaluated from the old top.

Paths that encounter a missing port evaluate to MISSING. QUERY with an empty stack stays empty under further zeros and always rejects. Epsilon and all inputs without # reject.

Only old paths 0 and 01 are inspected or installed. The rule is stationary: it does not mention input length, stack height, or the query index. Its neighborhood has depth two, its degree is two, and it allocates exactly one node per input symbol.

Invariant and proof

After a binary prefix x, the root’s port 0 names a chain labelled reverse(x), with port 1 as its tail link. This holds initially for the empty chain. A DATA step creates a new labelled head whose tail is the old head, preserving the invariant without changing any old node.

Reading # preserves the chain and enters QUERY. After j zeros, the chain has dropped min(j,|x|) heads. Each zero sets the new root’s port 0 to the tail of the old head, which is exactly old path 01. Induction proves the assertion, including exhaustion. The new acceptance bit is true precisely when this chain is nonempty and starts with B1, which is the defining condition of S. The DEAD transitions reject every malformed input.

This proves simultaneous exponential residual diversity and bounded local update cost. It does not compress n arbitrary data bits into bounded total memory: the archived nodes retain them.

General bounded-navigation rule

The same representation supports a fixed finite controller which, during a query phase, inspects and drops at most c old stack cells per input symbol, with c fixed independently of input length. Branch choices may depend on the labels observed along that bounded walk. If j cells are dropped, the next root uses descriptor 0 followed by j copies of port 1; j=0 is the path 0. Any final top-label read is at distance at most c+1. The entire bounded decision tree is one finite transition table.

Consequently this query model has degree two, observation distance max(1,c+1), and one new wrapper per query symbol. A preceding build phase uses the DATA push rule above. This statement permits no query-phase pushes, unbounded scans, or arbitrary root jumps. It is a sufficient construction for this restricted model, not a characterization of all stationary presentations.

What this resolves, and what remains

The example rules out treating either residual count or the number of potentially selected payload positions as a lower bound on scaffold update resources by itself. A large family of future demands can be served by one current root when the input supplies time to walk to the chosen address. Here selecting depth j costs j query symbols and j local updates. It says nothing comparable about a binary-encoded address delivered in only logarithmically many symbols.

The middle-bit language in T151 is a different example; this construction does not recognize it. In that language the desired input position moves forward as input arrives, so a backward stack cursor alone does not establish its bounded-update realization.

For FPRD-C02, the remaining problem is to find a representation and stationary update rule for the whole projected frontier, including branching and merging demands. A single backwards stack cursor supplies a calibration, not that frontier representation.

The scaffold model and its PEG connection are due to Loff, Moreira, and Reis, The computational power of parsing expression grammars. The present construction uses standard persistent linked stacks; no novelty is claimed. By the scaffold-to-PEG direction, it is the reversal of S that transfers immediately to PEG. No reversal-closure assumption is used.