Two height coordinates

A deterministic sequential integer-weighted machine assigns an initial weight, a weight to each defined transition, and a final weight to each accepting state. Its raw heightis the largest absolute finite weight in that presentation.

To obtain canonical height, first trim the machine. Choose the pinned breadth-first access tree, push each tree-path weight into the state it reaches, then absorb the initial weight into the final weights. Tree edges become zero. Canonical height is the largest absolute transition or final weight in this normalized machine.

The normalization preserves the computed series and is invariant under state gauges. It uses a fixed alphabet order and integer weights; changing either convention changes the surrounding compactness and comparison questions.

FPRD-T70 · theorem and sharp bound

Canonical inflation is controlled by access-tree geometry

Let $T$ be the pinned BFS access tree of a trim machine with $m$ states. Write $D$ for its depth and $\ell_T(e)$ for the length of the fundamental undirected tree cycle closed by a non-tree edge $e$ . Then

H(M)\le \max\!\left\{D+2,\max_{e\notin T}\ell_T(e)\right\}h(M) \le(m+1)h(M).

A canonical non-tree edge is a signed sum around its fundamental cycle. A canonical final weight contains the initial weight, one tree path, and the original final weight. These are exactly the two coefficients in the first maximum.

After minimizing among all horizon-correct machines with at most $n$ states,

h_{f,\le n}(N)\le H_{f,\le n}(N) \le(n+1)h_{f,\le n}(N).

The first inequality is not pointwise: a gauge can make one fixed machine's canonical height smaller than its raw height. It holds after minimization because the canonical form itself is a correct competitor in the same state-bounded section.

The coefficient is sharp. A unary target supported only at length $n-1$ , with value $n+1$ there, forces $n$ states. It has raw height one, while the canonical final coordinate on the accepting tree path is $n+1$ .

FPRD-T71 · theorem

The best raw gauge is a maximum mean circulation

Add a boundary vertex $\ast$ to the presentation graph. Represent the initial weight by an edge $\ast\to q_0$ and each finite final weight by an edge $q\to\ast$ . For an oriented closed walk $C$ , let $\operatorname{circ}_w(C)$ be the signed circulation and put

\rho(w)=\max_{C\ne\varnothing} \frac{|\operatorname{circ}_w(C)|}{|C|}.

\min_{z:V\to\mathbb R}\|w+\delta z\|_\infty=\rho(w), \qquad \min_{z:V\to\mathbb Z}\|w+\delta z\|_\infty =\lceil\rho(w)\rceil.

Circulations are gauge-invariant, proving the lower bound. For a proposed height $t$ , the inequalities on every gauged edge are a pair of difference constraints. Their auxiliary graph has no negative cycle exactly when $t\ge\rho(w)$ . Integral edge lengths give integral shortest-path potentials at $t=\lceil\rho(w)\rceil$ .

This is classical maximum-cycle-mean and difference-constraints duality applied to one fixed augmented presentation graph. It is infrastructure, not a novelty claim or a minimization over different automata.

The boundary vertex is load-bearing. Without its initial and final edges, a one-state machine with initial weight two and final weight minus two would appear to have an empty weighted graph even though its presentation height is two.

FPRD-T72 · theorem and explicit separation

A fixed target retains a linear gap after global repairs

For a partial integer-valued target $f$ , define

\widehat h_{f,\le n}(N)= \min_{\lambda,c\in\mathbb Z}h_{f+\lambda|\cdot|+c,\le n}(N), \qquad \widehat H_{f,\le n}(N)= \min_{\lambda,c\in\mathbb Z}H_{f+\lambda|\cdot|+c,\le n}(N).

Take $L_j=2^j$ and support words

w_j=\begin{cases} b^jca^{L_j},&j\text{ even},\\ b^jcd^{L_j},&j\text{ odd}, \end{cases} \qquad f(w_j)=\begin{cases}+L_j,&j\text{ even},\\-L_j,&j\text{ odd}. \end{cases}

The domain is exactly $\{w_j:j\ge0\}$ ; the target is undefined on every other word. For $k\ge3$ , at $N_k=k+1+2^k$ , the exact minimum state budget is $n_k=k+3\cdot2^{k-1}+2$ , and

\widehat h_{f,\le n_k}(N_k)=1, \qquad \widehat H_{f,\le n_k}(N_k)=3\cdot2^{k-2} =\left(\tfrac12-o(1)\right)n_k.

The minimum-state quotient forces one positive and one negative countdown carrier. A global length shift adds the same slope to both: it may cancel either carrier, but not both. The alternating boundary circulation therefore leaves one linear canonical obstruction while a raw ±1 weighting remains possible.

