FPRD LabShare an approach

← Claims

Theorem · exact base tier and strict first step of the scaffold distance hierarchy

FPRD-T159

Distance-one scaffolds recognize exactly the regular languages

Exact statement

Every distance-one scaffolding automaton of degree d, working-alphabet size g, and q controls compiles to a DFA with at most N=q[1+(g+1)^(d+1)] states, so its residual tower stabilizes by horizon N-1. Conversely, every regular language has a distance-one scaffold presentation. Hence SA_<=1=REG. The explicit degree-two, distance-two persistent selector is nonregular, so REG=SA_<=1 is a strict subset of SA_<=2.

StatusSelf-contained constructive proof with compiler and strictness audits
External reviewA targeted literature search found the original scaffold model but no published statement of this distance-one characterization; no specialist review or priority claim is recorded.

Context

FPRD-T153 gives radius R_(k,h)=k+(h-1)(k-1) for horizon h. At k=1 this radius is constant, so one finite rooted view determines the complete future residual.

Hypotheses and scope

  • The machine is a finite deterministic scaffolding automaton with observation and descriptor distance at most one.
  • The unfolded rooted view includes labels, missing targets, repeated targets, and SELF behavior exactly as in the native model.
  • Acceptance is determined by finite control.

Proof or evidence

The DFA state is the pair of scaffold control and radius-one root view. A distance-one descriptor can target only missing, SELF, the old root, or one old neighbor, so the next radius-one view is a function of the current pair and input symbol. The audit checks 12,264 compiled runs, 78,336 exhaustive finite-scaffold transitions, 78,192 same-summary comparisons, and the distance-two selector on 88,573 words.

Distance-one collapse theorem →

Verification notes

The checker covers degree one and two, missing roots, SELF loops, empty old-root paths, one-port paths, exact DFA summaries, the qV_1 state bound, and 2,046 selector residual profiles through data length ten.

Limitations

  • The theorem does not separate distance two from distance three or establish a full strict hierarchy.
  • The DFA state bound is a uniform ceiling and need not be minimal.
  • The strict witness uses the previously published persistent-selector construction rather than a new language family.
  • No novelty or literature-priority claim is made without broader specialist review.

Open work

Use T160's complete distance normalization to study degree-versus-distance succinctness and optimal degree rather than further expressiveness levels.