Relation composition: sharing, receipts and future queries

Working argument, 9 October 2026. Entry 129 investigation. This journal contains assessments 121-189; the linked proof chain continues through assessment 199.

Outcome and scope

This investigation asks when two independently prepared relation fragments can be composed without rereading or rewriting all of their stored data. A relation is a table of possible transitions. Composition asks whether an output of the first table can serve as an input to the second. If one fragment permits middle states $\{0,2\}$ and the other accepts $\{1,2\}$, their composition can connect through state $2$. Replacing the second set by $\{1,3\}$ removes that connection. Retaining both tables is easy; discovering and reusing their shared middle states under bounded local access is the hard part.

The journal establishes three kinds of result. Sections 1-7 give polynomial Boolean presentations and an unconditional communication lower bound for exact composition of independently prepared stores. Sections 8-60 test which input structures let a native persistent machine avoid that obstruction. The constructions progress from bounded fanout and finite images to checked coverage, learned row classes, stable palettes, unequal-width lanes, bounded holes and name-paid suffix readers. Section 29 separately gives a conditional native obstruction under OMv. None of these results characterizes all cheap composition.

Current result and frontier. The latest result is the scale-sparse band construction. Picture the accepted target lengths in one row as many separated runs. Instead of maintaining every run in one global directory, the construction groups lengths into exponentially growing bands. Each band is empty, full or contains one interval, and every doubling block of band indices has at most a fixed number $r$ of partial bands. Ordinary input builds and checks two persistent directories. The work needed through queried band $k$ is $O_r(k)$, so a short query does not wait for unrelated work at much larger scales.

This permits unboundedly many separated components while preserving positive and negative late answers. It extends the preceding persistent interval construction, which removed the fixed maximum-diversity gate for one interval of occupied lengths. The result still requires complete binary levels, scale-sparse partial bands and right-first serial reuse. It does not settle unrestricted radial profiles or joins of independently prepared stores.

The next test allows several separated occupied runs inside one partial band. The open obligation is to build a checked mixed-region budget from ordinary input and make its representation locally readable after late name selection, without supplied decompositions or unpaid bursts. Sections 50-60 retain the earlier path from final-profile agreement to bounded exceptions and name-paid suffix rows. The source collection provides readable notes, highlighted checkers, stable line anchors and exact downloads.

Full binary relation composition has a polynomial-size presentation by ordinary Boolean constraints over a fixed finite character alphabet. Exact two-sided continuations distinguish every relation. This supplies the semantic half of entry 129’s obstruction. It does not supply a matching-diagram representation of a persistent machine.

There is also an access obstruction that survives arbitrary persistent sharing: under the independent-preparation contract below, exact composition followed by even one fixed endpoint query requires

$$(c+T)\log_2(S+2)=\Omega(h).$$

Here each independently prepared store has at most $S$ bounded-degree cells, $c$ counts exported handles and words, and $T$ counts old-store cell observations during the entire merge and query. For fixed $c$ and polynomial $S$, $T=\Omega(h/\log h)$. This is a written application of a standard deterministic communication argument, with a self-contained proof below; no novelty claim is made. It is not a native SAT/PEG lower bound.

The structural obstruction is an independent cut exposing two arbitrary subsets of the same h choices, followed by an exact intersection test. It is a necessary obstruction criterion, not a characterization of all patterns permitting cheap reuse.

1. Fixed-alphabet Boolean fragments

Let $H=\{0,\ldots,h-1\}$, $h\ge 2$, and $b=\lceil\log_2 h\rceil$. Expose two $b$-bit Boolean tuples $X,Y$. For each code pair $(a,d)\in\{0,\ldots,2^b-1\}^2$ that is invalid or absent from $R$, include the clause

$$(X\ne a)\lor(Y\ne d).$$

Each displayed inequality expands into the $b$ literals saying that some bit differs from its specified value. The resulting CNF has at most $4h^2$ clauses, each of length $2b$, and its satisfying boundary assignments are exactly $R$. Invalid codes are excluded explicitly; unused binary codes are not hidden domain promises.

Turn a clause l_1 OR … OR l_k, k>3, into the usual chain

$$(l_1\lor l_2\lor z_1),\quad (\neg z_1\lor l_3\lor z_2),\ldots, (\neg z_{k-3}\lor l_{k-1}\lor l_k),$$

using fresh private variables. If every $l_i$ is false, the chain forces $z_1,\ldots,z_{k-3}$ true and contradicts the last clause. If some $l_i$ is true, choose each $z_j$ to mean that all preceding literals $l_1,\ldots,l_{j+1}$ are false. This extends the boundary assignment and satisfies the chain. Clauses of size at most $3$ are retained. Thus existential projection is preserved, including the empty and full relations.

For $m$ fragments, use boundary tuples $X_0,\ldots,X_m$ and disjoint private chain variables; conjoin $F_{R_t}(X_{t-1},X_t)$. Existentially hiding $X_1,\ldots,X_{m-1}$ and all private variables gives $R_1\cdots R_m$ in left-to-right path order. This follows by choosing the intermediate states in the definition of relational composition, in both directions. The empty composite is the identity relation on valid codes, represented by bit equalities and domain restrictions.

There are $O((m+1)h^2b)$ variables and literal occurrences. Give variables ordinary binary identifiers with explicit signs, separators and clause delimiters. The alphabet is fixed, independent of $h$ and $m$. Actual encoded length satisfies

$$N=O((m+1)h^2 b\log((m+1)h^2 b+2)).$$

This is a uniform, explicit polynomial construction, not compressed relation letters. It spends time writing every literal and identifier. It is not a bounded-output online recoding: allocating global variable names, building clauses, and identifying adjacent interfaces are construction work. Reading these strings natively grants neither prepared handles nor an uncharged decomposition.

To distinguish R from Q, choose (i,j) in their symmetric difference and add the b pins X=i and the b pins Y=j. Exactly one formula is satisfiable. Equivalently compose with singleton diagonals I_{i}, I_{j} and test nonemptiness. These continuations have ordinary finite encodings. Their existence is semantic distinguishability, not a free native query operation.

2. The precise diagram transfer

Entry 129, liveness paper, Corollary 3.2, proves: an identity-containing submonoid of the matching monoid $D_k$ mapping unitally onto all relations on $h$ points requires

$$k\ge 2^{\lfloor(h-2)/31\rfloor}.$$

Its Theorem 4.1 constructs symbol-local diagrams for an $s$-state two-way deterministic read-only automaton, with $k\le 4(s+2)^2$; Lemma 5.2 gets the quotient by singleton contexts. These are established imported results. The companion complementation paper concerns two-way nondeterministic complementors and a different constant 127; this investigation uses the deterministic paper’s divisor theorem. Neither supplied result is a fixed-alphabet native persistent-language bound.

Here is the exact sufficient contract for a fragment transfer. For fixed $h$, assign every relation fragment a context-independent $d_R$ in one common $D_k$. Empty composition is $1_k$. Composition of independently represented fragments is exactly matching multiplication, with fixed port identification and no additional context-dependent rewrite, memory, cached bit, or growing port set. A fixed observer of $d_Ld_wd_R$ answers nonemptiness correctly for every finite fragment word and every two-sided context, including empty contexts. All ports count, including ports encoding control or retained receipts.

Then d_u=d_v implies equal answers in all two-sided contexts. The singleton tests above imply r_u=r_v. Hence d_w maps well-definedly to r_w on the generated submonoid, preserving products and identity, and reaching every relation through its one-fragment generator. The imported divisor theorem applies.

Physical serialized CNFs need not form a monoid under literal string concatenation: fresh private names and boundary identification are explicit. The contract is on fragment composition up to renaming, with the empty identity specified. A theorem about raw string readers would additionally need a charged implementation of this gluing. Likewise one must not apply the automaton’s quadratic state-to-port estimate to an arbitrary persistent interpreter.

The contract permits arbitrarily many revisits when they are already encoded by the same passive diagram. It does not permit a revisit to carry new unbounded state. Finite control can be charged into ports; it is not free to grow with h. An h-dependent diagram is a nonuniform representation family unless one separately proves a uniform implementation.

3. How sharing escapes, and what it does not buy

A persistent term store can retain two operand roots and allocate a binary node Join(left,right). Old operand cells are shared, not copied or modified. The node denotes relational product, and retained roots permit further independent reuse. The operation costs one node once both handles are actually available. A product expression of $m$ explicit matrices takes $O(mh^2+m)$ cells in a simple bounded-degree representation. Exact evaluation can be done later, for example by successive reachable-set propagation through the matrices; its work and routing are not zero.

This is a precise escape from the diagram contract: composition extends a directed term graph with two references and deferred existential Boolean evaluation. It is not fixed-port matching multiplication. Parenthesizations are only semantically associative, and a join with identity need not be physically identical to its operand. A semantic quotient of this term algebra can therefore contain the relation monoid without forcing a small matching representation.

A more eager, nonnative upper control materializes $h^2$ product bits as ORs of $h$ pairwise ANDs. A bounded-fanin persistent Boolean circuit uses $O(h^3)$ gates and shares old operand bits; a balanced index tree reads a materialized result bit in $O(\log h)$ pointer steps. Enumerating and routing the operand handles is charged additional construction work. Neither this circuit count nor the one-node lazy join proves a native constant-time merge. The extra compositional operation is creation and evaluation of mixed Boolean gates whose inputs come from both prepared stores.

4. Independent-preparation access theorem

Fix public $h$, a deterministic uniform interface algorithm, degree $d$ and a finite label alphabet. Permit even nonuniform public code depending on $h$, provided it is independent of the two private inputs. Alice independently prepares a bounded-degree store $A(x)$ from $x\in\{0,1\}^h$; Bob independently prepares $B(y)$. Preparation may be arbitrary and expensive, but is counted separately as $P_A,P_B$. No preparation phase reads the other store. Each store has at most $S$ cells, with labels and $d$ pointers, all pointers represented by $O(\log(S+2))$ bits. Private cell numbers can always be replaced by chronological allocation indices. A public immutable base is allowed; private aliases between the two stores are not.

The merger receives at most $c$ words or handles total, each of $O(\log(S+2))$ bits, and bounded finite control. Handles, lengths, completion signals and any input-dependent control returned by preparation count in that budget. Arrival time, allocator metadata, program selection and unbounded numeric pointer values are not additional channels. Addresses and equality outcomes, if used, must be represented within the same bit budget. Thus the statement does not smuggle input bits through identities.

After this boundary, allow arbitrary computation, new persistent cells, branching, copying of acquired handles, retained receipts, revisits and mixed cached summaries. Every access to a private old cell is charged. Its contents, including all outgoing pointers, fit $O(\log(S+2))$ bits. Let $T$ be a worst-case bound on the total number of those old-cell accesses until the first exact Boolean answer. Deferred jobs and reads through newly allocated routing nodes count when they reach old cells. New-cell allocation and local work are charged in the overall runtime too; allowing them for free in this stronger access lower bound only strengthens its scope. Any later advice supplied by a preparer also counts as communication.

Suppose this service works for all relation pairs and reports whether (0,0) belongs to their product. Set

$$R_x=\{(0,i):x_i=1\},\qquad B_y=\{(i,0):y_i=1\}.$$

Then $(0,0)$ is in $R_xB_y$ exactly when some $x_i=y_i=1$. These row/column relations themselves have fixed-alphabet 3CNF fragments of $O(hb\log(hb+2))$ length: pin the fixed endpoint and forbid each invalid or excluded code of the other endpoint, then apply the clause-chain construction. No exponential compressed input is being postulated. The query endpoint is fixed in advance, so it cannot transmit either private subset.

Proof of the bound. Both parties simulate the merger. Send its exported handles and words. When it requests a cell from one party, that party sends the addressed cell contents; communicating the request address too costs only another $O(\log(S+2))$ bits. Both parties then know the abstract merger state and every newly created cell, and can repeat. Unbounded private preprocessing need not be communicated. This gives a deterministic two-party protocol for nonempty set intersection of cost $O((c+T)\log(S+2))$, including one final answer bit. Variable termination must be represented in the transcript; the bound is worst case.

