Late values: unique successful prediction still exceeds deterministic scaffolds

5 October 2026. Written construction and consequence of the previously established late-input circuit obstruction.

The ordered XOR-circuit language $K$ from the propagation and replay result has a useful further distinction:

$$K\notin\mathsf{SA},\qquad K\in\mathsf{USA}.$$

Here $\mathsf{USA}$ means unambiguous nondeterministic scaffolding recognition, defined below. Every accepted input has exactly one accepting computation. The completed input determines every circuit value uniquely; nevertheless, its values can arrive too late for a deterministic native recognizer. Prediction succeeds without adding a replay or changing the formula encoding.

This gives $\mathsf{SA}\subsetneq\mathsf{USA}$ for that precise extension of the native model. The main contribution is the explicit circuit witness and the explanation of its timing obstruction. The nondeterministic extension does not change the meaning of ordinary deterministic scaffolding recognition or PEG recognition.

Same input, different availability

Names are literal nonempty binary words, with leading zeros significant. Records are X(u,v,t);, meaning $t=u\mathbin\oplus v$, and T(u);, F(u);. Every symbol counts toward length $N$. Malformed words are rejected; the empty conjunction is accepted. There is no supplied ordering certificate, variable handle, padding, preprocessing or extra input-end step.

A word is in $K$ exactly when:

1. Each gate output has a unique producer.
2. Every gate operand is either an output of a strictly earlier gate, or a variable never produced by a gate and pinned somewhere in the complete word.
3. All pins are mutually consistent, including pins on otherwise unused variables.
4. Evaluating gates in their recorded order satisfies every output pin.

Source pins may follow their uses. Self-reference and use of a future producer violate condition 2; repeated operands do not. For example, X(0,0,1);F(0);F(1); is accepted, while X(0,0,1); is rejected because its source is never pinned.

The earlier negative theorem applies to this exact $K$: a row-major matrix-to-XOR construction would turn a deterministic native recognizer into a fully adaptive inner-product data structure with logarithmic coordinate-update and final-query costs. Ko’s lower bound excludes that combination. Its input accounting is $b=1+n+n^3$ and $N=\Theta(n^3\log n)$, with all initialization and history charged. We use that completed result rather than claiming a new lower-bound technique.

The nondeterministic model

Start with the native definition of Loff–Moreira–Reis: fixed finite control and labels, fixed degree and observation radius, one base node, one immutable new node per input symbol, and acceptance determined by the final control state. Replace the finite transition function by a finite relation of legal native actions. A word is accepted if a computation accepts. A machine is unambiguous if every word has at most one accepting computation.

Each computation individually has exactly $N+1$ physical scaffold nodes. Alternatives are computations, not a free store of parallel branches inside a deterministic machine. Transitions still have no physical pointer-equality test, numeric addressing, old-node mutation, external advice or post-input cleanup.

A dictionary and one outstanding-obligation stack

Use the proved serial finite-payload dictionary. Its path-capsule invariant supports arbitrary updates of a fixed finite terminal payload; unary intersection was one application, not a restriction on the dictionary. Each comma or closing parenthesis commits the current terminal and resets the next traversal within a bounded batch.

For each name store four finite fields:

Initially $P=U=0$ and $M$ is unpinned. A separate immutable unary stack counts source variables that have been predicted but not yet pinned. Its cells carry no variable identity. Push, pop and emptiness inspect or allocate a bounded number of records. Pins can arrive in any order: the stack represents a count, not a last-in-first-out order of obligations.

At an operand delimiter: if $P=1$, use $V$. Otherwise, if $U=1$, reuse $V$ even when the pin has not arrived. If neither flag is set and $M$ is a singleton, take its value and set $U=1$. In the remaining unpinned case, choose one bit, store it in $V$, set $U=1$, and push one outstanding obligation. This is the only nondeterministic action.

At the output delimiter: reject if $P=1$ or $U=1$. Otherwise compute the gate from its two operand bits, retained in finite control, check any existing pin, and store $P=1$ and the computed $V$. The $U$ test rejects a future producer previously mistaken for a source, including self-reference.

At a pin delimiter: reject a conflicting pin or disagreement with a produced or used-source value. A first pin on a used, previously unpinned source pops one obligation. Repeated identical pins do not pop again. A pin on a variable with neither flag merely records its mask and value.

At input end: accept exactly at a complete-record boundary with no error and an empty obligation stack. The empty flag is refreshed whenever the stack changes, so the final decision is in finite control. There is no final dictionary scan.

Correctness and unambiguity

Along each nonrejecting computation, the stack height equals the number of distinct used-source variables whose pin has not yet appeared. A variable contributes once, at its first unpinned source use, and is removed once, at its first pin. The dictionary prevents duplicate pushes and pops, irrespective of repeated names, prefix-related names, repeated operands and arbitrary pin order.

An accepting computation therefore has every source pinned. The output checks enforce single assignment and backward producer order. Inductively, every produced value is the gate value of its operands, and every pin agrees. Thus its word belongs to $K$.

Conversely, for a word in $K$, predict each source’s eventual pinned value. No producer or consistency test fails, and all obligations are discharged. This gives an accepting computation.

