Sparse growing support through exact row classes

12 October 2026. Written native construction 74. This adapts the Lab’s charged dictionaries, persistent queues, counters and pending-reader schedule; no root admission or external priority claim.

The current investigation guide places this result alongside its successors. The two-omission review identifies the current paid strict-extension target; it does not remove this note’s hypotheses or close its remaining frontier.

Result and motivating example

Let the observed targets be three long, otherwise unrelated names $a,b,c$. Rows $\{a,b\}$ and $\{a,c\}$ together cover all observed targets, regardless of the empty literal regions between those names. More generally, if every row omits at most one observed target, two different rows cover the whole support. Repeating an equal row changes nothing. Composition can therefore compare exact row classes instead of traversing a common support tree.

The construction below learns these classes from ordinary positive Horn records while support grows. It assigns each live class a short binary code, recycles a code only after its class has no current rows, and pays for every change during actual input. A future query reads at most two row tries or the global support trie. No enumeration of absent literal names occurs.

This is a different escape from the common-directory obstruction, not maintenance of its moving mixed-region budget. Unlike construction 73, it pays no ambient-cube charge. Its restrictions are explicit: rows omit at most one final observed target, widths are common within each name role, and alias length is at most a fixed multiple of target length. Targets can be arbitrarily longer than aliases. Independently prepared stores remain outside the result.

1. Exact language and resource statement

Fix an integer $A\ge1$. Use ordinary right records (-01v,+1w);, followed by left records (-00u,+01v);, then ordinary pins (+00a);(-1q);, with the inherited fixed phase delimiters. Require at least one right record. Learn a common positive alias width $\ell$ and common positive target width $n$ from the first record. Every intermediate name in either factor must have width $\ell$; every right target must have width $n$. Check

$$\ell\le An.$$

There is no restriction on source or pin lengths beyond the ordinary positive-name syntax. Let $X_v$ be the distinct right targets of an observed right alias, and let $U=\bigcup_vX_v$. At the right boundary check

$$|U|-|X_v|\le1\quad\text{for every observed right row }v.$$

Only the final gate is required. Intermediate rows can have arbitrarily many omissions and signatures can collide there. Duplicate incidences have no effect. The global support can grow on the very last right record. An alias absent from the right factor denotes EMPTY, not an additional row constrained by the gate.

Theorem 74. For each fixed $A$, one deterministic native scaffolding automaton recognizes exactly the well-formed formulas satisfying these gates that are SAT. It has fixed degree, radius, labels, finite control and initialization, with immutable old-top updates and bounded work and allocation per actual symbol. Output is ready at the final symbol. Native recognition supplies a PEG for the reversal of this complete checked language.

The actual input length is

$$N=\sum_R(9+|v|+|w|)+\sum_L(10+|u|+|v|)+11+|a|+|q|,$$

plus actual fixed phase delimiters. Total logical work, old-storage observations and retained records are $O_A(N)$. The inherited simultaneous-record compiler gives $N+1$ physical scaffold nodes, and explicit pointer serialization uses $O_A(N\log(N+2))$ bits. There are no supplied class codes, free handles, pointer-identity tests, address metadata, input padding, uncharged preprocessing or EOF work.

2. Exact signatures and the collapse of union

For an arbitrary finite set $X$ of width-$n$ names, define

$$\sigma(X)=\left(|X|,\ \bigoplus_{w\in X}w\right).$$

The XOR is bitwise on actual target spellings. It is an exact algebraic quantity, not a probabilistic hash. It need not identify arbitrary intermediate sets.

At the final gate, every nonempty observed row is either $U$ or $U\setminus\{h\}$ for one $h\in U$. Cardinality distinguishes the FULL case from every omission. Among omissions,

$$\bigoplus(U\setminus\{h\})=\left(\bigoplus U\right)\mathbin{\oplus}h,$$

so equal XORs imply equal omitted names. Thus, on the checked final class,

$$\sigma(X)=\sigma(Y)\iff X=Y.$$

