Proof of `A for-transducer produces the child configuration graph`
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 170 of the paper of lax-157538, Transducers
Description
A for-transducer maps the string representation of a configuration to the representation of its child configuration graph (Claim D.2.6), .
Proof strategy
The source computes every letter of the child configuration graph by a rational function: each of its finitely many components — the fixed pebbles, the first child in the column, and the outgoing and incoming edges of every state — is a regular property of the input marked at the gap, decided by the regular languages of Claim D.2.3 (, , ), and a rational function is a for-transducer by Theorem D.1.1. The concept's letters form a distinct structure from the source's; the source's for-transducer is post-composed with the letter-to-letter bijection , itself a for-transducer (), and the two representations agree under the bijection ().
Attribution
Claim D.2.6 of Transducers, Part D; formalised by Aristotle (Harmonic), .