Finally, each prediction on an accepting computation is forced by the eventual pin for that same variable. All other transitions are deterministic. Hence there is exactly one accepting computation for each word in $K$, and none for any other word. Multiple assignments are not the source of this separation: each word in $K$ has a unique assignment to all names that occur in it, including pin-only names.

The same positive construction works for any fixed finite Boolean gate collection in the analogous checked ordered language with eventual source pins. The negative theorem used here is specifically for the XOR language $K$.

Native implementation and resources

The dictionary needs three logical pointers: committed root, current subtree and path FIFO. Add the obligation-stack pointer to the same header. All tests use finite tags and bounded labelled unfoldings. A push creates one immutable stack cell; a pop follows its tail. No physical identity comparison is introduced.

A conservative simultaneous-record certificate is $s=1$, $q=6$, $A=64$, $r=24$: one header root, arity at most six, at most 64 fresh logical records per symbol, and old-access radius at most 24. This comfortably contains the dictionary’s established $A=32,r=16$ transitions plus a stack update and its finite empty flag. Initialization is one fixed finite pointer-closed virtual graph.

The reviewed tuple-packing compiler lifts to this finite transition relation branch by branch. For each permitted source plan, use its canonical packed action. Store the predicted bit in the finite packed label, so distinct choices remain distinct computations; add no choices during otherwise deterministic packing. The same one-step simulation induction proves both recognition and the one-to-one correspondence of accepting computations.

The resulting machine has degree at most 385, radius at most 25 and exactly $N+1$ native nodes on each computation. All logical queue, trie and stack history uses $O(N)$ records, or $O(N\log(N+2))$ bits under explicit pointer encoding. There is no separate preparation or deferred query phase. These are existence bounds, not optimized constants.

What the distinction explains

The three controls now have a precise relationship:

The positive proof does not search through alternatives in deterministic time. It identifies the exact missing information and shows that successful predictions are uniquely certified later. Together with the negative theorem, this refutes unique completed values as a sufficient condition for deterministic native recognition.

For PEGs, retain the exact existing consequence: $K^R$ has no PEG, while its verified two-copy language has a PEG. The nondeterministic model defined here has not been identified with ordinary PEGs, and unambiguity of its computations is a different notion from ordered choice in a PEG.

A unique letterwise certificate, and its PEG consequence

There is also a fully deterministic formulation. Replace each input letter $a$ by a pair $(a,h)$ with one hint bit. At a first unpinned source-use delimiter, the controller uses $h$ as the predicted value. At every other symbol it requires $h=0$. Let $V$ be the resulting verifier language, and let $\pi(a,h)=a$ forget the hint.

The same dictionary, obligation stack and finite controller give $V\in\mathsf{SA}$. Correctness and uniqueness prove

$$\pi(V)=K,\qquad \pi\!\restriction_V:V\longrightarrow K\text{ is bijective}.$$

Thus deterministic native languages are not closed even under length-preserving letter homomorphisms that are injective on the accepted source language. The homomorphism is not injective on the entire alphabet; the assertion is exactly about its restriction to $V$. There is no padding or erasure, and each accepted ordinary word has one valid annotation.

Apply the deterministic reversal correspondence to $V$: $V^R$ has a PEG and $K^R$ does not. Letter projection commutes with reversal and remains injective on $V^R$. Therefore the same injective-on-language projection failure holds for PEGs. This uses the deterministic verifier, not a supposed nondeterministic scaffold-to-PEG theorem.

The point is stronger than ambiguous existential certificates: even forgetting a uniquely determined, locally presented certificate can destroy expressibility. Kim–Park already establishes general homomorphism nonclosure; the statement here records the specific length-preserving, unique-annotation circuit witness, without claiming general nonclosure anew.

Attribution and assessment

The machine definition is an explicit nondeterministic extension of Loff–Moreira–Reis, §4.1, Definitions 12–15; their Theorem 16 supplies the deterministic reversal correspondence. The negative circuit result imports Ko’s inner-product lower bound through the already documented serialized native simulation. Guessing consistent values and checking them later is classical; the finite-payload dictionary and compiler are the established implementation dependencies.

For comparison, the dictionary already makes ordinary fixed-domain, fixed-arity CSP verification nondeterministically native: guess a variable’s value at its first occurrence, store it, and check each relation from finitely many argument values. Accepting computations correspond to satisfying assignments. The special content here is unambiguity for a checked circuit language already known to resist deterministic recognition, not merely nondeterministic SAT membership.

This is an extension of those methods with an exact SAT-circuit witness, checked missing-pin obligations and strict input-end resource accounting. The full Kim–Park proof has now been compared directly. Its displayed witness-selection grammar permits multiple matching records; adding the established native seen-key dictionary to require distinct keys yields a direct unambiguous adaptation, and marking the unique selected record gives a unique letterwise certificate. Thus the general strict-inclusion and projection conclusions are extensions of known machinery, not a new separation method. The specific contribution here is the availability distinction for a uniquely valued ordinary circuit language. See the structural literature assessment for the comparison and its implications. The proofs are written and independently audited, not formally verified.