The cardinality is essential: omission of the all-zero name does not change XOR. Distinct final signatures imply $X\cup Y=U$, including the case in which one row is already $U$. Consequently a selected union is EMPTY, one representative row, or all of $U$. This proof is independent of the shape and sparsity of the literal support trie.

3. A final gate without changing every old row

Maintain the ordinary global support trie and one ordinary trie per observed row. The actual target traverses both, so the endpoint reveals two distinctness flags: $b$ for a new global target, $e$ for a new incidence in this row. Always $b\le e$. Maintain $g=|U|$, each row degree $c$, and the minimum observed row degree $m$.

A histogram keyed by degree stores unary populations of rows with that degree. Degree keys have $n+1$ binary bits, sufficient through $2^n$ and the speculative successor $2^n+1$. When an existing row receives a new incidence, move one population unit from $c$ to $c+1$. The new minimum is

$$m'=\begin{cases}m+1&c=m\text{ and the old bucket at }c\text{ had population }1,\\m&\text{otherwise.}\end{cases}$$

Indeed, in the first case no smaller degree remains and the updated row itself witnesses degree $m+1$. In every other case a row still witnesses $m$. A newly observed row has degree one and sets $m'=1$. There is no search for a successor minimum and no scan of rows.

The final co-singleton gate is exactly $m\ge g-1$. Prepare both $g$ and $g+1$, both the old and prospective histogram/minimum, and the corresponding comparison flags during the actual target. At its endpoint select the unchanged or updated row state using $e$, and the global count using $b$. The final gate flag is therefore current after every record, including a last global birth. Intermediate failure does not set a permanent rejection flag.

These preparations use $O(n)$ local work: saved binary counters have fixed width $n+1$; unit arithmetic and exact comparison scan them, and a histogram point update traverses and returns along $n+1$ bits. A fixed number of candidate updates is permitted. The keys depend only on saved counters, not on the late distinctness flags. Unary bucket populations use bounded increment, decrement and one tests. All traversals and returns are charged to the target’s $n$ actual bits at a fixed accelerated service rate. A prospective new row is handled separately, avoiding deletion of a nonexistent degree-zero bucket.

4. Short codes for the current signature classes

Maintain a dictionary whose keys are complete signatures. A leaf contains a positive unary count of current rows with that signature and a code in $\{0,1\}^{\ell}$. Each row header stores its current code, degree, materialized XOR word and membership trie. Class populations count rows, not target incidences. Removing the last row deletes that signature leaf and releases its code.

At most $2^\ell$ aliases, hence at most $2^\ell$ live signature classes, can exist. A persistent binary free-code trie represents the unused codes. It begins as implicit FULL; it is not enumerated. An allocator follows child nonemptiness to a free leaf, materializes its $\ell$ bits and removes it in $O(\ell)$ local work. Freeing a saved code is a paid point insertion. Code equality later means equality of these actual bits, never pointer identity.

Consider a new incidence of an existing row. Its count increases, so its signature changes even if the inserted target is zero. Let $o$ be its old code and $F$ the old free set. If $F$ is nonempty, prepare a free candidate $f$ and all four sets

$$F,\quad F\cup\{o\},\quad F\setminus\{f\},\quad(F\setminus\{f\})\cup\{o\}.$$

Each takes only a fixed number of length-$\ell$ traversals and returns. At the signature-key endpoints, the old population-one flag and new-class-present flag select the correct prepared set. A present new class supplies its existing code. An absent new class receives $f$; release $o$ precisely when its old class dies. For a first occurrence of an alias there is no old code to release.

If $F$ is empty and a new class is needed, reuse $o$. This case is safe: all $2^\ell$ classes are occupied, so all $2^\ell$ aliases already exist and each class contains exactly one row. The current old class therefore dies. A new alias cannot occur in this case. If the new signature instead joins an existing class, release the dead old code. All cases preserve a bijection between live signature keys and used codes.

