FPRD-T159: Distance-one scaffolds collapse to finite automata

1. The distance hierarchy

For a finite scaffolding automaton, the distance parameter $k$ bounds both the unfolded neighbourhood inspected at each step and the old-root paths that may be installed as ports of the new node. Let $\mathsf{SA}_{\le k}$ be the languages recognized by machines of distance at most $k$, with arbitrary finite degree, labels, and control.

FPRD-T153 proved that a continuation of length at most $h$ depends only on the current control and the old-root view of radius

$$R_{k,h}= \begin{cases} 0,&h=0\text{ or }k=0,\\ k+(h-1)(k-1),&h\ge 1\text{ and }k\ge 1. \end{cases}$$

The crucial boundary is immediate from this formula but stronger when stated as a machine compilation:

$$R_{1,h}=1 \qquad(h\ge 1).$$

The readable cone never grows.

2. Distance-one collapse theorem

Theorem. Every distance-one scaffolding automaton is equivalent to a deterministic finite automaton. If the scaffold has degree $d$, working alphabet size $g$, and $q$ control states, then the DFA needs at most

$$qV_1(d,g)$$

states, where

$$V_0=g+1, \qquad V_{r+1}=1+(g+1)V_r^d.$$

In particular,

$$V_1(d,g)=1+(g+1)^{d+1}.$$

Consequently the Myhill–Nerode index is at most $qV_1(d,g)$, and the finite-horizon residual tower from FPRD-T156 stabilizes by horizon $qV_1(d,g)-1$. This follows from the standard fact that two inequivalent states of an $N$-state DFA are separated by a word of length at most $N-1$.

Direct compilation

After a prefix $p$, summarize the scaffold configuration by

$$s(p)=(q_p,N_1(p)),$$

where $q_p$ is finite control and $N_1(p)$ is the unfolded radius-one view of the newest node, including the missing-root case.

A distance-one transition reads exactly this summary. Its new label and each new port descriptor are therefore determined by the summary and the next input letter. Every descriptor is missing, SELF, the empty old-root path, or a one-port old-root path. The radius-zero view at its target is already present inside $N_1(p)$; for SELF it is the new label. Consequently the complete radius-one view of the new node is a function of $s(p)$ and the next letter.

Thus

$$s(pa)=\delta(s(p),a)$$

for one finite transition function. The reachable summaries are DFA states, and acceptance is inherited from the scaffold control. There are at most $qV_1(d,g)$ summaries.

The same conclusion also follows semantically from FPRD-T153: agreement on control and radius-one view forces agreement on every finite continuation horizon, hence on the full right residual. The direct construction is stronger because it gives the finite automaton explicitly.

3. Exact characterization and strict first threshold

Every regular language has a distance-one scaffold: run its DFA in finite control, ignore the graph, and append one dummy node with missing ports per input symbol. Therefore

$$\mathsf{SA}_{\le1}=\mathsf{REG}.$$

Equivalently, in the stationary transport spectrum,

$$\operatorname{Tr}(L) \cap \{(d,k,g,q):k\le1\} \ne\varnothing \quad\Longleftrightarrow\quad L\text{ is regular}.$$

The inclusion into distance two is strict. The persistent selector

$$S=\{x\#0^j:x\in\{0,1\}^+,\ 0\le j<|x|,\ x_{|x|-j}=1\}$$

has an explicit degree-two, distance-two scaffold. For each $n$, its $2^n$ length-$n$ data prefixes have different residuals, since the suffixes $\#0^j$ recover every payload coordinate. Hence $S$ is not regular and

$$\mathsf{REG}=\mathsf{SA}_{\le1} \subsetneq \mathsf{SA}_{\le2}.$$

Distance two is therefore the first level where persistent graph memory can increase language-recognition power beyond finite control.

4. Residual modulus interpretation

For general $k>1$, the readable radius is

$$R_{k,h}=(k-1)h+1.$$

The map from a reachable scaffold configuration to its residual tower has a linear modulus of continuity: agreement through graph radius $(k-1)h+1$ forces agreement through response horizon $h$. At $k=1$, this modulus degenerates to a constant. The full infinite residual is already determined by one finite view, causing the regular collapse.

This is the first exact phase transition supplied by the transport program. It distinguishes graph storage from graph reachability: arbitrarily many old nodes may exist at distance one, but only finitely many radius-one unfolded views can affect any future.

5. Research boundary

The theorem does not separate distance two from distance three or prove a full strict hierarchy. For $k>1$, readable radius grows linearly with the future horizon and the finite-summary argument no longer applies. Any further separation must exploit the slope $k-1$, or another structural limitation, rather than residual cardinality alone.

The scaffolding-automaton model is due to Loff, Moreira, and Reis. The collapse proof is an elementary consequence of its local transition form and the readable-cone lemma. A targeted literature search did not locate a published statement of this distance-one characterization, but no priority claim is made without broader specialist review.

6. Reference

Bruno Loff, Nelma Moreira, and Rogerio Reis, The computational power of parsing expression grammars, arXiv:1902.08272.