Proof of `Infiltration automata and infiltration-finite series` (6th statement)
groundedproofs/Lax619925Proofs/Infiltration.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.
Description
The equality (zeroness) problem is decidable for infiltration automata over a finite alphabet (paper §7). As in the Hadamard and shuffle cases, 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 other two classes is the transition invariance (): the letter map is an infiltration (ℚ-linear, neither a ring hom nor a derivation), so instead of (Hadamard) or the Leibniz rule (shuffle) one decomposes as a finite -linear combination of orbit-set elements and applies the infiltration product 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.