Proof of `Every for-transducer has a prenex form`
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.
In the paper
- page 159 of the paper of lax-157538, Transducers
Description
Every for-transducer is equivalent to one in prenex form (Lemma D.1.3), .
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 (, , ). The concept's prenex form is transported through : loop freedom, nesting of loops and the one-output bound all commute with , so the source's prenex program comes back as of it, with the same semantics by .
Attribution
Lemma D.1.3 of Transducers, Part D; formalised by Aristotle (Harmonic).