When a stored answer becomes a usable answer

13 October 2026. Dedicated primary-proof review. Construction 78 was the latest native result at this assessment. This review compares two established primary arguments and derives an exact scheduling test; it does not claim a new native recognizer or lower bound.

Subsequent progress: construction 80 supplies growing-delay envelopes and bounded speculative readout. This dated review retains its original scope and evidence. Current research target.

What the comparison resolves

A completed representation of a string need not make that string available to another computation before its deadline. There are two useful ways around this problem. A fixed finite-state consumer can be maintained as a summary while the string is constructed. A growing consumer needs actual access operations, released early enough that meaningful remaining input pays for them.

For example, a transducer can build a word and its reversal in two registers. A fixed automaton’s answer about their concatenation can be maintained without enumerating the final string. But replacing that automaton by an input-built activation dictionary changes the resource question. The dictionary’s state space grows, and its current version changes when sources activate stores. A finite-state composition theorem cannot absorb those costs as a machine constant.

Construction 78 handles growing dictionaries by delaying a learned prefix lookup and paying its replay during a meaningful unchanged suffix. The next test is an input-built suffix transducer with bounded output delay. This review identifies exactly what that extension must charge.

1. Streaming transducers: composition by all-state summaries

Primary source. Rajeev Alur and Pavol Cerny, Expressiveness of streaming string transducers, FSTTCS 2010 author manuscript, 12 pages. The complete manuscript was reacquired and read for this reconstruction.

Model and quantifiers

Section 3 fixes finite input and output alphabets, a finite controller and finitely many string registers. Each input symbol updates the registers simultaneously by concatenating constants and old register values. Copylessness is global across all right-hand sides of one update: an old register occurs at most once in their union. It is not merely a restriction within each expression. The final expression is also copyless, and a partial output function specifies the domain.

The output semantics evaluate the final register expression as a whole string. They do not require that an arbitrary downstream reader has traversed that string by the last input symbol. The paper explicitly distinguishes this finite-alphabet model from its earlier data-string setting, where sequential-composition closure does not carry over.

Why Proposition 1 composes

For each register of the first transducer and each possible start state of the second, the construction maintains the second transducer’s end state and symbolic register substitution over that register’s current string. A substitution is independent of the incoming register valuation: control depends on input symbols, not tests on string-register contents.

Copylessness bounds the number of old-variable occurrences in the substitution. For a second transducer with m registers, at most 2m fresh string pieces plus finite bookkeeping represent the substitution. Concatenating first-stage register values composes the corresponding substitutions. The start-state index matters: the consumer may enter a fragment in different states after a preceding fragment changes. The displayed construction uses m1 times n2 times 2m2 registers, with finite control depending on the two fixed machines. Undefined first-stage output or undefined second-stage output remains undefined.

This review imports Proposition 1’s closure theorem, including its copyless bookkeeping; the summary description above is not a separate implementation proof of the complete construction. In particular, maintaining every possible consumer start state requires the theorem’s global bookkeeping, not merely composing one pair of substitutions in isolation. Its fixed-machine quantifier is essential. An unbounded collection of input-built namespace maps or a growing activation dictionary cannot be installed as that second machine without separately constructing and maintaining its summaries. Proposition 2’s conditional composition is similarly controlled by a fixed regular language, not an arbitrary evolving input-built predicate.

What the equivalent heap and logical models preserve

Section 4’s heap transducer allocates labeled singly linked cells and can modify an old cell’s next pointer through one of finitely many pointer variables. It cannot follow a next pointer during its update computation. Its final output is the whole list reachable from a selected pointer. Thus bounded updates coexist with semantic readout of an arbitrarily long chain. The old-pointer mutation also differs from the Lab’s immutable old-top update contract.

Section 5 explains why the equivalence is stronger than a superficial syntax translation. Two-way excursions are summarized for every state. Determinism permits shared output suffixes when excursions merge, avoiding arbitrary copying. Halting and error cases are tracked, and a second copy anticipates the right end marker. The heap-to-register construction compresses uninterrupted list segments; finitely many live pointers bound the interruptions and leave only a finite heap shape to remember. The register-to-MSO construction records assignment edges, links old-variable occurrences to prior columns, and removes unused nodes and epsilon edges in the final output graph. Those translations preserve the string function, not a charged final query against a changing external dictionary.

