Proof of `Polynomial automata and Hadamard automata`

groundedproofs/Lax619925Proofs/PolynomialAutomata.lean · lax-619925

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

A series is recognisable by a polynomial automaton iff its reversal is Hadamard-finite (paper appendix). Only-if: the component series gi(w)=πi(qI⋅wR)g_i(w) = π_i(q_I · w^R) generate a Hadamard algebra closed under left derivatives containing fR=F(g1,…,gk)f^R = F(g_1, …, g_k). If: from a left-derivative- closed Hadamard algebra Qg1,…,gkℚ{g_1, …, g_k} containing fR=F(g1,…,gk)f^R = F(g_1, …, g_k), rebuild the polynomial automaton with initial state (g1(ε),…,gk(ε))(g_1(ε), …, g_k(ε)) and transitions given by the left-derivative polynomials; an induction on the word shows gi(w)=πi(qI⋅wR)g_i(w) = π_i(q_I · w^R), hence f=⟦B⟧f = ⟦B⟧.