For completeness, such a protocol needs at least $h$ bits in the worst case up to a fixed additive convention. Consider the $2^h$ disjoint input pairs $(x,\operatorname{complement}(x))$. If two distinct pairs share one rejecting terminal transcript, the deterministic protocol rectangle property makes both crossed pairs share it as well. At least one crossed pair has a common 1: otherwise x is a subset of x’ and x’ is a subset of x, contradicting distinctness. That crossed pair must accept. Hence all $2^h$ pairs need distinct rejecting leaves, and a binary protocol tree of depth $C$ has at most $2^C$ leaves. Thus $C\ge h$, proving the displayed bound.

Consequently, when $c$ is fixed and $S\le h^a$ for a fixed $a$, a constant-cost merge plus constant-cost exact query is impossible, even with sharing and receipts. In a bounded-radius graph machine, one step observes at most $B(d,r)$ old cells, where $B$ is fixed for fixed degree and radius. Any implementation of this independent-store contract therefore has merge-plus-query time $\Omega(h/(B\log h))$. This statement grants the merger more routing freedom than native old-top access, so it does not rely on making native routing free.

The bound is deliberately on merge plus first query. It cannot exclude expensive merge followed by cheap reuse, or joint preprocessing followed by a ready answer. It is deterministic and exact; no randomized tradeoff is claimed.

5. Native transfer audit and controls

The outstanding premise is independent preparation, not the availability of Boolean encodings. A native machine reading the second fragment can inspect the first history while new symbols arrive. Those observations are joint work. The $O(hb\log(hb+2))$ real symbols in the sparse construction can already pay the $\Omega(h/\log h)$ lower bound. Calling that phase independent preprocessing would be false. Similarly the full relation alphabet supplies one letter per $h^2$-bit relation whereas this encoding supplies polynomially many characters. The original exponential state theorem does not bypass this accounting.

Completed affine-fragment joins provide a useful contrast: their matrix/query bit-probe bounds restrict linear encodings and a different query family. This bound permits arbitrary independent encodings but charges access to both stores and uses intersection. Neither replaces the other. Replay slices retain a computation’s causal history; they do not automatically provide two isolated independently prepared roots. The persistent causal algebra’s unfolding/full-abstraction and guarded folds, and the unary coherent cubical algebra’s path coherence, preserve their stated observations. None supplies the missing constant-cost mixed readout theorem. Result 120’s bounded-extra branches are fixed in advance and use actual base-name symbols to do work; their timing is not contradicted.

6. A stronger-algebra test: reusable entry access and matrix multiplication

The sharing escape can be tested without trying to force it back into diagrams. Suppose a uniform persistent interface prepares any two $h\times h$ Boolean matrices from their explicit inputs, at costs $P_A(h),P_B(h)$, then composes them at cost $M(h)$. Suppose its exact product root can be retained, and each ordinary binary endpoint query $(i,j)$ costs $Q(h)$ through its output, with $H(h)$ additional work to select or restore the retained product version. All these bounds are worst case, and polynomial storage with $O(\log h)$-bit pointers is required. Matrix-dependent preprocessing, name decoding, root routing, allocation and output are included. There is no free ready query handle.

Enumerate all $h^2$ endpoint pairs. Restore the retained root as contracted, send the actual $O(\log h)$-symbol query, and write the answer bit. The output is the Boolean matrix product. This is a deterministic uniform algorithm taking

$$O(P_A+P_B+M+h^2(Q+H+\log h))$$

word-RAM operations whenever each bounded-local interface step has its usual constant-cost cell simulation. The simulation uses $O(\log h)$-bit words because storage is polynomial; a bit-cost simulation adds its pointer-processing cost. The formula includes writing the $h^2$ output bits and does not infer a decision lower bound from output size.

In particular, near-quadratic preparation and merge, plus polylogarithmic query and version-selection costs, yield near-quadratic Boolean matrix multiplication. This is an algorithmic implication, not an assumed BMM lower bound and not a claimed impossibility. A native syntax implementation of the Boolean-fragment compiler must additionally charge generating its explicit constraints (polynomial in Section 1, near-quadratic up to logarithms for one full relation), verifying the structure, and exposing the retained product version. A native recognizer for SAT by itself need not expose this service or answer all entries; the implication cannot be applied to it without that interface theorem.

This test distinguishes the two escape mechanisms: delayed Join pays Q, while eager mixed materialization pays M. Persistent version selection is a third cost H, not an automatic benefit of having once allocated the root. It also gives a concrete upper-construction target: implement reusable product access in this full accounting, or find the step where native chronology forces a larger cost. No matrix-multiplication conjecture is used in this note.

7. Next decisive test and failure record

The failed route is: polynomial CNF realization + exact future quotient => native exponential lower bound. It fails because the representation and timing premises do not follow. The countermechanism is a persistent Join node plus delayed or eager mixed Boolean computation. This does not refute entry 129 or prove cheap exact native composition.

The next test is a chronologically valid native construction in which the second independently meaningful fragment arrives while the first root is retained. Determine exactly which old-store observations during that arrival must mix both inputs, and whether an ordinary later short continuation can force additional work after those paid observations. A lower-bound route must bound the information in retained mixed receipts, not discard them or reset independence. A positive route must schedule every mixed gate, root lookup and final read within actual symbols with fixed degree/radius. If all dependence can be paid while the second fragment arrives, this particular independent-cut obstruction is exhausted for that encoding; choose a genuinely new late query family rather than replaying the same intersection lower bound.

Validation: written proofs above; finite semantic check and operational receipt are linked from the program checkpoint. The finite check corroborates small encodings and fooling sets, not the asymptotic proofs. Root CLAIMS.yaml admission and reader publication are separate gates.

8. Exact observation contract

Consider a tree with many possible routes to one source. Seeing one live route proves reachability. Seeing a dead route says nothing about the alternatives. The next arguments ask exactly what a retained summary must have computed to make the all-dead answer quick. The reconciled Horn construction and positive-path contract supply the relation semantics and chronological branching realization used here.

Fix a query q and a promised family of prepared stores. Stores have a common finite universe of logical record positions. A record contains a finite label and at most d ordered pointer fields; an absent edge is an explicit null field. The whole record, including pointer targets and any observable metadata, is the observation atom. Initial roots and control are identical across the family. If a varying exported word or control value is allowed, include it as an initially observed atom; it is not free information.

The readout is deterministic and causal: its next action, allocation, labels, pointer choices and answer depend only on the fixed query, current finite control and previously observed records. New records may share old pointers and previous allocations. Pointer equality, if allowed, must use already observed pointers. No address arithmetic or opaque identity, allocator layout, metadata, variable preparation time, or other channel supplies input-dependent information without an observed atom. Arbitrary address probes can be granted as a stronger readout model, but their chosen addresses must still depend only on this transcript. Physical storage remains charged separately.

Native specialization, if applicable: one uniform machine has fixed d, radius r, finite labels/control and a fixed initial graph. Each actual input symbol creates its allowed new top using only the permitted neighborhood of the old top; old nodes are immutable. The forward encoded formula is followed by ordinary binary-name endpoint unit pins, and output is due at the final symbol, with no EOF work. A step’s observable old neighborhood has at most a constant b atoms, for example b <= 1+d+…+d^r for one root. Charge all extra active roots/control atoms, preparation symbols, allocations, routing, restoration and output; changing the model cannot hide them inside b. The theorem below even grants more access than that machine. It is not a compiler into it.

Observation lemma (certificate necessity). Let G0 be a baseline store and let G range over every promised store giving the opposite answer to q. Let Delta(G) be the positions where its observation records differ from G0. If O is the set of initial and old records observed on the G0 execution, then O intersects every Delta(G).

Proof. If a G has no such intersection, induction along the baseline execution gives identical input, control, observed values, allocation choices and new records in both executions. The next selected position is identical and its record agrees. Repeated observations and negative tests preserve the induction. Both executions therefore terminate with the same answer, a contradiction. Newly created receipts cannot introduce a distinction absent from the transcript. Initial differences must have been counted as observations. This proof does not assume the readout is monotone.

Conversely, for a fixed position set O, intersecting every opposite-answer difference set says exactly that the observed record tuple is an answer certificate on the promised family. It does NOT supply an efficient procedure to choose, route to or verify O, nor a finite-control implementation. Thus hitting number is a necessary observation bound, not a complete native criterion.

For $h$ opposite-answer variants with at most $\lambda$ of their difference sets containing any one atom, $|O|\lambda\ge h$. If at most $a$ initial atoms and $b$ old atoms per step are observed, $(a+bT)\lambda\ge h$. A fast representation must therefore concentrate distinctions into accessible records or exploit a smaller relevant alternative family. This is necessary, not sufficient: a cached parity bit distinguishes zero from every singleton flip, yet misses every double flip. Using only singleton variants cannot certify exact OR. The observation lemma uses all opposite-answer stores.

9. A concrete chronological branching subclass

Use two older terminal nodes, source and dead. Create h switch nodes, each with one pointer to source (live) or dead (off). Finally create a balanced binary OR routing tree above the switches, bottom-up, each internal node with at most two pointers to earlier nodes. Its root reaches source exactly when at least one switch is live. Labels are fixed and finite; the input determines only the switch edge. Node count is O(h), outdegree at most two, and all edges point backward in creation order. This is an instance of the foreground relation-layer graph, with alternatives converging on the same designated source.

On the all-off store, activating switch i changes only that switch’s record. The observation lemma forces inspection of every switch, even if routing starts with a freely granted root, reads arbitrary positions, revisits nodes, allocates new receipts, or uses negative local tests. Under fixed radius/degree this is Omega(h) steps up to the constant neighborhood size. A late query consisting of ordinary endpoint names of length O(log h), with a constant number of delimiters/signs, supplies only O(log h) native steps. Hence this raw snapshot plus fixed initial control cannot supply that readout at the deadline for growing h.

The gratis root/arbitrary probes strengthen the lower-bound model; they are not an allowed input format or an implementation claim. Endpoint names and source designations are mathematical indices, not unbounded machine labels. Routing them would only add cost. Constant initialization does not supply the growing tree: its O(h) preparation and storage are charged. This snapshot construction has not established that the tree is built by the native old-top update rule from an arbitrary clause stream. The result is conditional on a representation actually using that raw snapshot and exporting no varying summaries. A previously computed OR bit, or input-dependent finite control, invalidates that premise and is a legitimate escape.

This is a no-path obstruction, not an exponential-port theorem. The source graph is polynomial and permits branching. A deterministic test of the absence of every path is decreasing under adding live edges, so it does not satisfy the companion’s positive increasing readout contract. Negative tests explain why that conditional bound cannot simply be applied to it; The observation lemma explains why the raw escape still has access cost.

10. Exact preparation/probe tradeoff in a stronger, separate contract

Take h independent Boolean input atoms x_1,…,x_h. Preparation is a fixed acyclic circuit of g charged gates, each of fan-in at most B >= 2, whose outputs are stored records. Gate functions may be arbitrary Boolean functions, including negation, with finite fixed record alphabets. Copying a pointer or atom does not combine dependencies; a record combining several values counts its actual input fan-in. Circuit topology, gate descriptions, exported roots, control and addresses are input-independent. All changing records arise from these gates or input atoms. Query computation may adaptively probe any input or gate-output record and perform arbitrary Boolean computation. There is no unobserved metadata channel or free answer-dependent initial state.

10. On the all-zero input, any exact OR (or its complement) readout inspecting q distinct records satisfies

$$h \le q+(B-1)g.$$

Proof. Every input must be an ancestor of at least one inspected record. Otherwise flipping it leaves all inspected values identical; transcript induction contradicts the changed OR. Take the union of the circuit ancestor cones of those records, containing g’ <= g gates and all h input vertices. Ignoring constant vertices only weakens the count. Its underlying undirected graph has at most q components: every included vertex has a directed path to an inspected vertex. Thus it has at least h+g’-q edges. Gate fan-in gives at most Bg’ edges (parallel wires can be discarded). Therefore h <= q+(B-1)g’ <= q+(B-1)g. Constants, unary copies, shared ancestors and multiple observations cannot improve this inequality.