The traversal extension and the paper’s merge example are useful guardrails. Once heap traversal is added, more string transformations become possible. Conversely, a fixed number of indivisible register fragments cannot implement arbitrary interleaving of two independent growing input blocks. This does not establish a restriction on native branching scaffolds with paid traversal, and no such transfer is made here.

2. Persistent queues: schedules must pay for dependencies

Primary source. Chris Okasaki, Simple and efficient purely functional queues and deques, JFP 5(4), 583-592, October 1995. The full ten-page paper was reacquired and independently reviewed.

Why total amortized work is insufficient

A two-list queue uses a forward front and a reversed rear. Reversing the rear when the front empties has constant amortized cost along a single linear operation history. Persistence permits repeated operations from the same retained version; each descendant can trigger the same expensive reversal. A potential argument for one path does not automatically pay the entire version tree.

Lazy rotation fuses append and reversal so that output can be demanded incrementally. But a newly forced cell may require forcing a suspended cell of an older rotation. The paper’s intermediate lazy queue bounds the nested dependency depth logarithmically by the shrinking sizes of prior fronts. Laziness alone therefore does not give the final worst-case constant bound.

The explicit schedule is the decisive mechanism

The real-time queue retains a third list S, a suffix of the same memoized front L, as a schedule. It maintains $|R|\le |L|$, and after a completed operation $|S|=|L|-|R|$. An insertion or legal removal reduces the front/rear difference by one, so on entry to the repair function $|S|=|L|-|R|+1$. If S is nonempty, the repair advances it once. Otherwise $|R|=|L|+1$, triggering rotation and resetting S to the new front. Advancing S forces evaluation in advance of actual demand. When the next rotation starts, the required older front has already been evaluated and memoized. Each new rotation step consequently performs bounded work rather than triggering an unbounded chain of older suspensions. Rear tails require only bounded access because they have no nontrivial delayed computation.

The deque construction uses two schedules because rebalancing may affect either end. For a fixed integer $c\ge2$, it maintains $|L|\le c|R|+1$ and $|R|\le c|L|+1$. A violation triggers rebalancing: retain the first $\lfloor(|L|+|R|)/2\rfloor$ cells of the longer list and append its reversed remainder to the shorter list. The two rotation phases distribute dropping and reversing in chunks of c, leaving at most c+1 cells of residual work. Each insertion advances both schedules once; each removal advances both twice. One advance per removal would be insufficient because repeated removals from one side can force a new rotation too soon.

Writing $j=\min(|L|,|R|)$ and $k=\max(|L|,|R|)$, both schedule lengths are at most $\max(2j+2-k,0)$. Resetting schedules after a balanced rotation establishes this invariant. An insertion can lower the bound by at most one and a removal by at most two, exactly matching the advancement rates. Before another imbalance triggers a rotation, the old schedules have therefore emptied. The singleton opposite-side removal case and the convention that the tail of an empty schedule is empty complete the boundary cases. These balance, release and advancement conditions are part of the worst-case proof, not optional implementation details.

The paper distinguishes semantic persistence from evaluation behavior: memoized shared lazy tails are important for the efficiency argument. This is not a license to mutate old native storage. The Lab keeps its established strict persistent FIFO and simultaneous-record compiler; a new construction must provide its own paid service schedule. In particular, retaining a version does not grant its descendants the service performed by another descendant.

3. An exact fixed-consumer consequence

Fix a deterministic finite automaton A with state set Q. For a word v define

$$T_v(q)=\delta^*(q,v).$$

Then

$$T_{uv}=T_v\circ T_u,\qquad T_\varepsilon=\operatorname{id}_Q.$$

Replace each string register by its element of the finite set Q^Q. An assignment that concatenates constants and old registers becomes composition of their transformations. Simultaneous assignments use old values. At the end, evaluate the final expression’s transformation on A’s initial state and test its accepting set. A partial producer’s undefined output remains rejected or undefined as specified by the chosen consumer language.

This proves that a fixed finite-state consumer can be updated throughout the producer computation without enumerating the final string. The finitely many transformations and registers can be absorbed into finite control. Copylessness is not required for this particular consequence: repeated old-register occurrences repeat a finite transformation, although copylessness remains part of the imported SST theorem.

