Weighted automata and exact learning

Learning rational sequences

Exact coefficient prefixes determine a rational sequence once enough coefficients are known relative to its Hankel rank. Arbitrarily revisable polynomial snapshots are fundamentally different: pointwise stabilization alone does not permit a universal learner, even when the eventual target is rational.

FPRD-LRN-D01 · observation models

Exact prefixes and revisable snapshots are different data

Let $F(q)=\sum_{n\ge0}a_nq^n\in\mathbb Q[[q]].$ A rational series is equivalently a rational linear recurrence sequence, a finite-rank Hankel sequence, or the behavior of a finite-dimensional unary weighted automaton.

Exact prefix

At stage $N$ , the learner knows $a_0,\ldots,a_{N-1}$ . Every zero below the frontier is known as data.

Revisable snapshot

At stage $t$ , the learner sees a polynomial $P_t$ and is promised only

$\forall n\;\exists T_n\;\forall t\ge T_n: [q^n]P_t=a_n.$

The second promise gives no computable frontier below which the coefficients are known to be final.

FPRD-LRN-T01 · theorem

Exact prefixes recover rational sequences

Theorem. If $F$ has Hankel rank $0<r<\infty$ , then exactly $2r$ initial coefficients determine and reconstruct its minimal recurrence. If a bound $R\ge r$ is known, $2R$ coefficients give certified exact reconstruction. Without a known rank bound, repeating the reconstruction on longer prefixes identifies $F$ in the limit. The rank-zero class consists only of the zero series.

Proof. Berlekamp–Massey over $\mathbb Q$ recovers the shortest connection polynomial from $2r$ samples of a sequence of linear complexity $r$ . Multiplying that polynomial by the observed generating prefix recovers the numerator.

For uniqueness, suppose two rank-at-most- $r$ series agree through degree $2r-1$ . Their difference has Hankel rank at most $2r$ . A nonzero sequence whose first nonzero coefficient occurs at index $m$ has an anti-triangular leading Hankel block of rank $m+1$ . The difference therefore must vanish. ∎

The count is sharp. For $r\ge1$ , split the nodes $0,1,\ldots,2r-1$ by parity:

F_r(q)=\sum_{\substack{0\le j<2r\\ j\text{ even}}} \frac{\binom{2r-1}{j}}{1-jq},\qquad G_r(q)=\sum_{\substack{0\le j<2r\\ j\text{ odd}}} \frac{\binom{2r-1}{j}}{1-jq}.

Each side has Hankel rank $r$ by the Vandermonde factorization. The finite-difference identity says their coefficients agree through degree $2r-2$ and differ in degree $2r-1$ . Thus $2r-1$ observations can never suffice uniformly.

The arithmetic operation count is polynomial in the observed prefix length. Rational numerator and denominator growth still matters for bit complexity.

FPRD-LRN-C01 · counterexample

No finite prefix certifies an unrestricted guess

After observing coefficients through degree $N-1$ , compare

$F(q)\qquad\text{and}\qquad F(q)+\frac{cq^N}{1-\lambda q},\quad c\ne0.$

Both are rational and agree on the entire observed prefix, yet they are different. Thus an unknown-rank learner may converge to the right answer, but cannot truthfully announce from finite data alone that its current hypothesis will never change.

FPRD-LRN-T02 · impossibility theorem

Pointwise stabilization is not enough

Theorem. No learner identifies every rational target in the limit from arbitrary polynomial snapshots whose coefficients merely stabilize pointwise.

Proof. Assume a learner succeeds on every such stream. Choose a fresh exponent $k$ . If the current finite history were followed forever by the constant snapshot $q^k$ , success would force the learner eventually to output that monomial. Repeat $q^k$ just long enough to reach such a stage, then choose a larger fresh exponent and continue.

Every fixed coefficient is nonzero in at most one block, so the constructed snapshots converge coefficientwise to the zero series. But the learner is forced to output nonzero monomials infinitely often and therefore does not converge to zero. ∎

This is stronger than a slow-convergence warning: under the bare promise there is no universally correct limit learner.

FPRD-LRN-B01 · research boundary

What can restore a positive theorem

Revisable program approximants can still support exact learning if their semantics provide usable finality information. Examples include a computable stabilization modulus, markers certifying a coefficient prefix, monotone sound bounds with an effective gap test, a detectable revision bound, or active coefficient and equivalence queries.

The next mathematical step is therefore to recover what the motivating program analysis guarantees about its approximants. Recurrence fitting alone cannot manufacture that guarantee.

Sources

Problem source. Learning sequences, contributed by Benjamin Kaminski.

James L. Massey, Shift-Register Synthesis and BCH Decoding, IEEE Transactions on Information Theory 15(1), 1969, pp. 122–127. This is the recurrence-synthesis source used by the exact-prefix theorem.
Jean Berstel and Christophe Reutenauer, Minimization, in Noncommutative Rational Series with Applications, Cambridge University Press, 2010, pp. 29–46. This supplies the Hankel-rank/minimal-linear-representation equivalence.
E. Mark Gold, Language Identification in the Limit, Information and Control 10(5), 1967, pp. 447–474. Gold supplies the classical convergence criterion, not this page's coefficient presentation.
Francesco Bergadano and Stefano Varricchio, Learning Behaviors of Automata from Multiplicity and Equivalence Queries, SIAM Journal on Computing 25(6), 1996, pp. 1268–1280.
Laure Daviaud and Marianne Johnson, Feasability of Learning Weighted Automata on a Semiring, Logical Methods in Computer Science 21(3), article 15, 2025, pp. 15:1–15:36, arXiv:2309.07806.

Gold's positive-text model and the active query models in the cited weighted-automata literature are not the same as exact coefficient prefixes or arbitrary revisable snapshots.

Independent review evidence. Scope and reproduction instructions, exact checker, and committed output, with its hash certificate.