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

Proof of `Pebble transducers are continuous`

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

Pebble transducers compute continuous functions (Theorem D.2.1), Transducers.pebblecontinuousTransducers.pebble_continuous.

Proof strategy

The source proves the regularity of the languages recognised by pebble automata (a pebble transducer whose output is a single accepting bit) by induction on the number of pebbles, the top pebble being eliminated by a two-way automaton that guesses the run of the automaton below it (PartD/PebbleLev1.leanPartD/PebbleLev1.lean, PartD/PebbleAut.leanPartD/PebbleAut.lean, PartD/PebbleReg.leanPartD/PebbleReg.lean); the inverse image of a regular language under the transducer is then recognised by a pebble automaton. The concept's pebble transducers are transported by toSrcPebtoSrcPeb, whose configuration graph is that of the concept's transducer (stepCfgtoSrcPebstepCfg_toSrcPeb, reachestoSrcPebreaches_toSrcPeb), giving isPebbleTransduceriffisPebbleTransducer_iff.

Attribution

Theorem D.2.1 of Transducers, Part D; formalised by Aristotle (Harmonic).