Draft — mutable and not usable as a dependency; its citation marks the draft state.

Proof of `Every for-transducer has a prenex form`

groundedproofs/Lax194892Proofs/Results.lean · lax-194892

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

In the paper

Description

Every for-transducer is equivalent to one in prenex form (Lemma D.1.3), Transducers.forTransducerprenexTransducers.forTransducer_prenex.

Proof strategy

The source pulls the loops to the front one at a time, replacing a loop nested under a conditional or followed by further code by a loop whose body tests a Boolean flag recording the position in the original control flow (PartD/ForPrenex.leanPartD/ForPrenex.lean, PartD/ForNest.leanPartD/ForNest.lean, PartD/ForMerge.leanPartD/ForMerge.lean). The concept's prenex form is transported through prenexFormtoSrcProgprenexForm_toSrcProg: loop freedom, nesting of loops and the one-output bound all commute with toSrcProgtoSrcProg, so the source's prenex program comes back as ofSrcProgofSrcProg of it, with the same semantics by evalofSrcProgeval_ofSrcProg.

Attribution

Lemma D.1.3 of Transducers, Part D; formalised by Aristotle (Harmonic).