For B=2 and any partition of the inputs into q nonempty groups, prepare one OR receipt per group using exactly h-q binary gates. Query all q receipts and negate their OR to answer no-path. This attains q+g=h in the granted probe model. Preparation depth for a receipt depending on u inputs is at least ceil(log_B u); ordinary balanced OR trees attain logarithmic depth. The latter counts dependency depth, not native symbol latency or free parallel execution.

The matching upper bound pays O(h) input/gate work and storage and O(q) query probes plus combining work, even when q=1. Selecting group receipts and retaining/restoring roots is NOT included for free in a native application. This is a fixed-topology circuit/probe result; arbitrary adaptive persistent preprocessing has not been reduced to such a circuit with g equal to its allocations. In particular a pointer’s possible targets and input-dependent control may encode dependencies. Expanding those operations into gates could cost much more. The observation lemma remains the general observation statement; The tradeoff must not be silently substituted for it.

11. Attempted native transfer, escape and precise bottleneck

A fixed endpoint product bit is OR_k(A_ik AND B_kj). Raw branch switches can represent these h terms; even granting that their ANDs are already computed, the all-zero OR needs the inspection/receipt tradeoff. But while the second operand arrives, a machine can compute joint receipts. For the restricted fixed-endpoint family where A_ik=1 and only B_kj varies, a finite running OR uses O(h) charged input work and constant state, answering the later fixed query immediately. Thus the supposed universal linear query lower bound is false. Chronological immutability does not prevent a fresh top from retaining an accumulated bit.

For arbitrary late i,j, one fixed-query receipt is insufficient. The direct control is a full table: compute h^2 product bits with O(h^3) Boolean gates/work and retain their values, then use an ordinary bit-addressed trie for lookup. This is an offline circuit/data-structure control only. A dense two-layer Horn stream has N=O(h^2 log h) symbols (actual encoding), so the elementary cubic computation does not fit a fixed per-symbol native budget merely by calling it preprocessing. No lower bound excludes a faster computation, and sparse instances have a smaller N. A supplied table or endpoint handles would change the problem.

Two attempted transfers therefore fail for separate exact reasons: 1. Applying the positive-path bound after negating reachability violates its increasing-readout premise. 2. Applying the raw-snapshot bound or the run 121 independence bound to a native whole stream forbids or omits mixed receipts that can be paid while input arrives.

Neither failure is a closure of the Lab’s SAT/scaffold question. The next attack must track endpoint-specific receipt creation and old-top root routing together. A candidate useful positive subclass would have a bounded number of unresolved interface alternatives after each charged composition, plus a native schedule producing certificates for every permitted late endpoint. Bounded semantic alternatives without that schedule is not enough. The retained-product/BMM implication in run 121 remains a diagnostic, not an assumed impossibility theorem.

Controls: affine-fragment joins depend on their representation contract; replay slices pay for observations at available symbols; causal and unary cubical algebras describe allowed structural operations without granting an answer oracle; equal-support and bounded-extra SAT constructions build explicit finite survivor receipts on their demonstrated schedules. None supplies generic late endpoint-indexed relation receipts. No closure/reduction to arbitrary SAT, nor a forward PEG claim, follows. Native recognition of L gives a PEG for reversal(L).

These extensions use elementary observation indistinguishability and circuit dependency counting. They identify the representation and scheduling obligations; they do not claim a new general circuit lower-bound technique. Finite checks exhaust small receipt partitions, arbitrary binary gate functions and chronological switch graphs. Their exact scope is recorded in the maintained checkpoint.

12. A native positive: composition through finitely many frozen rows

Suppose a completed table describes which targets each intermediate name reaches. A second table names at most a fixed number of intermediates for each source. We need not copy the target sets or construct their unions. While reading each second-table edge, locate the completed target-set dictionary and retain its root. A later source name selects a bounded list of those dictionaries; the target’s arriving bits search them in parallel.

This gives a genuine native positive case of composition and reuse. The structural conditions are that the referenced computation has finished, each source selects only a bounded number of its predicates, and the selecting names are present when the reference is created. The number of sources and targets, the sizes of the target sets, and all name lengths remain unbounded.

12.1 Ordinary Horn input and exact theorem

Fix $d\ge1$. Names $u,v,w,a,b$ are arbitrary nonempty binary words; leading zeros and proper-prefix names are significant. Use three disjoint variable classes with ordinary binary names $00u$, $01v$, and $1w$. These fixed prefixes are checked syntax, not supplied handles, a graph decomposition certificate, or a growing alphabet. No decomposition of an arbitrary input graph or closure under arbitrary variable renaming is assumed.

The input is a concatenation of the following ordinary signed clauses, in the displayed block order:

1. Any number of $S$ clauses (-01v,+1w);.
2. Any number of $R$ clauses (-00u,+01v);.
3. Exactly the two late unit pins (+00a);(-1b);.

There are no block headers or sizes. The sign, arity and fixed variable prefixes identify the clauses; a finite parser checks the phase order. Literal order inside each binary clause is part of this encoding. Within either block, edges may appear in arbitrary order and repeat. Require at most $d$ distinct intermediate names $v$ for each source $u$ in $R$; the machine checks this requirement. Neither block needs to contain an edge, and queried names need not have appeared earlier.

Written native construction. For each fixed $d$, one deterministic native scaffolding automaton recognizes the well-formed inputs above that satisfy the degree condition and whose formula is satisfiable. It has fixed degree, radius, finite labels/control, fixed initialization, one new node per actual symbol, and acceptance at the final semicolon without EOF work. All logical history and work are $O_d(N)$, where

$$N=\sum_{(v,w)\text{ records}}(9+|v|+|w|) +\sum_{(u,v)\text{ records}}(10+|u|+|v|) +11+|a|+|b|.$$

The sums count repeated records. There is no padding, preprocessing outside this input, fixed-width-name promise, advice, or uncharged product table. Syntax or degree violations reject regardless of satisfiability. This is a restricted Horn language, not arbitrary Horn SAT or arbitrary clause order.

The Horn composition proof gives its semantic test:

$$F_S(z,y)\land F_R(x,z)\land x_a\land\neg y_b \text{ is SAT}\iff (a,b)\notin RS.$$

The clauses are presented right factor first, although their relation product remains $RS$. Logical conjunction does not impose an input order; the native scheduling proof does. The scaffold-to-PEG theorem gives a PEG for the reversal of this exact encoded language, not automatically for its forward orientation.

12.2 Pointer-valued serial dictionaries

The construction uses the Lab’s serial capsule trie, strict persistent FIFO, and simultaneous-record compiler. The needed extension is a fixed-arity pointer payload, rather than only a finite scalar at a trie terminal.

Represent a terminal value by one pointer to an immutable payload record, with missing meaning the default. A trie node contains that pointer and two child pointers. A path frame contains the value pointer, a finite direction bit and the off-path child. Frames remain fixed-arity records. The FIFO copies only its opaque frame references; it does not inspect, compare or execute the stored values. The existing FIFO payload extension therefore applies unchanged. The dictionary’s one-node view copies a value reference and exposes children without recursively interpreting the value. A caller follows only the fixed fields it needs.

While a key is arriving, accumulate its ancestor frames in root-to-leaf FIFO order. At its delimiter, retain the current node’s children and create a new explicit tip with the desired value reference. Publish a capsule consisting of that FIFO and explicit tip. This updates the value without walking back along the key. The frame-fold invariant from the serial dictionary proof applies to arbitrary payload references: their meaning is preserved by copying, and no pointer-identity test occurs.

An outer-key traversal can remain suspended while an inner key is read. Its current subtree and path FIFO are retained roots with strict, ready queue operations. After finishing the inner update, use its newly completed root as the outer terminal payload and close the outer capsule in bounded work. This is a fixed depth of nesting, not a recursive call stack growing with input length. The explicit-tip invariant holds for both dictionaries. Proper-prefix keys retain both their own payload and their children.

12.3 Preparing the right factor and capturing its rows

Maintain an outer dictionary $D_S$ mapping each intermediate $v$ to a Boolean membership dictionary for the row $S_v$.

During an $S$ clause, the bits of $v$ traverse its outer key while saving the outer path. At the comma, obtain the existing row root, defaulting to the empty dictionary. The bits of $w$ perform the inner membership insertion. At clause close, mark $w$ present, finish the inner capsule, and publish that root as the value of the suspended outer key. A duplicate merely sets an already true membership bit. Each name bit performs bounded local work; closing both capsules takes a fixed batch independent of both lengths.

At the first $R$ clause, freeze $D_S$. All subsequent right-row references point into this completed version. Maintain a second outer dictionary $D_R$. Its value at $u$ is a receipt containing a Seen dictionary of intermediate names, a finite count at most $d$, and at most $d$ row-root references.

For an $R$ clause, the bits of $u$ traverse the corresponding outer key, again retaining its path. While the bits of $v$ arrive, perform two parallel traversals: look up $v$ in frozen $D_S$ and traverse the receipt’s Seen dictionary. At the delimiter:

• If Seen already contains $v$, retain the receipt. Duplicate edges do not consume another slot.
• If $v$ is new and the count is $d$, latch rejection.
• Otherwise mark $v$ seen, append the completed row root $S_v$ to the bounded receipt, and increment its finite count. A missing $S_v$ contributes an empty-row root. Close the suspended outer capsule around the updated receipt.

Distinct intermediate names may have identical row contents or even share a root; they still occupy distinct slots. Deduplication tests their transmitted names through Seen, never pointer identity or extensional equality. Copying a receipt’s at most $d$ references is fixed work for the chosen machine.

By induction over $R$ records, the receipt at $u$ contains exactly one frozen right-row root for each distinct $v$ with $(u,v)\in R$. Every root is already available when captured. No long stored name needs to be replayed, including when a very long $u$ is followed by a one-bit $v$. The suspended capsule, rather than an upward restoration walk, closes that update.

12.4 Late queries and complete resource accounting

During the positive unit pin, the arriving bits of $a$ traverse $D_R$. At its delimiter, retrieve the at-most-$d$ row roots, using an empty list for a missing source. During the negative unit pin, feed each arriving bit of $b$ to all of these row cursors in parallel. At its delimiter inspect their finite presence flags. Accept at the final semicolon exactly when every flag is false. Thus

$$\text{reject on the pins}\iff \bigvee_{v:(a,v)\in R}[b\in S_v] \iff(a,b)\in RS.$$

The fixed parser has only the two implication phases, the two pin phases and a rejecting state. It checks all punctuation, signs, prefixes, nonempty suffix names and the end-of-record acceptance condition. A stopped partial input rejects. A finished implication prefix without both pins rejects as incomplete for this language. The last implication update is ready at its own delimiter; no later query symbol is being used to complete it.

Here is the entire per-symbol schedule at the abstract record level:

Each builder or lookup step makes a bounded number of strict FIFO operations, views and allocations. Finite labels carry tags, directions and counts in $\{0,\ldots,d\}$, never names or unbounded counters. The number of active roots, record arity, old-address radius and fresh batch size are all constants depending only on $d$. Copying a captured root means copying an exposed pointer field, not following its unbounded subtree. The initialization consists of fixed blank dictionaries, empty queues and empty receipts. Fresh pointers target bounded old addresses or declared same-batch slots. Guards inspect finite labels along bounded paths, with no numerical addresses, identity, timing or metadata channel.

These are exactly the whole-run compiler hypotheses. Its letter-synchronous translation supplies the native fixed-degree/radius machine with $N+1$ physical nodes including the base. All virtual frames, queue history, payload records, copied receipts, discarded partial paths and query-created capsules count toward $O_d(N)$ logical records. Literal pointer serialization costs $O_d(N\log(N+2))$ bits. No numerical optimization of the compiler constants is needed for this theorem.

The frozen product representation can also serve repeated endpoint queries in an explicit query protocol: retain $D_R$ in every header, reset the lookup cursor at each query’s first punctuation, and charge all subsequent name bits and allocations. This gives $O_d(|a|+|b|+1)$ work per query with bounded work per symbol. Repeated query answers refer to separate hypothetical pin continuations; they are not the SAT answer for conjoining every pair of pins into one formula. Selecting an unbounded family of past product versions is not granted for free.

