Independent constraint components need no shared name scale

5 October 2026. Written native construction, extending the bounded-component pending-write method.

A collection of equality pairs can mix very short names in one pair with very long names in another. Those independent components should not have to share a global naming convention merely to keep their constraints consistent.

The previous bounded-component construction required the longest name in the whole input to be within a fixed factor of the shortest. We can now replace that global condition by a condition inside each connected component. Arbitrarily different name lengths in unrelated components are allowed.

The recognizer maintains separate dictionaries for different length ranges. While a name arrives, it prepares the next dictionary before the name becomes long enough to need it. The latest component update remains in a bounded list of pending writes, so every answer is current even when some distant dictionaries still have unfinished installation work.

The precise positive theorem

For a nonempty binary-word name $w$, define its length class

$$\lambda(w)=\lfloor\log_2 |w|\rfloor.$$

Thus class $j$ contains lengths from $2^j$ through $2^{j+1}-1$. Fix a nonempty finite domain $D$, a finite language $\Gamma$ of unary and binary relations, and integers $k\ge1$ and $s\ge0$.

Let $L_{D,\Gamma,k,s}$ contain exactly the well-formed, satisfiable ordinary constraint records for which every connected component $H$ of the loopless primal graph satisfies

$$|H|\le k,\qquad \max_{w\in H}\lambda(w)-\min_{w\in H}\lambda(w)\le s.$$

Written theorem. Both $L_{D,\Gamma,k,s}$ and its string reversal have deterministic native scaffolding-automaton recognizers and PEGs. The recognizers check both displayed conditions.

The parameters are fixed independently of actual input length, variable count and name widths. Records remain U(w); and B(u,v);, with finite relation tags, nonempty literal binary names, significant leading zeros, and ordinary delimiters. Constraints may arrive in any order. Repeated edges, pins before or after edges, prefix-related names, and same-name binary records are included. Every distinct-name binary record contributes an edge, even for a full relation; a same-name record applies its diagonal restriction without adding a loop. Invalid input rejects and the empty conjunction accepts.

There is no supplied decomposition, length header, external handle, padding or preprocessing phase. Work and allocation per symbol are bounded; the final answer needs no end-of-input computation.

The local condition is substantive. It bounds name lengths within a component by a factor less than $2^{s+1}$, but places no ratio bound between different components. For $s=0$, one pair can have names of length1 and another names of length one million, provided each pair stays within one length class. For $s=1$, names immediately on opposite sides of a power-of-two boundary may interact. Arbitrary length disparities inside one connected component remain unresolved.

Any collection whose global name-length ratio is at most $C$ satisfies the local class condition for $s\ge\lceil\log_2 C\rceil$. The new accepted language also contains collections with unbounded global ratio. This is an exact theorem about the displayed class condition, not a claim to check a different exact local-ratio predicate automatically.

What each dictionary stores

There is one dictionary $T_j$ for each name class $j$, containing only names of that class. Its bucket also holds at most one pending batch $P_j$ of at most $k$ point replacements. The logical dictionary is $T_j$ with $P_j$ applied, whether or not those writes have been physically installed.

A component has an ordered list of member spellings $W=(w_1,\ldots,w_t)$ and exact feasible relation $R\subseteq D^t$, where $t\le k$. Each member terminal stores $W,R$, its own coordinate, and the member class offsets relative to its own class. These offsets lie in $[-s,s]$ and are finite data. The spellings are at most $k$ immutable FIFO references, collected from actual input. Relation tables and indices are finite because $D,k,s$ are fixed. An unseen name denotes a fresh singleton allowing every value of $D$.

Use the existing strict FIFO and capsule trie. A write to a stored spelling of length $h$ needs at most $a(h+1)$ bounded local operations, for a fixed constant $a$. Trie frames copy the bounded component header pointers opaquely. One-node exposure remains nonrecursive; no operation tests pointer identity or reads a numeric address.

A reader can look up a name in a snapshot $T_j$ while comparing the arriving bits against all targets in its saved $P_j$. A full target match selects that replacement payload; otherwise the snapshot payload is current. Exact termination distinguishes a name from a proper prefix. The reader retains its own original pending list even if another worker has meanwhile completed the bucket’s writes.

Preparing a bucket before it is needed

The index $j$ is not supplied with a name. Waiting until its delimiter to select a bucket would leave no time for lookup. Instead the machine prepares one class ahead while the name is still arriving.

