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

Proof of `A for-transducer produces the child configuration graph`

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

A for-transducer maps the string representation of a configuration to the representation of its child configuration graph (Claim D.2.6), Transducers.fromconfigurationtochildconfigurationgraphTransducers.from_configuration_to_child_configuration_graph.

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 (PartD/CGLang.leanPartD/CGLang.lean, PartD/CGAtom.leanPartD/CGAtom.lean, PartD/CGSem.leanPartD/CGSem.lean), 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 cgLetterOfSrccgLetterOfSrc, itself a for-transducer (isForTransducermapisForTransducer_map), and the two representations agree under the bijection (cgOfChildrentoSrccgOfChildren_toSrc).

Attribution

Claim D.2.6 of Transducers, Part D; formalised by Aristotle (Harmonic), PartD/CGFor.leanPartD/CGFor.lean.