Code reuse cannot change an old snapshot: old row headers, dictionaries and free pools are immutable, and each snapshot retains its own coordinated roots. Left selections start only after the right store freezes. We never compare codes from independently prepared stores or from different right-store versions.

The one-sided length gate pays for the allocator: the old row’s code becomes available only after its alias lookup, so the subsequent target must fund $O(\ell)$ work. Assuming this work was already paid by the just-finished alias would be incorrect. Since $\ell\le An$, fixed accelerated target service suffices. No converse bound $n=O(\ell)$ is used.

5. Streamed signatures and atomic dictionary changes

This section supplies the remaining preparation deadline rather than treating interning as a free primitive. Reuse the established strict persistent FIFO and coherent path capsules. Saved binary words have bounded local head/tail access; arithmetic may construct both orientations with paid stacks and FIFOs. All signature and code words are explicit streams, not accumulated XOR adapters.

Encode a signature by interleaving the $n$ target-order XOR bits with the first $n$ least-significant-first count bits, and append the remaining count bit. Write the order explicitly as $(c_0,x_0,c_1,x_1,\ldots,c_{n-1},x_{n-1},c_n)$. Its key has exactly $2n+1$ bits. Lexicographic numeric order is unnecessary: the dictionary tests equality. This encoding also permits first-record initialization before $n$ is known.

For a later record, its alias opens one row header and saves the outer row-dictionary path. During the target, a fixed collection of workers does the following:

• Compute prospective degree $c+1$, histogram/minimum candidates and gate comparisons from ready old counter streams.
• Prepare the free-code candidate and joint release/allocation variants from the ready old code and free-pool root.
• Traverse the actual target in the global and row membership tries, while XORing each bit with the corresponding saved row-XOR bit and retaining the new XOR stream.
• Once the new counter stream is ready, feed the old and new complete signature keys through a joint dictionary update. Buffer early target/XOR bits in a strict FIFO while counter preparation runs.

There is a fixed bound $a_A(n+1)$ on the counter, histogram, comparison and code preparation work, because $\ell\le An$. Give these workers a fixed rate large enough to finish within the first quarter of the target’s symbols, with a fixed small-$n$ case absorbed by increasing the rate. The stream worker has a fixed cost per queued bit; give it more than twice the input arrival rate after setup. It catches up before the final target bit, then handles each new bit in its arriving symbol’s bounded batch. The last target bit and trailing count bit need only bounded work. Increasing all service constants together accounts for FIFO operations, old observations, discarded candidates, call returns and allocation. This is one fixed machine for each $A$, not a nonuniform choice per input.

The two signature writes must not publish two stale independent root paths. The chosen encoding makes their joint update particularly simple: incrementing the degree always flips its least-significant bit $c_0$, which is the first key bit. Old and new signatures therefore enter opposite children of the root. Open one suffix builder in each old child and retain their root directions. At the endpoints create both changed tips, close the two suffix capsules, and assemble one root from the two new child views. Every saved suffix frame has an untouched sibling; no shared ancestor path is overwritten. This is a fixed number of closures, not a reverse traversal. A newly observed alias uses a single insertion. A duplicate incidence discards all prospective updates.

Class-population flags and the new existing code are known only at these key endpoints. The prepared free-pool variants and candidate code are already ready, so choosing the leaf payloads requires bounded work. Histogram updates, code changes, signatures, membership tries and row headers commit as one fixed root tuple. The saved outer row path is written exactly once with the finished header; no other row path is changed during that record.

First-record initialization and invalid inputs

The first alias builds its width ruler and code $0^\ell$ as its actual bits arrive. In parallel, construct the free-code view with that code removed: along the all-zero path retain FULL untouched siblings and an EMPTY tip. The coherent path capsule closes in bounded work. No alias identity is privileged thereafter.