12.5 What the criterion explains, and what remains open

For $d=1$, let every one of $m$ sources select the same intermediate, whose frozen right row contains $n$ targets. The product has $mn$ entries, but the representation shares one target dictionary among the source receipts. Its construction charges only the actual two blocks and names. Future answers remain available at serial-name cost without enumerating the product. This is access-preserving reuse, rather than just compact storage of unresolved branch choices.

The classical operations are functional trie lookup, immutable reference capture and a bounded union of predicates. The additional written construction is their ordinary-name, duplicate-checked, final-symbol native schedule. Demaine, Langerman and Price’s confluently persistent tries, §1’s constant-number-of-fingers model and §2’s functional path representation, are the closest existing container comparison. Their model already stores constant-size information including data pointers. Our proof uses the Lab’s FIFO capsule specialization and explicitly checks pointer payloads, suspended outer paths and chronological row completion. It is not a new general persistence technique.

Two restrictions are load-bearing. Allowing an $S$ update after an $R$ receipt has captured its row can make that receipt stale: capture an empty row at $(u,v)$, then add $(v,w)$ to $S$. The old receipt still reports absence of $(u,w)$. This refutes that extension of this implementation, not every other native algorithm. Removing the bound on the number of selected rows makes the query cursor family unbounded; the fixed-batch proof then fails. Neither restriction is an impossibility theorem.

The next decisive comparison is the opposite functional case: retain right-first presentation, let $S$ have one target per intermediate, and allow unbounded left fanout. The semantic product is only a renaming of the left relation, but its current receipt construction may need to replay long target names or maintain later-changing named columns. Resolve that routing and update-coherence obligation before asserting symmetry. Arbitrary factor order, arbitrary clause order, unbounded captured fanout and arbitrary Horn SAT remain open. The matching/positive-path lower bounds and the independent-preparation bound remain valid for their own contracts; this constructor reads and binds the second input against a completed first store and uses named, negative membership tests.

In particular, the left factor is read against the completed right store. An independently built left store is not merged for free: replaying its ordinary records would have to be charged, or another export-and-merge protocol would have to be proved. The positive theorem concerns the complete serialized input above.

12.6 Fixed-depth closure by flattening receipts

The same mechanism handles any fixed number $t$ of further factors with row degree at most fixed $d$, presented from right to left after the arbitrary base factor $S$. Use $t+2$ disjoint variable sorts identified by fixed prefix-free binary codes, and the same ordinary implication clauses in checked block order. Both $t$ and $d$ are chosen for the machine, not transmitted as a decomposition or nonuniform advice. These are recognized syntactic subclasses; no transformation from an arbitrarily renamed or ordered formula is asserted.

At level zero, each base row is its completed membership dictionary. After $\ell$ bounded factors, a row receipt contains at most $d^\ell$ references to those base dictionaries. To add an edge $(u,v)$ of the next factor, look up the already completed receipt at $v$ and copy its bounded reference tuple into the receipt being built at $u$. Keep a separate finite count and Seen dictionary for the at-most-$d$ distinct immediate successors; the number of flattened references is not that degree count. Duplicate edges are ignored. Different paths may contribute the same reference repeatedly; no identity test or set-union normalization is needed. A missing previous row contributes an empty tuple.

Induction on completed factors gives a reference for each contributing intermediate path and exactly the predicate union defining the relation product. At the base level a missing row may use the virtual empty membership dictionary; at higher levels a missing receipt has an empty tuple. Tuple length is at most $d^{\ell+1}$. Since $t,d$ are fixed, copying and observing such tuples remains a bounded batch. The same suspended-path updates and name-driven lookups apply. The finite phase parser also handles empty factors: when it skips a bounded-factor block, the product map becomes empty, while later records still undergo degree and syntax checking. At the final pins, run at most $d^t$ base-dictionary cursors in parallel. This proves native recognition with $O_{d,t}(N)$ logical work/history, fixed machine resources, and final-symbol output for this fixed-depth family. It avoids a query walk whose depth follows the whole stored dependency expression.

This is a sufficient criterion based on bounded expansion into already completed predicates, not a characterization of every reusable dependency pattern. The constants can grow with $d^t$; this proof does not provide one fixed machine when depth or expansion grows with the input. Nor does it make an input-supplied layering certificate free. The two-factor theorem above needs no additional layer markers, and this fixed-depth corollary checks its chosen finite collection of lexical variable sorts and phase transitions itself.

13. Unbounded branching with a checked finite terminal image

Assessment 124, 7 October 2026. Written supporting construction. The preceding result bounds how many completed dictionaries a row selects. A different sufficient condition bounds how many terminal answers can occur. This permits unbounded left fanout, and does not require the right relation to be functional. It does not settle the case of a functional right relation with an unbounded image.

Statement. Fix an integer $K\geq 1$. Use exactly section 12’s right-first ordinary Horn encoding, arbitrary nonempty binary suffix names and final positive-source/negative-target units. Replace its left-degree restriction by the checked requirement that at most $K$ distinct target names occur in the right block. There is a native deterministic recognizer for well-formed inputs meeting that requirement whose formula is satisfiable. Neither the source names nor the intermediate names have a cardinality bound. The machine constant is $K$, not an input parameter. Its PEG consequence concerns the reversed language only.

13.1 Discover the finite image, without a supplied palette

Maintain a capsule dictionary $P$ from target names to slots in $\{1,\ldots,K\}$ and a finite counter for occupied slots. Initially $P$ is empty. Maintain a second dictionary $D$ from intermediate names to subsets of those slots, initially empty. Subsets have $2^K$ possibilities and are finite labels; an absent value means the empty subset.

On a right clause $(-01v,+1w);$, process the actual bits of $v$ to obtain and suspend an update path in $D$. Its old value is a finite subset. Process the actual bits of $w$ to obtain an update path in $P$. If $w$ is new, assign the next unused slot, or reject on overflow. At the clause terminator, close the palette path if necessary and close the suspended $D$ path with the old subset union the singleton slot. Section 12.2’s capsule construction makes each closure a bounded batch, even when $v$ is arbitrarily longer than $w$. Repeated names recover the same slot by spelling, never by pointer identity. Duplicate clauses are idempotent. A new slot does not require updating any older mask: its previously unused bit was already zero.

After the right block, both $P$ and $D$ are frozen. No target spellings need be replayed. In particular a very long $w$ can be represented in arbitrarily many later contributions by its finite slot, while its full spelling remains in $P$ for the eventual query.

13.2 Combine all incoming contributions locally

Maintain a dictionary $A$ from source names to slot subsets. On a left clause $(-00u,+01v);$, suspend the update path selected by the actual bits of $u$. Follow the actual bits of $v$ in frozen $D$. At the terminator, close the $A$ path with the union of its old value and $D(v)$. There is no list of selected rows, no degree counter, no Seen dictionary and no cost proportional to the number of earlier contributors. Missing $v$ contributes the empty subset.

Induction on the processed left clauses proves

$$A(u)=\{P(w):\exists v\ ((u,v)\in R\ \land\ (v,w)\in S)\}.$$

The base case is empty. A new clause adds exactly the displayed contribution for its own $v$; duplicates add nothing. The invariant is exact because $P$ assigns distinct slots to distinct target spellings and is frozen before left processing.

The positive pin’s bits select $A(a)$, which is retained in finite control. The negative pin’s bits select $P(b)$. If $b$ is absent, accept at the final semicolon. Otherwise accept precisely when its slot is not in $A(a)$. By the Horn composition lemma this is precisely satisfiability. A missing source yields the empty subset. The section 12 finite parser still rejects malformed input, a right clause after a left clause, extra units, missing delimiters and incomplete prefixes. The empty-right-block case has an empty palette and accepts every well-formed pin pair.

13.3 All charged resources and the actual scope

Each name bit performs at most a fixed number of capsule views and strict FIFO operations. Each delimiter performs a fixed number of closures and finite-mask operations. Both dictionary roots and suspended-path headers form a fixed tuple. No deferred scan, arbitrary old-version selection, address test or unbounded arithmetic occurs. Initialization is the fixed empty representation. The exact length $N$ is the section 12 formula; no symbols were added. The existing bounded simultaneous-record compiler therefore gives fixed degree, fixed radius, finite labels/control, bounded old-top observations and allocations, and exactly $N+1$ physical scaffold nodes. Logical retained history is $O_K(N)$; a binary pointer encoding costs $O_K(N\log(N+2))$ bits. Python dictionary or tuple operations in a semantic checker are not the reason for these native bounds.

For any fixed number of right-to-left factors in section 12.6’s checked fixed-sort encoding, propagate these same masks instead of flattening row-root tuples. At each phase, freeze the preceding row-to-mask dictionary and build a fresh dictionary by unioning its selected masks. Induction gives the full relation product’s reachable terminal slots. Empty intervening factors give the empty map. Later clauses still undergo syntax checking. Thus fanout may be unbounded in every factor, while the mask width remains $K$ rather than growing with path multiplicity. This is for each fixed number of factors, with a fixed parser; arbitrary unsupplied layers or unbounded-depth parsing have not been established.

The sufficient mechanism is a fixed finite summary of terminal answers, preserved by union, whose classes are discovered with paid name traversal. It is an alternative to bounded selection among frozen predicates. Neither statement characterizes every native representation. The mask technique is classical finite-state aggregation; the additional written content here is its ordinary-name discovery, suspended-path commit and final-symbol schedule.

13.4 What the primary-proof review rules out as a shortcut

The assessment 124 proof comparison studies two persistence arguments. Their operation contracts do not by themselves supply the missing unbounded-image recognizer. Here are the concrete remaining failures.

• Expand the renamed relation. Let $S=\{(0,w)\}$, with $|w|=L$, and let $R$ contain $m$ distinct short source names pointing to $0$. The input costs $O(L+m\log(m+2))$. Explicit ordinary-name clauses for $RS$ repeat $w$ at least $m$ times, costing $\Omega(mL)$. Taking $m=L$ rules out a uniformly bounded-output-per-input-symbol materializing transducer, even if output is delayed. This is an output-contract obstruction. It does not obstruct shared representations, including section 12 and the $K=1$ construction above.
• Capture a mutable column and expect it to stay current. An immutable root captured before a later column update continues to represent the earlier version. Reading its local unfolding cannot reveal a newly created node. Supplying a current-version root and a paid route may repair this; retaining the old root alone does not. This is a failure of that particular implementation, not a lower bound for all possible routing.
• Accumulate an unbounded list of frozen functional rows. Each individual row is easy, but a late target name would need an unbounded number of simultaneous row cursors under this implementation. The finite-image construction succeeds because all contributions aggregate into one fixed mask. For unbounded image, replacing that mask with an arbitrary-size bit vector is not a finite-control operation.

The next decisive target is unbounded-image functional substitution, with right clauses first and ordinary late pins. Test an immutable, query-directed index that combines selected singleton targets without replaying their spellings, without following stale aliases, and without storing an unbounded cursor tuple. The unresolved obligation is a full per-symbol construction and lookup schedule. No lower bound follows merely because these three implementations fail.

14. Streaming names permit an unbounded terminal image

Assessment 125, 7 October 2026. Written native construction. There is a third sufficient mechanism for composition: a fixed routing rule can produce a target’s spelling while the intermediate name is arriving. This allows both unbounded incoming fanout and unbounded terminal image. It avoids recovering a long spelling from a completed pointer after the spelling’s input time has passed.

14.1 Exact checked language and routing contract

Fix a finite family $f_1,\ldots,f_k$ of total deterministic subsequential functions from nonempty binary words to nonempty binary words. Here this means a finite controller with a fixed initial output, a finite output word on each bit transition, and a finite final output determined by its ending state. Fix a common bound $c$ on every such output chunk. Empty transition chunks are allowed. The functions and $k,c$ are part of one fixed machine, independent of the input. They are not a supplied program, learned table, advice string or an unbounded family of ready handles.