The lower bound counts the distinct spine, positive-countdown, negative-countdown, and final residuals. At the exact state budget those residuals force the comb graph and its shortest access tree, so the same-parity boundary edges cannot be removed by choosing a different presentation. The displayed $k\ge3$ hypothesis is part of the source theorem; it was missing from the earlier public summary.

This is one partial target on a fixed alphabet. It is not a total rational-series result. A simpler one-carrier witness collapses under the same repair and is not used as evidence.

FPRD-T73 · theorem and dichotomy

Unambiguous series have no intermediate height rate

Let $f$ have a trim unambiguous integer max-plus realization. In the precise twins property, two states reached by the same input word must assign equal weights to every nonempty input word that loops at both states. For a trim unambiguous automaton, this property is equivalent to sequentiality and to the recognized series being Lipschitz in the prefix metric (Klimann–Lombardy–Mairesse–Prieur, 2004).

If one input word reaches two states and a common nonempty loop word has circuit weights $x<y$ at those states, repeat that loop $m$ times and attach fixed accepting exits from the two states. Unambiguity exposes the two runs as exact values, whose difference is $(y-x)m+O(1)$ . Any deterministic horizon-correct machine of height $h$ sees the same repeated prefix and can create only an $O(h)$ difference across the two fixed exits. Hence $h=\Omega(N)$ .

Exactly one alternative holds:

$f$ is sequential, and state, raw-height, and canonical-height demand are bounded;
$f$ is nonsequential, and both heights are $\Theta(N)$ .

Unambiguity is essential: it makes each arm the unique accepting run of its witness word. The twins/sequentiality equivalence is a classical input; the finite-horizon height formulation is the result recorded here. Nonsequentiality alone does not prove that finite-horizon state demand diverges, so that assertion has been removed.

FPRD-T74 · theorem and exact counterexample

Ambiguity degree two breaks the dichotomy

Define

f_{\min}(w)=-\min(|w|_a,|w|_b) =\max(-|w|_a,-|w|_b).

The last expression gives an exact width-two cover by two one-state sequential machines. No single finite sequential machine is exact. Indeed $f_{\min}(w)=\max(|w|_a,|w|_b)-|w|$ ; Klimann–Lombardy–Mairesse–Prieur prove that max-count is not even unambiguous, and a global length shift preserves sequentiality and ambiguity degree. Thus the intrinsic ambiguity degree, as well as exact cover width, is exactly two.

For every $N\ge2$ ,

A^1_{f_{\min}}(N)=2\lfloor N/2\rfloor+1, \qquad h^1_{f_{\min}}(N)=H^1_{f_{\min}}(N)=1.

The lower bound uses the distinguishable signed differences $-\lfloor N/2\rfloor,\ldots,\lfloor N/2\rfloor$ . A tracker clamped to exactly that interval attains the bound. Its tree-access words carry value zero, so the machine is already in canonical height-one form.

State demand is therefore linear while both height coordinates remain constant. This is the exact boundary showing that the unambiguous dichotomy does not extend even to ambiguity degree two.

The restriction $N\ge2$ is sharp. Through horizon one the target is identically zero, so one state of raw and canonical height zero suffices.

Scope and open questions

Find a rational series whose optimal canonical height strictly decreases as additional states are allowed.
Compare the quantitative dichotomy with determinization and degree-of-sequentiality results.
Determine which graph classes improve the general $m+1$ coupling factor.
Test whether the repaired incompatible-carrier separation survives for a natural total target.

Sources

State-conditioned height coupling
Cycle-mean gauge duality
Parity-comb repaired separation
Weighted automaticity research note
Mehryar Mohri, “Finite-State Transducers in Language and Speech Processing,” Computational Linguistics 23(2), 1997, pp. 269–311 — classical weighted-transducer normalization context.
Richard M. Karp, “A Characterization of the Minimum Cycle Mean in a Digraph,” Discrete Mathematics 23(3), 1978, pp. 309–311 — the minimum-cycle-mean characterization used by the fixed-graph computation.
Ines Klimann, Sylvain Lombardy, Jean Mairesse, and Christophe Prieur, “Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton,” Theoretical Computer Science 327(3), 2004, pp. 349–373; arXiv:0709.4117 — supplies the exact twins/sequentiality/Lipschitz theorem and the max-count ambiguity-two boundary, not the FPRD finite-horizon height formulas.
Independent weighted-height boundary audit — checks 4,192 parity-comb prefix signatures, 200 integer gauges, 65,515 min-count words, 511 state-separation pairs, and the sharp small-horizon boundaries.
Independent finite audit output and checker source.

No documented external or specialist review of these FPRD results is recorded. The cited twins and maximum-cycle-mean ingredients are classical and are not presented as new.