The first target is its row’s XOR word and the initial global support. Its actual bits build the two membership views, the width ruler and the one-class signature path. The count-one bits are $1,0,\ldots,0$ in least-significant-first order, so they can be interleaved with the target immediately. Append the final zero count bit at the delimiter. The degree histogram initially has its sole key one, likewise built from one followed by zeros while the target arrives. Set $g=m=c=1$ and the class population to one; both initial gate flags are true apart from the length check.

A cursor through the alias ruler consumes up to $A$ cells per target bit, testing $\ell\le An$ at the first target endpoint. Later width checks use the saved rulers. Ill-formed, short, overlong or incomplete records can reject without completing speculative workers; only well-formed records need their candidate state ready for reuse. Structural failure is permanent, unlike temporary failure of the final co-singleton gate.

6. Composition and exact final readout

Freeze the right store at its boundary, after testing the already ready final gate. Every surviving class code now identifies exactly one row set by section 2. No code changes during the left factor.

A source keeps a committed state EMPTY, ONE or FULL, with a representative row/code for ONE, and at most one pending row/code. During its next actual alias of width $\ell$, compare the old pending code with the committed ONE code one bit per symbol, while the new alias’s ordinary row lookup proceeds. If both rows exist and their codes differ, set committed FULL. If their codes agree, retain either representative. EMPTY installs the old pending row; FULL remains FULL. At the endpoint, install the newly looked-up row as pending, or EMPTY for an absent right alias. All comparisons and source-header writeback finish within that record, without charging the new pending job to symbols before it was released.

Immediately after any selection, a query uses the global support trie for committed FULL, or the committed representative and pending row tries otherwise. In the latter case it computes their Boolean OR. These are at most two literal readers, independent of selection count. The actual positive source pin retrieves its source capsule; the actual negative target pin traverses the selected literal readers. Terminals and widths distinguish supported targets from absent, short or long names. SAT is the negation of the resulting product entry. No omitted name is reconstructed and no final union is forced at EOF.

This is exact negative observation of the original ordinary relation product. The finite type comparison is a consequence of the checked co-singleton algebra, not a generic compiler or free semantic quotient.

7. Relation to the current frontier

The method accepts arbitrary sparse observed supports, arbitrary order of global births, and arbitrarily many current row classes. For a large sparse $U$, the rows $U\setminus\{h\}$, one for each $h\in U$, give unbounded class diversity. Choose sufficient alias width to name them and sufficiently long actual targets to satisfy the one-sided gate. A row may contain an unbounded number of targets, and an enormous common target prefix adds no class-comparison work in the left factor. Every preparation step is paid by those actual positive records.

A single late support birth can make all untouched rows co-singletons at once. Their stored signatures and codes need no revision: the new support changes which omitted name each signature denotes, but distinct signatures still distinguish the final row sets. The global degree/minimum check certifies that interpretation. This is the mechanism that avoids the old-row repair scan.

For two omissions, this particular collapse fails. Distinct rows can share one missing target, and cardinality plus XOR can collide: in a two-bit cube, omission pairs $\{00,11\}$ and $\{01,10\}$ have the same XOR. A short exact class code alone would also be insufficient, since two unequal two-hole rows need not cover $U$. The next operation must compute an intersection of bounded omission sets, including its exact literal readout, with a paid producer.

Construction 73 retains arbitrary ambient-budget rows; constructions 71 and 72 retain their support-relative classes. None is claimed to subsume the others. Early unique routing, replay slices, affine-fragment joins, persistent causal sharing and unary coherent algebra do not automatically supply this signature classifier. Imported entry 129 keeps its growing alphabet and conditional state/port bounds; this is a native positive subclass, not a SAT/scaffold lower bound or independent-store joining theorem.

Next decisive test: extend the mechanism to at most two omitted observed targets per row. Supply an exact input-paid omission representation and intersection operation that remains accessible after short-alias selections, or prove a precise failure of a proposed representation. Compare the completed dictionaries and deadline accounting with primary persistence and set-reconciliation arguments in the next literature review. Removing the one-sided alias/target gate and joining independently prepared stores remain separate.

Independent finite audit and review separate finite semantics from the written native schedule.