Use section 12’s exact ordinary Horn syntax: the right clauses $(-01v,+1w);$, then the left clauses $(-00u,+01v);$, then $(+00a);(-1b);$, with nonempty arbitrary binary suffix names. Either implication block can be empty. Impose the checked restriction

$$S\subseteq\bigcup_{i=1}^k\{(v,f_i(v)):v\in\{0,1\}^+\}.$$

There is no bound on the number of names or on left fanout. For $k=1$ the right relation is functional; for larger fixed $k$ each right row may choose any subset of the displayed outputs. The machine rejects a right edge outside this union. It accepts exactly the well-formed, restriction-satisfying formulas that are satisfiable. This is a recognition theorem for a checked syntactic subclass, not a promise algorithm for arbitrary SAT.

The encoded length is unchanged:

$$N=\sum_{(v,w)\text{ records in }S}(9+|v|+|w|) +\sum_{(u,v)\text{ records in }R}(10+|u|+|v|) +11+|a|+|b|.$$

Record sums count duplicates. No separators, padding, supplied decomposition or extra processing phase are inserted. The finite sort parser is the one in section 12. The native-to-PEG consequence is for this language’s reversal only.

14.2 Check the right block and retain a domain mask

Maintain a capsule dictionary $D$ whose value at $v$ is a subset of $[k]$. Initially all values are empty. Its invariant after each right clause is

$$i\in D(v)\quad\Longleftrightarrow\quad(v,f_i(v))\text{ has actually occurred in }S.$$

On a right clause, traverse and suspend the $D$ update path while reading $v$. In parallel, run all $k$ finite controllers on those same bits. Enqueue each controller’s output into its own strict persistent FIFO. Enqueue initial and final chunks at the fixed phase boundaries; each has length at most $c$. The queue contents are binary symbols, not unbounded labels.

During $w$, compare each bit with each still-viable FIFO’s front and remove that front. An unequal bit or an empty FIFO disables that lane. At the end of $w$, a lane matches exactly when it has not been disabled and its FIFO is empty. If no lane matches, reject. Otherwise union the matching-lane mask into the old $D(v)$ and close its suspended path. Reset the fixed tuple of queue roots for the next record; discarded queue history is still charged.

This compares the entire generated spelling, including terminal outputs. It never compares addresses, hashes or unbounded strings in one operation. If two functions agree at $v$, the same actual edge enables both lanes. Conversely an enabled lane certifies an actual right edge. Duplicate clauses are idempotent. Right-block termination freezes $D$ permanently.

14.3 Build separate coherent target sets while names arrive

Maintain separate dictionaries $A_1,\ldots,A_k$, each mapping a source name to a target-membership dictionary. Separating the lanes is necessary: two simultaneous tentative insertions into one old root cannot simply be committed as if they had merged each other’s updates.

For a left record $(u,v)$, the bits of $u$ traverse and suspend the outer update path in each $A_i$. Obtain that lane’s current inner root, using a blank dictionary if missing. Start an inner insertion builder there. Reset each finite routing controller and feed its bounded initial output directly into that lane’s builder.

While the actual bits of $v$ arrive, traverse frozen $D(v)$ and run all routing controllers. Feed each output chunk directly to its own inner builder, one ordinary trie step per generated bit. On the delimiter, feed the bounded final chunks. The enabled mask $D(v)$ is now known. For enabled lanes, mark the inner tip present, close its capsule, and close the suspended outer capsule with that new root. For disabled lanes retain the old $A_i$ root. All their abandoned tentative frames remain included in the allocation bound.

Thus no old target name is replayed from a pointer. No alias is expected to follow future mutations. Every insertion starts from the current root for that source in that lane; later records use its new root. A missing $v$ commits nothing. Repeated left edges merely set an already true membership value. Proper-prefix names retain their payload and children under the capsule invariant.

Induction over left records gives the exact invariant

$$A_i(u)=\{f_i(v):(u,v)\in R\text{ and }i\in D(v)\}, \qquad \bigcup_{i=1}^k A_i(u)=\{w:(u,w)\in RS\}.$$

The first equality holds initially and each record adds precisely its enabled contribution. For the second, an enabled contribution is an actual right edge by the right-block invariant. Conversely every right edge has at least one matching lane, which is enabled. Colliding outputs or repeated contributions do not change the union.

The late source pin selects the $k$ inner roots $A_i(a)$ by its actual bits. The late target pin drives $k$ membership cursors by its actual bits. Accept at its final semicolon precisely when all $k$ terminal flags are absent. The invariant and the Horn composition lemma prove this is exactly satisfiability. Both pins are late, ordinary names, and may be missing or have arbitrary lengths.

14.4 Charged native realization and reuse

Initial chunks are executed at fixed starts of names; final chunks at their delimiters. The controllers have finitely many states; the mask has $2^k$ possibilities. The fixed tuple of outer tips, inner tips, roots and strict queues has fixed arity. A chunk of at most $c$ serial trie steps is a fixed finite batch, not an amortized or unbounded internal loop. Each step uses the local capsule/FIFO primitives established in section 12.2. Unrolling these fixed batches bounds all old-top addresses and all same-batch dependencies by constants depending only on the routing family. Guards use finite labels, child fields and emptiness, never identity, numerical addresses, metadata, timing or an unbounded counter.

Initialization is fixed empty storage and finite controller states. The simultaneous-record compiler therefore supplies fixed degree, fixed radius, finite control, chronological old-top semantics and one new physical scaffold node per actual input symbol, plus the base. All preparation, queues, tentative paths, discarded roots, retained receipts and query-created capsules account for $O_f(N)$ logical records. A binary pointer serialization costs $O_f(N\log(N+2))$ bits. There is no preprocessing before input, uncharged ready index, deadline extension, output expansion after EOF or latent traversal after the last symbol. Malformed or incomplete words reject; a right clause after the left phase rejects. Empty blocks and absent dictionary entries use the same schedule.

Retaining the $k$ product roots supports repeated separate endpoint queries in $O_f(|a|+|b|+1)$ charged work. This refers to separate hypothetical pin continuations, not conjoining all pins. It does not grant free selection among arbitrarily many historical product versions. Nor does it merge independently prepared left and right stores at zero cost: the left records are processed against the completed right domain index.

The construction proves a useful sufficient criterion: a fixed bounded family of routes whose target spelling is generated within the arriving intermediate name’s clock permits accumulation into coherent persistent target sets. The image and the number of contributing intermediate vertices may both grow. Identity, bitwise complementation and fixed bit duplication give unbounded-image examples. A finite union permits checked nonfunctional right rows. For example, one source may select all $2^n$ distinct length-$n$ names under identity routing. This satisfies neither a fixed left-fanout bound nor a fixed terminal-image bound, while it satisfies this theorem for the same fixed machine at every $n$.

The ingredient reused from classical computation is deterministic finite-state transduction; the containers and compiler are the Lab’s existing constructions. The written advance is the checked ordinary-clause schedule, domain masks, separate-lane coherence and late negative readout. No general transduction closure theorem is invoked, and no novelty or new root-claim admission is asserted.

14.5 Length preservation alone does not provide the routing clock

Here is a narrower failed-route result, distinct from recognition. Consider a deterministic online normalizer required to output each left edge’s literal substituted target name, in order, with at most $C$ output characters per input symbol and no EOF work. Even length-preserving functional right maps do not suffice for that contract.

For arbitrary $L$, let the completed right block contain the two edges

$$0^{L-1}0\mapsto0^L,\qquad 0^{L-1}1\mapsto1^L.$$

Present one left edge with a fixed short source and either of those intermediate names, followed by fixed short pins. The right block and the entire left prefix before the last intermediate bit are identical in the two inputs. The required target spellings disagree in their first bit. Thus a sequential literal normalizer cannot emit even the first target bit before that deciding input bit. Only a fixed number $q$ of input characters remain, independent of $L$. Its remaining output budget is at most $Cq$, whereas the target alone has $L$ bits. Choosing $L>Cq$ gives a contradiction. Headers or other fixed output prefixes do not alter it. The normalizer cannot retract output or emit alternative factored encodings under this contract.

The total output here is only linear in the input; the obstruction is its prefix deadline, not total length. This refutes that literal normalizer only. Indeed section 13 recognizes these finite-image examples natively with $K=2$. A compact representation or another readout contract is not ruled out.

The next decisive target remains an arbitrary right-first functional table with unbounded image, especially length-preserving tables whose target routing depends on the final intermediate bits. Can a persistent index answer late named pins without forward target replay, stale columns or an unbounded lane family? Test a backward or query-directed construction with a complete per-symbol schedule. The present positive theorem settles fixed online-routing subclasses; it neither decides arbitrary table substitution nor yields a lower bound against it.

14.6 Query-side routing handles a different unbounded class

A complementary theorem routes the late query instead of every insertion. Fix total nonempty-output subsequential functions $g_1,\ldots,g_k$ with the same bounded-chunk contract, but require the checked condition

$$S\subseteq\bigcup_{i=1}^k\{(g_i(w),w):w\in\{0,1\}^+\}.$$

Again the right block comes first, all names are ordinary, and left fanout and terminal image are unbounded. A right row can now have arbitrarily many targets, since a function $g_i$ can have an unbounded fiber. Each target has at most $k$ possible predecessors. This is a different restriction from forward routing, not an assumed inverse-closure theorem.

Prepare and validate. While the intermediate name $v$ of a right clause is read, enqueue its bits into a strict FIFO. At the target-name start, retain $k$ references to that completed queue; these become independent persistent consumption cursors. Traverse an update path in a target dictionary $E$ while reading the actual $w$ bits. In parallel run $g_i(w)$. Compare every generated bit with lane $i$’s next queued bit of $v$; mismatch or underflow disables that lane. Initial and final output chunks are compared at the fixed phase boundaries. At target termination, a lane matches exactly when it remains viable and its queue is empty. Reject if none matches. Otherwise union the matching mask into $E(w)$ and close its capsule. Therefore

$$i\in E(w)\quad\Longleftrightarrow\quad(g_i(w),w)\text{ actually occurs in }S.$$

Freeze $E$ at the phase change. Queue sharing here is immutable: each lane advances its own root; no cursor sees an updated version by aliasing.

Accumulate the left factor. Build one ordinary nested capsule dictionary $B(u)$ for membership of intermediate names in $R_u$. The actual $u$ bits select and suspend the outer path; the actual $v$ bits insert into its current membership root; the delimiter closes both. No substitution occurs during this phase and there is no fanout bound.

Answer the late pins. The source pin selects $B(a)$. At the target-pin start, retain $k$ cursors at this same frozen membership root. While the bits of $b$ arrive, look up $E(b)$ and run each $g_i$, routing its bounded output chunks into cursor $i$. Include initial/final chunks at their fixed boundaries. At the final semicolon reject exactly when

$$\bigvee_{i=1}^k\bigl(i\in E(b)\ \land\ g_i(b)\in B(a)\bigr).$$

This is equivalent to $(a,b)\in RS$: a successful lane supplies an actual right edge and a left predecessor; conversely every product witness has a matching lane by the checked right restriction. Negating this expression gives the SAT answer. Missing keys, colliding functions, duplicates and empty blocks are covered by the invariant.

There are at most $kc$ queue comparisons or dictionary steps on any target-name bit, one FIFO enqueue on each right intermediate bit, and a fixed number of closures or flag tests on delimiters. The same fixed initialization, constant root tuple, chronological bounded-address batch and $O_g(N)$ logical history proof applies. All right-block comparison storage and late-query allocations are charged; no target spelling is replayed after its delimiter. The physical compiler gives $N+1$ nodes and reversal-only PEG transfer as before.

A decisive directional example. Let $S$ be any finite subset of the graph of right cyclic rotation: for a nonempty word $v=xb$, its target is $bx$. This includes arbitrary finite collections with unbounded image. Right rotation cannot be a forward subsequential function: on the common prefix $0^{L-1}$, last bits $0$ and $1$ require different first output bits, so all $L$ output bits would have to fit into the bounded last transition and final chunk. However its inverse, left cyclic rotation, is subsequential. Store the first input bit in finite control, emit every later bit as it arrives, and emit the saved bit at the name’s delimiter. Section 14.6 therefore gives native recognition with unbounded left fanout for this checked right relation. The delayed first bit defeats a single exact forward subsequential route, while query-side routing succeeds. This is not a minimality claim: finitely many guessed forward routes with additional final-state guards are another possible mechanism, not excluded here.