At name length $2^j$, the reader for class $j$ has already consumed the entire current prefix. During the next $2^j$ arriving bits:

• The current reader continues one bit at a time, ready if the name ends before the next boundary.
• A reader for class $j+1$ starts with a persistent copy of the prefix FIFO. Each new bit is appended to its replay queue, and it consumes up to two queued bits per input bit.

The ahead reader starts with $2^j$ queued bits. After $2^j$ more arrive, at most $2^{j+1}$ need to have been consumed, which the two-step rate supplies. Thus it is caught up exactly when the name length reaches $2^{j+1}$. Promote it then. Its replay includes both trie traversal and all saved pending-target comparisons, not just lookup.

Only the current and ahead readers exist at once. The first-bit case is a fixed-size initialization. If a name ends early, discard its ahead reader. All of that speculative work has already been charged to the input symbols that performed it.

A local clock, without numeric addresses

The machine detects the power-of-two boundaries using immutable unary lists. After the first bit, a remaining-interval stack has one cell. Each subsequent bit pops one remaining cell and pushes two cells onto a next-interval builder. When the remaining stack empties, the builder becomes the next remaining stack and the builder resets. Interval lengths are therefore $1,2,4,\ldots$; boundary lengths are $1,2,4,8,\ldots$.

A finite phase handles initialization. Each bit performs constant local work and allocation. The class-index stack is empty at length1 and gains one cell only at the later boundaries2,4,8,…, so its length is exactly the current class index. The logarithm in the theorem is a mathematical description of this clock, not an unbounded arithmetic instruction.

A fixed window of neighboring buckets

When the current name class is $j$, retain the directory window

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

Every bucket in this window has had its old pending batch completely installed by length $2^j$. The window is a fixed-size tuple, not an input-sized table. During the following interval, a separate worker prepares the next rightmost bucket, $j+s+1$.

Its targets have lengths less than $2^{j+s+2}$, so installing its at most $k$ writes requires at most

$$ak(2^{j+s+2}+1) \le ak(2^{s+2}+1)\,2^j$$

local operations. A fixed rate depending on $k,s$ completes them during the next $2^j$ input bits. At the next boundary, shift the window one position and admit this completed bucket. At length1, servicing buckets $0,\ldots,s$ is a fixed amount of work since their targets have length below $2^{s+1}$.

For $s=0$, the ahead reader and the rightmost installer concern the same bucket. They use a snapshot plus its saved pending list, so their overlap is safe. For larger $s$, the installer may concern a different bucket from either reader. There are still only two readers and one installer, with fixed additional cursors.

If the name ends before the next boundary, discard the unfinished rightmost installation and retain that bucket’s original payload in the directory. Do not publish its partial root. Completed servicing inside the current window is retained. Installing pending writes changes only the physical representation, not the logical meaning of any bucket.

The immutable directory

Buckets form a list in increasing class order, with an implicit blank suffix of empty buckets. The prefix left behind the window is retained as a FIFO of immutable frames; the current window and unvisited suffix remain separately rooted. Viewing one directory position opens at most one frame, exactly as for a one-child capsule trie. Crossing a boundary moves at most one old window header into the frame FIFO and exposes one next bucket.

At a name delimiter, rebuild the fixed-size explicit window and wrap the saved prefix frames around it in one capsule. No walk back through all previous classes occurs. The lookahead bucket outside the window is retained in its original form unless it was promoted at a completed boundary. Thus discarding speculative work cannot overwrite a newer serviced bucket or lose a pending batch. Short names visit only a short directory prefix; no maximum name length or bucket universe is known in advance.

Updating a constraint component

A unary restriction at coordinate $i$ replaces $R$ by

$$\{z\in R:z_i\in U\}.$$

For a binary record, save the first endpoint’s component table and coordinate. While the second name arrives, compare it against all spellings in that list. A match identifies the second coordinate in the same component, including a first-occurrence self-loop. Otherwise its component is disjoint, and its table is obtained from its own current bucket.

Within one component, intersect $R$ with the binary relation on the two coordinates. For disjoint tables $R\subseteq D^t$ and $S\subseteq D^u$, form

$$\{(x,y)\in R\times S:(x_i,y_h)\in B\}.$$

