FPRD-T161: Structural normal form for scaffolding automata

1. Statement

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

$$D_{d,k}=\sum_{\ell=1}^{k}d^\ell, \qquad m_{g,q}=\left\lceil\log_2(1+gq)\right\rceil.$$

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

$$(D_{d,k}+m_{g,q},\ 2,\ 1,\ 2).$$

The compiler preserves acceptance after every prefix and still creates exactly one node per input symbol. All created nodes use one neutral working label. The two physical control states record only whether the simulated source control is accepting.

Every distance-zero machine may first be regarded as distance one, so the consequence holds for every finite scaffolding automaton:

$$\mathsf{SA} =\bigcup_{D<\infty}\mathsf{SA}(D,2,1,2).$$

Equivalently, for every language $L$,

$$\operatorname{Tr}(L)\ne\varnothing \quad\Longleftrightarrow\quad \exists D\;(D,2,1,2)\in\operatorname{Tr}(L).$$

2. One structural code replaces both label and control

The native model starts with a distinguished base node. Reserve the all-zero bit pattern for that node. Number the $gq$ ordinary pairs

$$(\gamma,s)\in\Gamma\times Q$$

by the nonzero integers $1,\ldots,gq$. They fit in $m_{g,q}=\lceil\log_2(1+gq)\rceil$ bits.

Add one marker port for each bit. On a newly created node, a one-bit marker is SELF and a zero-bit marker is missing. Thus every physical node has the same neutral working label, while its local marker geometry records both the source label placed on that node and the source control reached when it was created.

The base node needs no added edges. Its marker ports are all missing, so it already realizes the reserved zero pattern. At the empty prefix, the source initial control is a compile-time constant. After a nonempty prefix, the marker ports of the current top recover the exact source control.

The compiled physical control retains only one bit:

$$A \quad\text{iff the recovered source control is accepting}.$$

This preserves acceptance at every cut. The complete source control needed for the next transition comes from the top-node marker geometry, not from physical finite control.

3. Shortcuts and markers fit in two hops

FPRD-T160 gives each node one shortcut port $[w]$ for every nonempty source port word $w$ of length at most $k$. There are $D_{d,k}$ such ports.

The present construction combines shortcut closure with structural coding rather than applying two black-box compilers in sequence. From the current top:

1. the root marker ports recover the current source label and control in one hop;
2. a shortcut port reaches the endpoint of any source path through length $k$ in one hop;
3. one marker hop from that endpoint recovers its source label.

Missing shortcut endpoints remain visibly missing. A nonmissing endpoint with all marker ports missing is the distinguished base. Hence the compiled radius-two view reconstructs the complete source radius-$k$ unfolded view and the current source control.

The finite transition table can therefore compute exactly the source next control, new label, and direct port descriptors. It installs:

• every new shortcut with the at-most-two-hop descriptor from FPRD-T160;
• every marker bit as SELF or missing;
• the accepting or rejecting physical control matching the source next state.

Induction on input length proves the shortcut invariant, the marker invariant, exact transition simulation, and prefix-by-prefix acceptance equivalence.

4. Canonical structural degree

Define

$$\delta_{\mathrm{str}}(L) =\min\{D:(D,2,1,2)\in\operatorname{Tr}(L)\},$$

with value $\infty$ when the set is empty. The minimum exists whenever the set is nonempty because it is a nonempty subset of the natural numbers. Then

$$L\text{ is scaffold-recognizable} \quad\Longleftrightarrow\quad \delta_{\mathrm{str}}(L)<\infty.$$

This does not erase the four-dimensional Pareto spectrum of FPRD-T157. Distance, label count, and control count can still trade against degree and can matter greatly for succinctness. It does show that the existence question has a one-dimensional canonical slice. Above the regular distance-one tier, all unbounded recognition capacity can be placed in persistent graph topology.

5. Audit

The executable audit checks the combined compiler on twelve deterministic source machines with degrees one and two, source distances one through three, and all binary prefixes through length seven. It checks exact source-view and source-state reconstruction, unary physical labels, two-state physical control, shortcut closure, every marker bit, and acceptance after each prefix.

It separately exhausts all working-alphabet and control sizes from one through eight, checking the sharp marker-width formula, the reserved base code, and every ordinary label-state round trip.

The checker is finite evidence for the construction. The proof is the invariant argument above.

6. Boundary and relation to prior work

The degree bound is sufficient, not claimed optimal. The construction may pay heavily in degree for removing distance, labels, and control. Its conclusion is about recognition power, not descriptional complexity.

Scaffolding automata are due to Loff, Moreira, and Reis. Encoding finite labels and control into local pointer geometry is a standard structural-encoding idea. A targeted search did not locate this exact unary-label, two-control normal form for scaffolding automata. No novelty or priority claim is made without specialist review.

7. Reference

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