For an example outside every fixed bound on right-row degree, let $g$ retain the first, third, fifth and subsequent odd-position bits. This is a total nonempty-output subsequential map. For all length-$2n$ targets $w$, include $(g(w),w)$ in $S$, and let one source select all length-$n$ intermediate names. Its left degree, right row degrees and terminal image all grow with $n$, while the same backward-route machine applies. A union of $k$ forward function graphs has right-row degree at most $k$, so no fixed forward family covers these complete right relations. This contrasts the two stated sufficient classes without claiming that no other forward algorithm exists.

Together the two constructions establish a two-sided sufficient routing criterion, not a characterization: bounded families of forward maps support coherent target-set updates, and bounded families of backward maps support query-directed predecessor tests. Neither the matching algebra nor monotone positive readout is the operative interface; exact ordinary-name membership and finite negation are used, with all routing and retained receipts charged. Independently prepared stores still require a paid input/export protocol.

The sharpened next test is a right block checked to satisfy $w=\operatorname{rev}(v)$, with arbitrary left fanout and unbounded image. Word reversal has no single exact forward or backward subsequential route: a last differing input bit determines the first output bit in either direction. No fixed-family index for this case is supplied here. The right pairs themselves can be checked with a stack, but that fact does not supply a coherent product index for late ordinary pins. Attempt a persistent reverse-name index, accounting for its creation, version routing and deadline. The absence of a construction from these criteria is not evidence of nonrecognition. Arbitrary functional tables remain the broader open target.

15. Arbitrary stored substitutions with compatible name lengths

Assessment 126, 7 October 2026. Written native theorem. The reverse-name test can be resolved by a stronger result: the right table need not obey any finite-state spelling rule. Bounded right-row size and compatible intermediate/target name lengths suffice. Left fanout, terminal image, source-name lengths and the number of right rows remain unbounded.

The mechanism is deferred installation with an exact pending overlay. A stored target spelling does not need to be inserted immediately when its pointer becomes available. The arriving intermediate name pays for the previous pending batch in the appropriate length range. Its own target spellings become the new pending batch. A query tests both committed entries and that bounded pending batch, so the final answer never waits for a flush.

15.1 Statement and ordinary input

For a nonempty binary name $z$, put $\lambda(z)=\lfloor\log_2|z|\rfloor$. Fix integers $d\geq1$ and $s\geq0$. Use exactly section 12’s right-first ordinary Horn records and late pins. Check these conditions on the actual right relation:

$$|S_v|\leq d\quad\text{for every }v, \qquad |\lambda(v)-\lambda(w)|\leq s\quad\text{for every }(v,w)\in S.$$

There is one deterministic native recognizer, for the chosen $d,s$, accepting exactly the well-formed formulas satisfying these conditions that are satisfiable. Arbitrary duplicate records are allowed. There is no restriction on left fanout or on the ratio between a source name $u$ and either $v$ or $w$. No name-length header, decomposition, ready handle, padding or preprocessing is supplied. The encoded length $N$ is the actual formula length in section 14.1; no symbols are added.

In particular, arbitrary length-preserving functional right tables satisfy $d=1,s=0$. Their contents are input data, not a fixed routing program. If the language must additionally check exact length preservation, compare a unary length stack collected during $v$ against the bits of $w$. To additionally check $w=\operatorname{rev}(v)$, push the actual bits of $v$ and pop/compare them against $w$, with exact exhaustion at its delimiter. These are bounded local operations in parallel with the construction. Thus the previously open checked reverse-name instance has a native recognizer with unbounded image and arbitrary left fanout. The PEG consequence remains reversal of the complete encoded language, not an assumed closure under changing individual names.

15.2 Prepare paid target-word receipts in the right block

The right dictionary $D(v)$ stores a receipt containing a Seen dictionary, a count at most $d$, and a tuple of at most $d$ target-word FIFO roots with offsets $\lambda(w)-\lambda(v)\in[-s,s]$. These are pointers to spellings constructed while their actual bits arrive. The tuple does not contain free names, numeric addresses or an unbounded vector.

During a right record, the bits of $v$ traverse and suspend the outer $D$ path. The bits of $w$ traverse the receipt’s Seen trie while being enqueued into a fresh strict FIFO. At the delimiter, the Seen flag decides whether this is a duplicate. A new target is appended only if the distinct-target count remains at most $d$; the Seen and outer paths close by bounded capsule operations. A duplicate adds no tuple entry. No pointer-identity test is used.

A unary doubling clock measures each name’s class. After length 1, its remaining interval has one cell; each further bit pops one cell and pushes two onto the next interval builder. Exhaustion promotes that builder. Boundaries are 2,4,8,…, and a unary class counter gains one cell at each boundary. While reading $w$, pop one cell of a saved copy of $v$’s class counter at each such boundary. If exhausted, retain only a saturated finite excess counter. At the delimiter, inspecting at most $s+1$ residual cells or this excess determines whether the offset is in $[-s,s]$ and, if so, its exact finite value. An out-of-range edge rejects, including a duplicate. The logarithm describes the clock; it is not an arithmetic instruction of the machine.

After the right block, $D$ is frozen. Every captured FIFO is ready for strict front/removal operations by the established queue invariant. Its construction, scheduling state and retained history were paid for during the right input. A missing row is an empty tuple.

15.3 The per-source index: committed sets plus pending words

Each source $u$ has an independent index $I_u$. Its directory has one bucket for each class $j\geq0$, with an implicit blank suffix. Bucket $j$ contains:

• a committed capsule membership trie $T_j$ for target names of class $j$;
• a pending tuple $P_j$ of at most $d$ target-word FIFO references, also of class $j$.

Its logical set is $T_j\cup P_j$, whether or not the pending insertions have been installed. Repeated words are harmless. Distinct-source indices and different buckets need not be physically up to date together. All completed roots and pending tuples are immutable.

Installing one pending word of length $h$ into the current $T_j$ takes at most $a(h+1)$ fixed local operations, for a uniform constant $a$: consume its FIFO, descend with capsule frames, mark the terminal and close the capsule. Install the at-most-$d$ words sequentially into the evolving committed root, then clear the pending tuple. This preserves the logical set. A partially executed installation is private work; its partial root never replaces the bucket before the entire batch finishes.

The directory is the existing one-child capsule list from the component-local length-scale construction. A FIFO of frames retains the prefix behind the active window. The window and untouched suffix have separate roots. Moving one position exposes only one frame; closing around a fixed explicit window is bounded work, with no return walk through the directory. This is the same pointer-payload extension used in section 12, not a random-access array of buckets.

15.4 Service the window before the receipt is known

The outer dictionary $A(u)$ holds $I_u$. During a left clause, the actual bits of $u$ select its current index and suspend the outer update path. During the actual bits of $v$, simultaneously look up frozen $D(v)$ and service the index’s length-class directory.

At a boundary $|v_{\mathrm{prefix}}|=2^j$, maintain the window

$$\max(0,j-s),\ldots,j+s$$

with every old pending batch in that window completely installed. At the first bit, servicing buckets 0 through $s$ is a fixed amount of work: their pending words have length below $2^{s+1}$ and there are at most $(s+1)d$ of them. Constants may depend on $d,s$.

During the next $2^j$ arriving bits, a separate worker prepares the next rightmost bucket $j+s+1$. Its at-most-$d$ pending targets have length below $2^{j+s+2}$, so its whole installation costs at most

$$ad(2^{j+s+2}+1) \leq ad(2^{s+2}+1)\,2^j.$$

A fixed service rate $ad(2^{s+2}+1)$ per actual bit therefore completes the batch before the next boundary. At that boundary promote the completed bucket and shift the window one position. If the name ends before promotion, discard the unpromoted speculative job, complete or partial, and retain that bucket’s original committed root and pending tuple. All discarded work remains charged to the symbols that executed it. Completed window service is retained.

At the delimiter, $D(v)$ reveals at most $d$ target-word references and their finite offsets. Each target bucket is now in the serviced window because the right-edge condition was checked. Partition this fixed tuple by its stored offsets and place each subtuple into that bucket’s now-empty pending slot. Close the fixed window/directory capsule and the suspended $A(u)$ path. There is no stored-word traversal at this delimiter, and no overwrite of an unfinished old batch. A missing $v$ schedules nothing. Repeated left clauses may schedule repeated insertions, which are idempotent.

The key point is that the destination range is predictable from the arriving intermediate’s length before its exact target spelling is available. Bounded row size limits the work waiting in each selected bucket. No coherence between an old alias and a later version is assumed: each record opens the current $I_u$, services it, and commits its new root.

15.5 Late target lookup sees pending answers immediately

The positive pin’s actual bits select the completed descriptor $I_a$. During the negative pin $b$, select the bucket for $\lambda(b)$ without waiting for the end of $b$.

At length $2^j$, a current reader for bucket $j$ has consumed the entire prefix. It traverses a snapshot of $T_j$ while comparing the same bits with every word in its saved $P_j$, using at most $d$ independent FIFO cursors. Exact exhaustion distinguishes a match from a proper prefix. The logical membership answer is the committed terminal flag OR any exact pending match.

During the next $2^j$ bits, an ahead reader for bucket $j+1$ starts with a retained FIFO of the current prefix. Append new bits to its replay queue and consume up to two queued bits per actual bit, performing both committed lookup and pending comparisons. It starts $2^j$ bits behind; at the next boundary it is fully caught up, since $2^{j+1}$ bits have been processed in $2^j$ two-step opportunities. Promote it and prepare the next ahead reader. If the name ends early, discard the ahead reader. Only the current and ahead readers exist, and a persistent copy of the prefix queue means copying a root, not copying the word in one step. The directory is traversed serially at class boundaries.

Querying does not require installing pending words. In particular, a very short source pin followed by a short target pin can answer immediately even if distant buckets retain very long pending targets. Those other length classes cannot contain the query name. The current reader’s mask and trie flag are ready when $b$ ends. Accept at the final semicolon exactly when the logical target membership is false.

15.6 Invariant, resources and reuse

After every completed left record, the exact invariant is

$$\bigcup_{j\geq0}\bigl(T_{u,j}\cup P_{u,j}\bigr) =\{w:\exists v\ ((u,v)\in R\land(v,w)\in S)\}.$$

Initially both sides are empty. Window servicing changes no logical membership. The new receipt adds exactly the actual right row selected by the current left edge. This proves the invariant inductively, including duplicates, absent rows and empty factors. A late query selects exactly its own length class and reads its committed-plus-pending predicate. The Horn composition lemma proves the acceptance condition.

The worker has one pending tuple, one current word cursor and one current insertion builder. All roots, window fields and masks have fixed arity depending on $d,s$. The directory prefix, clocks and word contents are immutable bounded-degree records, not unbounded labels or control variables. The initialization is the fixed empty representation. Every guard follows bounded old-top paths; each fixed-rate macrostep unrolls into a fixed batch with declared same-batch pointers. There are no address, identity, metadata, timing or control-flow side channels.

The existing simultaneous-record compiler therefore supplies fixed degree, fixed radius and finite control, with exactly $N+1$ physical nodes. All preparation, right-word receipts, installers, speculative readers, discarded partial work, directories and retained versions count toward $O_{d,s}(N)$ logical records. Explicit binary pointer serialization is $O_{d,s}(N\log(N+2))$ bits. No EOF work or supplied decomposition is charged elsewhere. Malformed, incomplete or out-of-phase inputs reject using the same finite syntax controller.

The resulting row descriptor is itself a completed predicate despite pending physical writes. A fixed number of such frozen descriptors can be selected and queried in parallel, as in section 12’s bounded-selection mechanism: each target bit drives its own fixed current/ahead readers. This permits bounded reuse of these new outputs without first materializing or flushing them. It does not grant arbitrary past-version selection or an uncharged merge of independent stores.

