Proof of `Shuffle automata and shuffle-finite series` (6th statement)
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.
Description
The equality (zeroness) problem is decidable for shuffle automata over a finite alphabet (paper §6). As in the Hadamard case, the orbit-ideal chain stabilises by Hilbert's basis theorem (), and the stabilised ideal is a bi-ideal, so the zeroness of the recognised series is characterised by the finite statement (). The only difference from the Hadamard case is the transition invariance (): the letter map is a derivation (ℚ-linear, not a ring hom), so instead of one decomposes as a finite -linear combination of orbit-set elements and applies the Leibniz rule termwise. The kernel is finitely generated (, by Noetherianity), so this finite statement is a batch of ideal-membership queries , each decided by ; the decision is the Boolean "and" of these queries over the (finite) orbit set.