For the updates x:=xa and y:=ay, the registers contain w and its reversal. Maintaining T_x and T_y therefore gives A’s answer on w reverse(w) by the final expression. This is a direct application of the finite transition monoid, not an originality claim.

A growing activation dictionary is the exact missing hypothesis. Treating each dictionary vertex as a state makes Q input-dependent. All-state transformation construction, name routing, current-version maintenance and observation then require paid work. The fixed-consumer argument proves none of those charges.

4. Exact release-tail test for an ordered worker

Let T and C be positive integers. Suppose T actual input symbols each provide C elementary service opportunities. Jobs 1 through k must execute serially in that order. Job j has positive integer cost p_j and release symbol r_j in {1,…,T}; it is usable from that symbol onward, with arrivals before that symbol’s service. Releases may be nonmonotone. Include every setup and dependency in the costs and release events; allow no service after symbol T.

The earliest completion coordinates satisfy

$$F_0=0,\qquad F_j=\max\{F_{j-1},C(r_j-1)\}+p_j.$$

Induction expands this recurrence:

$$F_k=\max_{1\le j\le k}\left(C(r_j-1)+\sum_{i=j}^k p_i\right).$$

The induction step appends the next cost to every existing term and adds the new job’s own release term. Thus the worker finishes by the final symbol exactly when

$$\sum_{i=j}^k p_i\le C(T-r_j+1)\quad\text{for every }j.$$

The empty job sequence finishes immediately. Greedy service is earliest among schedules respecting the fixed order, so these conditions characterize feasibility for that order. They are not a characterization for parallel or freely reorderable work.

One cost-T job released at symbol T fails whenever T>C, despite total work being linear. Consequently, finishing a reversed key at the end and only then starting its ordinary growing-trie scan fails that pipeline’s deadline. A prepared reversed-key index, finite-consumer summary or another aggregate may escape. This is not a native-language lower bound.

The criterion is an audit, not supplied advice. The runtime is not given T, release annotations, a decomposition or ready handles. A native proof must construct the jobs, discover their availability, and charge queue operations, old-storage observations, allocations, routing, deferred work and final output. A data-dependent release can be audited on its actual execution trace, but using a supplied release schedule would not construct the required recognizer.

5. The next producer test

The payoff is a sharper sufficient-condition target: useful delayed computation needs both bounded work and timely access to its dependencies. Construction 78 already demonstrates a nontrivial instance, where one late map lookup is paid by remaining key data. The next construction should replace its unchanged suffix by an input-built transducer with a fixed output-delay bound.

The native test must build transitions from ordinary records, reject inconsistent definitions, initialize the right consumer version, pay consumed-prefix replay and read current activation by the final symbol. The delay bound is a fixed machine constant, independent of namespace count and input length. Any final bounded output burst must be serviced on existing ordinary delimiters, never extra padding or EOF work. Total output length, bounded delay and bounded local transition access are separate obligations; none substitutes for the others.

Replay slices require each fork to pay its replay. Affine joins retain their coordinate and routing hypotheses. Persistent causal algebra preserves shared history without furnishing a free current answer. Unary coherent cubical controls do not supply arbitrary branching or feedback. Native SAT controls retain ordinary late pins and final-symbol negative output. Recognition would give a PEG for the reversed checked language unless a separate closure argument applies.

Arbitrary whole-suffix permutations, arbitrary-name routing and heterogeneous service remain open. Entry 129’s relation quotient and matching/positive-path bounds retain their original contracts; the present arguments do not convert port bounds into an unrestricted native lower bound.

Evidence and contribution

The fresh checker compares a tick-by-tick ordered worker with the recurrence and tail inequalities, including nonmonotone releases. It separately compares finite-state register summaries with explicit string evaluation. These are bounded abstract-model experiments, not native execution tests.

The finite-consumer result is known/direct finite-monoid reasoning. The deadline formula is elementary scheduling algebra. The contribution of this review is their resource-contract comparison and the resulting producer test, not a new theorem count. Construction 78, mathematical count 141 and root claims remain unchanged.

This reconstructed edition supersedes the missing local manuscript documented in the repository recovery record. Only fresh checks and review of this edition are attached to it. The dedicated assessment is counted once upon completion of the required review, integration and publication workflow; publication receipts remain in root integration state.