This theorem uses established capsule/FIFO and length-bucket scheduling machinery. The new written construction is its application to arbitrary stored right-row substitutions, with only the intermediate-to-target class span constrained. It imposes no component-size bound and no source-to-target length constraint. No novelty claim or new root CLAIMS.yaml admission is made.

15.7 What this resolves, and the remaining boundary

For $d=1,s=0$, no target spelling has to be generated from its intermediate spelling by a fixed transducer. Arbitrary same-class functional tables are allowed, including all length-preserving tables and their arbitrary finite permutations. The reverse-name test is therefore resolved without a reverse-name trie insertion algorithm: the right block already supplies the target’s ordinary spelling, and the pending overlay bridges its late availability in the left block. Treating that paid stored spelling as unavailable had made the previous formulation unnecessarily narrow.

The length-range condition is load-bearing for this scheduler. If $v$ is short and its target lies arbitrarily many classes beyond the serviced window, repeated short left records can request long insertions before previous ones have finished. Publishing those as one pending slot would lose uninstalled answers. Keeping an unbounded pending list defeats the bounded simultaneous-comparison query proof. These are failures of those implementations, not lower bounds against every index. If targets lie far below the intermediate class, all earlier buckets may have been serviced, but choosing an arbitrarily distant one at the final delimiter is not supplied by the fixed-window access proof.

A quantitative failure of the literal installer makes this precise. Give $m$ distinct length-$\ell$ intermediate names distinct length-$L$ targets in the right block, with $m\leq2^\ell$. Then select them in $m$ left records for one fresh source $u$. Consider this implementation’s contract: start its row index empty, install each selected word by an $L$-step trie traversal, and retain at most $d$ uninstalled target words in their one common length bucket. By the last left-record boundary, at least $m-d$ words must be fully installed. Any fixed service budget $C$ per left-input symbol would require

$$(m-d)L\leq C m(10+|u|+\ell).$$

For $m>d$ and sufficiently large $L$ this fails. This grants the installer even free selection of the correct distant bucket, so merely repairing directory access does not fix its backlog. It is a bound on this fresh-row, explicit-installation contract, not a native lower bound: the long right block’s paid preparation and a shared representation could support another algorithm. The image has $m$ distinct targets; a single repeatedly selected long target is deliberately not the claimed obstruction.

The next decisive target is therefore arbitrary cross-scale functional substitution, with unbounded image and left fanout, still under right-first ordinary input. Seek a query-directed pending representation or a charged directory route that handles arbitrarily short intermediate names selecting arbitrarily long target names, and the converse. Preserve the finite-image control: repeatedly selecting one very long target alone is already easy, so it is not an impossibility witness. A useful negative result must quantify over a genuinely unbounded selected image and exclude uncharged addressing. The imported algebraic bounds and independent-preparation theorem retain their own hypotheses; none automatically applies to this jointly constructed index.

16. Checked prefix ambiguity gives timely, version-coherent readout

Written native sufficient-condition theorem, 7 October 2026. Fix an integer $K\geq1$ and a deterministic finite-state alignment clock $\chi$. On each ordinary target-name bit the clock advances and either ticks once or does not tick. It resets at the beginning of each target name, and has no end-of-name ticks. The clock is part of one fixed machine, not advice supplied with a right table.

Write $t_\chi(p)$ for its number of ticks on the binary word $p$. For a nonempty intermediate name $v$, let $\eta_n(v)$ be its first $n$ symbols after padding its end forever with a new mathematical symbol $\bot$. The actual input alphabet remains the ordinary fixed binary-name clause alphabet. For the right relation $S$, define

$$\nu_\chi(p)=\left|\{\eta_{t_\chi(p)}(v):(v,w)\in S,\ p\text{ is a prefix of }w\}\right|.$$

Consider the same right-first Horn input as above: right clauses $(-01v,+1w)$, then left clauses $(-00u,+01v)$, then the late pins $(+00a),(-1b)$, with the established punctuation. Require

$$|v|\leq t_\chi(w)\quad((v,w)\in S),\qquad \nu_\chi(p)\leq K\quad(p\ne\epsilon).$$

There is a single deterministic native machine recognizing exactly the well-formed inputs satisfying these two conditions whose pinned formula is satisfiable. Both conditions are checked during the actual right block. There is no bound on left fanout, the right relation’s image, a right row’s size, source-name length, or the ratio of target length to intermediate length. The machine has fixed degree, radius, labels and control depending on $K,\chi$, constant initialization, one physical node per actual input symbol, and a decision by the final symbol. This is a subclass theorem, not a necessity criterion or a general native SAT theorem.

16.1 A decomposition learned and checked from ordinary input

Build two persistent capsule tries during the right block. The joint trie $J$ has a fixed eight-letter logical edge alphabet. A letter is a pair consisting of the arriving target bit and one of four labels: source bit 0, source bit 1, padding $\bot$, or no emission $\varepsilon$. Encode each such edge by three binary trie edges. At a ticking target step, dequeue one actual source bit if one remains; otherwise use $\bot$. At a non-ticking step use $\varepsilon$ and do not dequeue. The source FIFO was prepared one bit at a time during the immediately preceding ordinary $v$ field.

Each complete joint-letter prefix has a present flag and a terminal flag. The present flag records that some right row follows that prefix; the terminal flag records that a complete right row ends there. Missing paths are blank. A second trie $P$, keyed by target bits alone, stores a counter in $\{0,\ldots,K\}$ at every nonempty target prefix.

While reading a target bit, advance the current $J$ builder by its three fixed edges and inspect the old present flag. If this joint prefix is new, increment the counter at the corresponding $P$ prefix, rejecting on overflow. Mark the joint prefix present, preserving any old terminal flag. If the prefix was already present, leave its counter unchanged. At the target delimiter reject if the source FIFO is not empty; otherwise mark the final joint prefix terminal and close both builders.

These are not deferred internal-node writes. A capsule builder saves the current payload, chosen direction and untouched sibling whenever it descends. Change the current payload before its next descent, so the saved frame already holds the updated prefix flag or counter. Closing installs the modified final payload beneath that queue of frames. The pointer-payload capsule interface from section 12 applies unchanged. A fixed number of descents, observations, FIFO operations and payload changes occurs per actual target bit. The right delimiter performs only bounded closures and an empty-queue test. Earlier versions remain immutable.

For a fixed target prefix $p$, the clock’s emission positions are determined by $p$. Hence its distinct joint prefixes are in bijection with the distinct strings $\eta_{t_\chi(p)}(v)$ contributed by right rows extending $p$. Inductively $P(p)=\nu_\chi(p)$ for all right rows seen so far. New distinct prefixes increment exactly once; duplicate clauses do not increment. Counts can only increase, so early overflow rejection is sound. FIFO exhaustion checks the other condition. No sorting, supplied decomposition, precomputed inverse table, name comparison by pointer identity, or end-of-block rebuild is used.

16.2 Mark selections under the spelling that actually arrives

Freeze $J$ after the right block. During the left block build the ordinary nested membership trie $A(u)(v)$, marking exactly the pairs in $R$. Suspend the outer source-path builder while the actual intermediate bits drive its inner builder, then close both capsules at the clause delimiter. This is the established direct pointer-payload update, with no traversal of a stored target word.

The positive pin’s actual name $a$ selects the completed current row $A(a)$. Capture that root. In particular, the reader does not follow aliases into an older source version. A missing source selects the blank row. The snapshot has exactly the intermediate marks of the completed left block.

16.3 A bounded family of coupled cursors

Start the target query with one pair of cursors: the root of $J$ and the captured root of $A(a)$. A finite ended flag is initially false. Each arriving target bit advances the same clock. At a non-tick, follow only the joint edge with label $\varepsilon$, leaving the source-row cursor unchanged. At a tick, try the three edges labeled 0,1,$\bot$. For a bit label, advance the source-row cursor by that bit; for $\bot$, retain that cursor and set the ended flag. After padding has started, no further source bit is allowed. Missing joint prefixes are discarded.

After every target prefix $p$, the surviving cursor pairs correspond exactly to the joint prefixes above $p$. A source-row cursor has consumed precisely the non-padding emitted intermediate prefix, and freezes when that intermediate ends. The width check guarantees at most $K$ pairs. At most $3K$ candidates are inspected in one step and compacted into $K$ fixed slots using a finite presence mask. There is no address comparison or uncharged deduplication: distinct joint-prefix paths remain distinct after extension, so no candidate is reached from two different predecessors. Equal source-row cursors are neither compared nor merged.

At the target delimiter, take the OR of the at-most-$K$ predicates

$$\text{joint cursor is terminal}\ \land\ \text{source-row cursor has a terminal mark}.$$

A terminal joint path is exactly an actual right pair $(v,b)$, and its row cursor is exactly at $v$. This includes $|v|=t_\chi(b)$, where no padding has yet appeared, and shorter $v$, where it has. A proper prefix of a stored target is not accepted unless its own terminal flag is set. Thus the OR is exactly $\exists v\,[R(a,v)\land S(v,b)]$. The pinned Horn formula is SAT exactly when that already available bit is false. Negative readout is one finite Boolean complement; it is not an uncharged global absence test. Final punctuation requires no traversal or flushing.

16.4 Resource contract and reuse

All roots, masks and temporary tuples have fixed arity. Counters are finite labels bounded by the machine constant $K$, not unbounded native integers. Joint labels are an internal constant alphabet, not a growing input alphabet. Name storage, builder frames and FIFO contents are immutable bounded-degree records. Queries create only boundedly many logical cursor records per input bit; discarded alternatives and all preparation are included. The simultaneous-record compiler gives fixed degree and old-top observation radius, exactly $N+1$ physical nodes and $O_{K,\chi}(N)$ logical records; explicit binary pointer serialization is $O_{K,\chi}(N\log(N+2))$ bits. Here

$$N=\sum_{(v,w)\text{ right occurrences}}(9+|v|+|w|) +\sum_{(u,v)\text{ left occurrences}}(10+|u|+|v|) +11+|a|+|b|$$

for the established record spelling. Repeated records count each time. No virtual ticks, padding in the input, readiness handles, nonuniform tables, preprocessing outside these symbols, or EOF work is available. Malformed and out-of-phase words reject. Timing and control are deterministic functions of bounded local observations and the actual symbol, with no identity or address side channel.

The captured row can be any completed version selected by a charged ordinary source lookup. A fixed number of such completed predicates can be read simultaneously with separate cursor tuples. This preserves bounded selection and reuse without materializing all composed target sets. It does not supply arbitrary selection among past roots or an uncharged merge of independently prepared stores. Native recognition gives the corresponding PEG for the reversal of this complete checked language, not automatically for its forward spelling.

16.5 What the criterion adds and what it misses

With a tick on every bit and $K=1$, take any depth-$h$ binary prefix-tree automorphism $\pi$ supplied through the right table, and pairs $v\mapsto\pi(v)0^{L(v)}$ for all $h$-bit names $v$, with arbitrary nonnegative $L(v)$. Every target prefix determines a unique emitted source prefix, so the width is 1. The construction handles arbitrary input-defined choices of $\pi$, unbounded images and arbitrarily long expansions. Neither $h$ nor a tree decomposition is provided separately. The actual target spellings pay for their construction.

A second fixed clock ignores the initial zeros and the first 1, then ticks on each later bit. It handles the corresponding tables $v\mapsto0^{L(v)}1\pi(v)0^{E(v)}$ at width 1. Before the first 1 every emitted source prefix is empty. Afterwards inverse prefixes are unique. Those initial zeros are genuine name bits, not inserted working time; the clock merely specifies which source cursor advances their actual steps may perform.

The condition is not necessary. For all $h$-bit names with the length-preserving reversal map, the all-ticking clock has maximum prefix width $2^{\lfloor h/2\rfloor}$. Any clock satisfying the length condition on those length-$h$ pairs must tick on every bit of each such target, so clock choice does not remove that width. Yet section 15 already recognizes these arbitrary length-preserving tables. Bounded prefix ambiguity and the earlier pending-overlay mechanism are different sufficient conditions. No bounded inverse-fibre condition alone proves this finite-frontier invariant: even these bijections have unbounded prefix ambiguity.

