FPRD-T160: Distance-two normal form for scaffolding automata

1. Statement

Let a finite scaffolding automaton have node degree $d$, distance $k$, working-alphabet size $g$, and $q$ control states. For $k\ge2$, define

$$D_{d,k}=\sum_{\ell=1}^{k}d^\ell.$$

Theorem. The machine has an equivalent distance-two scaffolding automaton with resource tuple

$$(D_{d,k},2,g,q).$$

The compiled machine creates exactly one physical node for each original node, uses the same node labels and finite control, and preserves acceptance after every prefix.

In transport-spectrum notation,

$$(d,k,g,q)\in\operatorname{Tr}(L),\ k\ge2 \quad\Longrightarrow\quad (D_{d,k},2,g,q)\in\operatorname{Tr}(L).$$

Together with FPRD-T159, this classifies the distance coordinate completely:

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

Every scaffold-recognizable nonregular language has minimum possible distance exactly two.

2. Shortcut closure

Let

$$W_{d,k}=\{w\in\{0,\ldots,d-1\}^*:1\le |w|\le k\}.$$

The compiled node has one port $[w]$ for each $w\in W_{d,k}$. If a compiled node represents an original node $v$, its shortcut invariant is

$$[w](v)=\operatorname{follow}_{\mathrm{original}}(v,w).$$

Missing original paths remain missing. The labels are unchanged.

The native radius-two view of a shortcut-closed node observes each shortcut endpoint with one further layer. It distinguishes the nonmissing base from a missing endpoint, which the native radius-one frontier can conflate, and thus determines the original native radius-$k$ view. The compiled transition can recover exactly the original transition’s next control, label, and $d$ direct port descriptors.

3. Installing the new shortcuts in two hops

Fix one word $w=i_1\cdots i_m\in W_{d,k}$. Symbolically follow $w$ from the new original node.

While the chosen direct port is SELF, the symbolic walk remains at the new node. If all of $w$ is consumed this way, the compiled shortcut $[w]$ is SELF. If a chosen port is missing, $[w]$ is missing.

Otherwise the walk first leaves the new node through an old-root descriptor $t$, where $|t|\le k$. Let $s$ be the unconsumed suffix of $w$. Then $|s|\le k-1$. Old nodes cannot point forward to the new node, so the rest of the walk stays entirely inside the old scaffold. Its endpoint is reached in the compiled scaffold by:

• the empty old-root path if $t=s=\epsilon$;
• one shortcut hop $[s]$ if $t=\epsilon$ and $s\ne\epsilon$;
• one shortcut hop $[t]$ if $t\ne\epsilon$ and $s=\epsilon$;
• two shortcut hops $[t][s]$ if both words are nonempty.

Thus every new shortcut descriptor has compiled length at most two. This argument covers repeated SELF choices, empty old-root descriptors, cycles inside old nodes, and paths that become missing.

Induction on the input length proves that the shortcut invariant holds at every node, that the compiled radius-two view reconstructs the original radius-$k$ view, and that both machines have identical control and acceptance.

4. Structural consequences

The distance parameter has only two semantic regimes:

1. At distance at most one, the readable cone is constant and the language is regular.
2. At distance two, shortcut closure can realize every finite scaffold distance. Persistent recognition has already reached its full power.

Higher distance can still be useful as a succinctness resource. Replacing distance $k$ by distance two can increase degree from $d$ to $D_{d,k}$. The theorem removes distance as an expressiveness hierarchy, not as a description-size or Pareto tradeoff.

For stationary transport spectra, every nonempty spectrum contains a tuple on the slice $k\le2$. Positive constructions may therefore target distance two without loss of recognition power. Lower bounds cannot separate a language from scaffolding automata by requiring distance three or more.

5. Research boundary

The degree bound is sufficient and can contain redundant shortcuts. It is not claimed Pareto-optimal. The construction preserves one node per input symbol, the original labels, and the original control, but trades descriptor distance for port degree.

The scaffolding-automaton model is due to Loff, Moreira, and Reis. Shortcut closure is a standard pointer-machine idea. A targeted search did not locate this exact distance-two normalization for scaffolding automata. No novelty or priority claim is made without specialist review.

6. Reference

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