FPRD LabShare an approach

← Claims

Theorem and constructive upper bound

FPRD-T75

Raw height from finite-horizon output variation

Exact statement

Let f:Σ∗⇀Gf:\Sigma^*\rightharpoonup G have nonempty domain DD, let Λf(N)\Lambda_f(N) be its finite-horizon prefix-metric variation, and let βN\beta_N be the largest shortest completion length among prefixes of D∩Σ≤ND\cap\Sigma^{\le N}. Then Λf(N)≤hf1(N)≤max⁡{∣f(w∗)∣,(2βN+3)Λf(N)}\Lambda_f(N)\le h_f^1(N)\le\max\{|f(w_*)|,(2\beta_N+3)\Lambda_f(N)\}, and for every domain hf1(N)≤∣f(w∗)∣+24(∣w∗∣+1)Λf(N)+1h_f^1(N)\le |f(w_*)|+24(|w_*|+1)\Lambda_f(N)+1. Moreover βN≤N\beta_N\le N; if a trim qq-state NFA recognizes DD, its uniform completion radius is at most q−1q-1.

StatusProved and independently reconstructed
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

With state count unconstrained, a horizon trie can realize the target using edge weights controlled by nearby completed domain words. The theorem makes the completion-length dependence exact.

Definitions

  • Λf(N)=max⁡∣f(u)−1f(v)∣/(dpref(u,v)+2)\Lambda_f(N)=\max |f(u)^{-1}f(v)|/(d_{\rm pref}(u,v)+2) over domain words of length at most NN.
  • βN\beta_N is the maximum, over p∈Pref⁡(D∩Σ≤N)p\in\operatorname{Pref}(D\cap\Sigma^{\le N}), of the shortest ∣z∣|z| with pz∈D∩Σ≤Npz\in D\cap\Sigma^{\le N}. Empty horizons use Λf(N)=βN=0\Lambda_f(N)=\beta_N=0.

Hypotheses and scope

  • The output group has a fixed finite symmetric generating set and its word norm.
  • The input alphabet is finite; the construction may use exponentially many states.

Proof or evidence

The elementary upper bound anchors each horizon-trie prefix at a nearby completed word. The uniform theorem extends the boundary map into a weighted tree with factor eight, compares its Lipschitz constant to 3Λ_f(N), and rounds the image to Cayley-graph vertices.

Finite-horizon variation bound →

Verification notes

The review independently reconstructed both proofs and checked 32,767 nonempty finite domains, 310,784 trie edges in each construction lane, 1,966,080 output-value pairs, 5,600 trim NFAs, and 41,038 directed NFA edges.

Limitations

  • This minimizes raw height with no state bound and therefore is not a state-complexity theorem.
  • The uniform arbitrary-domain bound depends on Basso–Sidler's external metric-extension theorem; the numerical constants are proved upper bounds, not claimed optimal.

Open work

Determine whether either construction coefficient is optimal after minimizing over all unrestricted-state realizations.

Notes

The upper-bound presentation is the full horizon trie and carries no state budget. This is a metric-extension statement, not an effective construction from a weighted-automaton presentation. The stronger arbitrary-domain uniform coefficient proposed through geometric tree extension still has written-proof obligations and is not promoted here.