The explanatory advance is therefore a checked, data-built inverse program whose number of simultaneously possible access prefixes is bounded. It couples the right relation to the current source marks before their late endpoint deadline, resolving the terminal-only inverse failure for this subclass. It needs neither a fixed forward/inverse spelling transducer nor a preinstalled materialized composition. The unrestricted injective expansion case, contraction, and arbitrary relation composition remain open. The next comparison should ask how this bounded-frontier readout composes with pending overlays, and which primary transducer results supply a larger resource-preserving class. No necessity, novelty, imported-port-bound transfer or new root claim admission is asserted.

17. Combining pending words with bounded-prefix readout

Assessment 129, 7 October 2026. Written supporting consequence of sections 15–16, informed by a dedicated two-paper proof review. This is a sufficient condition for the same checked, right-first Horn language. It is neither a characterization nor a new root claim admission.

17.1 What transducer proofs contribute

Jecker–Filiot, Multi-Sequential Word Relations, 2015 preprint, Theorem 6 and its appendix, characterize finite unions of sequential functions by weak twinning. Determinisation retains residual output after removing common prefixes. At decreases of accessible component rank, weak determinisation splits and resets residuals; bounded residuals and finitely many component paths give finitely many sequential machines. Conversely, pumping a violating loop yields incompatible delays across more inputs than finitely many sequential components can cover. The bounds depend on the fixed transducer. This supports section 14 when the resulting finite family is fixed in advance. It does not make a decomposition of an input-sized table machine-constant. We do not use the paper’s separate advice-enabled constant-memory model as our native resource contract.

Reynier–Villevalois, Sequentiality of String-to-Context Transducers, 2019, with the full preprint proofs, allow output contexts acting as $c[x]=l x r$. Theorem 11 relates sequentiality, contextual twinning and a factor-distance Lipschitz condition. Synchronized loops are either commuting around a primitive word or noncommuting and aligned. The determinisation records bounded contexts and synchronized histories; after the aligned case, two ordinary twinning arguments bound the left and right residuals. Theorems 25–26 establish finite determinisation and decidability. Contexts can express reversal, unlike append-only output. But producing a context is not the operation of reading a current persistent membership dictionary along its represented word. That additional action still needs a charged schedule.

Thus we combine the two already charged access constructions, rather than interpreting compressed output as free readout. The complete proof-path comparison and scope audit are retained in assessment 129’s review.

17.2 A checked mixed condition

Fix constants $d\geq1$, $s\geq0$, $K\geq1$ and one finite-state alignment clock $\chi$ as in section 16. Write $\lambda(x)=\lfloor\log_2|x|\rfloor$ for nonempty binary names. Partition the actual right relation, without input annotations, by

$$S_{\mathrm{near}}=\{(v,w)\in S:|\lambda(v)-\lambda(w)|\leq s\}, \qquad S_{\mathrm{far}}=S\setminus S_{\mathrm{near}}.$$

Check at most $d$ distinct near targets per intermediate $v$. On the far part, check exactly section 16’s two conditions: every $v$ is exhausted by the clock on $w$, and every target prefix has at most $K$ distinct padded intermediate prefixes. There is no degree bound on far rows and no ambiguity bound on near rows. The clock and constants belong to one fixed machine, not to advice extracted from a particular table. Far contractions fail the exhaustion test; near contractions within the fixed class range remain allowed.

Supporting composition proposition. The SAT language with these checked conditions, the ordinary right-first clauses of sections 15–16, arbitrary left fanout and late ordinary endpoint pins has a native recognizer. Both kinds of edge may occur in any order in the right block and in the same intermediate row. No partition, ready handles, sorting or extra input time is supplied.

17.3 Construction and the late-choice issue

For a right record $(v,w)$, maintain the two previously committed roots: the near receipt directory and the far paired/projection tries. Actual $v$ bits prepare the source FIFO and the suspended near-row path. Actual $w$ bits run both bounded builders from those roots. They also run the existing length-class comparison. The final class comparison selects which provisional root to retain.

In the near builder, retain at most $d$ distinct target receipts, with the membership trie and paid spelling FIFO from section 15. A provisional degree violation is a finite error flag, not an immediate global rejection. In the far builder, update paired-prefix presence and projection counters before saving their path frames, as in section 16. Saturate provisional counters at $K+1$ and latch an overflow flag. Source exhaustion is checked at the target delimiter. Again, these are provisional failures until the class is known. A terminal flag can be installed even on a provisional branch destined for rejection or disposal; it is not visible through the committed root.

At the delimiter, if the edge is near, commit only its valid near receipt root and ignore far errors. If it is far, commit only its valid paired/projection roots and ignore near errors. If the selected builder failed, reject. The other provisional structures are abandoned by dropping their boundedly many root pointers. They need no traversal or rollback. In particular, a near reversal edge may overflow a provisional far prefix counter, and a far edge may exceed the provisional near degree: neither is a reason to reject the other class. A near contraction may leave source bits unconsumed in the far builder. This is also harmless when that whole alternative is discarded.

Inductively the committed near root contains exactly the accepted near edges, and the committed paired/projection roots contain exactly the accepted far edges. Immutable provisional updates cannot contaminate either earlier root. Duplicate edges are idempotent in their selected class. Distinct classifications of the same pair are impossible because the partition uses the actual lengths. Only bounded flags, saturated counters, cursor families and suspended builders are active at once; unbounded paths remain in charged immutable storage.

After the right block, freeze these roots. During each actual left record $(u,v)$, run section 15’s near pending-overlay updater and section 16’s direct current-row mark updater in parallel. They use separate roots, so no simultaneous updates race on one old dictionary version. The outer $u$ paths remain suspended while $v$ arrives. A missing near receipt schedules no words; recording $v$ for the far reader is still valid. All right preparation is already complete.

The late source pin selects both current source descriptors. The target pin drives the near current/ahead bucket readers and the far bounded coupled cursors in parallel. Accept the product entry precisely when either answers yes:

$$(RS)(a,b)=(RS_{\mathrm{near}})(a,b)\lor(RS_{\mathrm{far}})(a,b).$$

The pinned SAT answer is its complement, as earlier. Each reader consults the selected source’s current version, including logically completed pending near writes. Neither reads an alias to a superseded row. Their fixed final Boolean combination fits the same terminal-symbol budget; no EOF flush is introduced.

The fixed parallel batch has constants depending only on $d,s,K,\chi$ and the established primitive implementations. The old-top compiler therefore preserves fixed degree, radius, labels and control, with one physical node per actual input symbol after initialization. Total logical work and storage, including discarded provisional records and retained snapshots, are $O_{d,s,K,\chi}(N)$. This accounting includes name routing, all old observations, FIFO preparation, allocation and output. It does not assume machine integers, free addresses, pointer identity, timing channels or uncharged preprocessing. The PEG consequence remains reversal of the complete checked language.

17.4 Why the combination is larger

For all binary words $x$ of length $h$, take the functional injective table

$$0x\mapsto0\operatorname{rev}(x),\qquad 1x\mapsto1x0^{h^2}.$$

The first lane is near with $s=0,d=1$; the second is far for sufficiently large $h$ and has prefix width 1 under the all-ticking clock. The mixed criterion uses fixed $d=K=1,s=0$. The whole table has unbounded length-class span, so no fixed section 15 class bound covers this family. The first lane has growing reversal prefix ambiguity, so no fixed section 16 width bound covers the whole family either. Any clock satisfying exhaustion on all first-lane words of length $h+1$ must tick at every position along them; changing to another permitted clock cannot remove this witness. These are failures of those whole-table sufficient hypotheses, not lower bounds against other recognizers. The zeros are actual identifier bits included in $N$; no unused padding or extra symbols are appended to obtain work time.

17.5 Evidence and remaining frontier

The independent set-relation oracle in tools/research/check_hybrid_composition.py checks the immutable transaction model on 6149 contract/order cases, 6498 retained source versions and 152136 queries. It includes discarded overflow, discarded source-exhaustion failure, duplicate edges, internal prefixes, absent sources, a non-ticking clock and five functional mixtures. The finite mixtures use a longer zero suffix to place small examples firmly in the far class. Python clocks, tuple queues and directory copies are semantic models, not native timing evidence. The general resource claim rests on the schedules above and the prior primitive proofs.

The useful boundary has sharpened: near arbitrary stored names can be serviced by bounded pending batches, and far names can be read through bounded inverse-prefix ambiguity. What remains is an input-defined injective far-expansion family with unbounded inverse-prefix ambiguity, after allowing a fixed alignment clock. A compact context program alone does not settle it. The next decisive test is whether a bounded collection of pending contexts admits current-version membership action during actual endpoint input, or whether a precisely stated such action contract fails. Existing reversal, finite-image, affine, replay, causal and unary-cubical controls remain available. This review and direct combination do not constitute an additional substantive mathematical count.

18. Checked finite-fibre normalization preserves timely reuse

Assessment 130, 7 October 2026. Written native sufficient-condition theorem. The representation can shorten names without forgetting which original target a future query names. This resolves a far-expanded reversal test left outside section 17. It does not settle arbitrary functional tables or claim that compressed contexts act for free.

18.1 Exact contract

Fix one partial subsequential map $g:\{0,1\}^+\rightharpoonup\{0,1\}^*$, constants $K,d\geq1$ and $s\geq0$. Its finite control, initial output, transition outputs and final output are fixed with the machine. Erasing transitions are allowed; outputs are binary words. Let $T$ be the set of distinct actual target names occurring in the completed right relation $S$. Check all of the following from ordinary input:

1. Every $w\in T$ is in the domain of $g$ and $g(w)$ is nonempty.
2. For every key $z$, at most $K$ distinct names in $T$ satisfy $g(w)=z$.
3. Each intermediate name $v$ has at most $d$ distinct normalized targets $g(w)$ with $(v,w)\in S$.
4. Every such edge satisfies $|\lambda(v)-\lambda(g(w))|\leq s$, where $\lambda(x)=\lfloor\log_2|x|\rfloor$.

Then the same right-first ordinary Horn SAT language, with unrestricted left fanout and late ordinary endpoint pins, has a native recognizer. Original target lengths, their ratios to intermediate lengths, the size of $T$, and the table size are unbounded. Each actual right row has at most $Kd$ distinct targets, a consequence of the conditions rather than an omitted restriction. Neither the fibres nor a partition are supplied. The conditions are independent of right-record order; the implementation assigns temporary finite lane numbers by first occurrence.

The constants describe one fixed recognizer for all admissible inputs. This is not permission to choose $g$ after inspecting a table. The map need not be globally injective or finite-to-one: only its fibres on the actual target set are checked. The case $K=1$ is particularly useful.

18.2 Discovering fibres without comparing stored names

Maintain an immutable dictionary $E$ on full original targets, whose terminal payload is a lane in $\{1,\ldots,K\}$, and a dictionary $C$ on normalized keys, whose terminal payload counts distinct original targets assigned to that key. Actual target bits traverse $E$. The fixed transducer’s emitted bits simultaneously traverse $C$. Both paths start from their last committed roots and close in bounded work using the established capsules. No reverse lookup, hash, address comparison or identity test is needed.

At the target delimiter, an existing terminal of $E$ supplies that target’s previous lane. For a new target with key $z$, assign lane $C(z)+1$, rejecting if it exceeds $K$, and update both terminal payloads. A duplicate target does not increment $C$, even when it occurs under a different intermediate. Determinism of $g$ ensures that the duplicate belongs to the same key as before. By induction, $E$ assigns distinct lanes precisely among the distinct actual targets in each fibre. The same finite lane number may be reused for entirely different keys.

A separate normalized right-row validator runs on $(v,g(w))$ and checks conditions 3–4 using section 15’s right-receipt construction. This validator sees every right record, so its degree bound is global across lanes. Its acceptance implies the corresponding bound in each lane. Domain and nonempty-output failures are rejected; all counters saturate with a finite overflow flag.