Proof of `Shuffle automata and shuffle-finite series` (3rd statement)

groundedproofs/Lax619925Proofs/Shuffle.lean · lax-619925

What this proof establishes

no assumptions

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

The shuffle coincidence theorem (paper §6): a series is shuffle-finite (a shuffle polynomial in a finite tuple of series closed under the left derivatives) if and only if it is recognised by a shuffle automaton. The "finite implies recognisable" direction extends the witnessing tuple by the series itself and builds the automaton from the closure under left derivatives; the "recognisable implies finite" direction reads off the generator tuple A.sem(Xi)A.sem (X_i), closed under left derivatives by the derivation property.