Proof of `Pebble transducers are continuous`
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 165 of the paper of lax-157538, Transducers
Description
Pebble transducers compute continuous functions (Theorem D.2.1), .
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 (, , ); 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 , whose configuration graph is that of the concept's transducer (, ), giving .
Attribution
Theorem D.2.1 of Transducers, Part D; formalised by Aristotle (Harmonic).