Reject if the merged size exceeds $k$. These are finite table operations. The first endpoint’s table stays logically current during the second lookup because servicing buckets performs no new semantic constraint update.

Checking and rebasing the class span

Save the first endpoint’s unary class counter $j_1$. During the second name, pop one of its cells at each later class boundary2,4,8,…; do not pop at the first-bit initialization. At the delimiter, bounded lookahead through at most $s+1$ residual cells, or a saturated finite excess counter, determines whether

$$\delta=j_1-j_2\in[-s,s].$$

If not, the binary record violates the component span condition and rejects. A self-loop cannot cause this failure. In both the within-component and disjoint-component cases, shift the first table’s offsets by $\delta$ to use the second endpoint’s class $j_2$ as origin. Only in the disjoint case append the second component’s list, whose offsets already have that origin. Temporary offsets lie in a fixed finite range. Compute the maximum minus minimum of the resulting list and reject if it exceeds $s$.

For a valid component, every member now lies in the serviced window around $j_2$. Produce at most $k$ terminal replacements, partitioned among those buckets. If the combined offsets are $a_1,\ldots,a_t$, the payload for member $m$ stores offsets $a_l-a_m$, rebased to that member’s own class. All lie in $[-s,s]$.

At the record’s final delimiter, place these replacements into the affected buckets’ pending lists and commit the fixed window through its capsule. For a binary record, use the second endpoint’s current directory path and window, never the saved path from the first endpoint. Every affected bucket was serviced during the last endpoint’s name, so its old list is empty. There is no unbounded backlog inside a bucket and no merging of unfinished dictionary traversals. Globally, many distant buckets may retain pending lists; the next name services only the relevant bounded window.

The same rebasing rule applies to unary updates without a merge. Empty relations latch inconsistency immediately. Component-size violations, span violations and contradictions are all permanent under additional conjuncts. The final answer uses the new relation table now, not after installation of its replacements. No final flush is required.

Correctness, reversal and resources

Inductively, the logical bucket dictionaries contain exact component tables, consistently replicated at all members through committed entries or pending replacements. Snapshot-plus-pending lookup reads those exact tables. Physical servicing preserves their meaning. The relation operations are the usual exact restriction and join, while class-offset checks enforce the stated graph condition. This proves acceptance at every complete-record boundary; malformed and incomplete syntax reject.

For reversed input, use the mirrored record parser. Hold at most two endpoint tables until the relation tag arrives at the record’s end, validate its arity, and transpose a binary relation because its endpoints were read in reverse order. Reverse all name spellings consistently. This preserves lengths and name identity, and reversing constraint order preserves the final conjunction and graph. The same servicing, class checks and current-answer invariant apply. Applying the scaffold-to-PEG correspondence separately to the two native recognizers gives PEGs in both orientations.

Every input bit performs a fixed number of queue, trie, directory and unary-stack operations. Window changes and finite relation operations have bounds depending only on $D,\Gamma,k,s$. Old-access radius and fresh allocation therefore remain fixed. All pointers come from exposed old fields or declared same-batch slots; no identity tests, old writes, memoization or numerical address operations occur. Initialization is a fixed finite graph of empty structures. The reviewed simultaneous-record compiler applies.

For actual encoded length $N$, the native run has $N+1$ physical nodes. All source storage and discarded speculative history are $O_{D,\Gamma,k,s}(N)$ records; explicit pointer serialization uses $O_{D,\Gamma,k,s}(N\log(N+2))$ bits. Every name bit and delimiter is charged, and the number of variables is at most $N$.

Contribution and remaining question

This is a further native application of persistent tries, buffered updates and classical real-time scheduling. The previous proof compares those mechanisms with Okasaki’s Purely Functional Data Structures, §5.2. The additional construction here is the early preparation of a length class, its immutable neighboring-bucket window, and the checked component-local span invariant. The finite component relations themselves are elementary. The proof has independent audits; it is not a machine-checked formalization or a new general persistence theorem.

The global name-length restriction is removed. The local restriction is not: one component may still not connect arbitrarily distant length classes in this construction. Such an update would require access to a bucket outside every fixed serviced window. A different representation might resolve that; no lower bound is claimed. Unbounded star components also remain open because one change need not have a bounded list of member replacements.

The next decisive test is therefore cross-scale equality inside a single pair, where a short name can constrain a very long partner. Independent components with different scales no longer account for the obstruction in the current construction.