Lax916827.RegularOfTwoWay
Every two-way transducer computes a regular function
concepts/Lax916827/RegularOfTwoWay.lean · lax-916827
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 98 of the paper of lax-157538, Transducers
Theorem
Every function computed by a two-way transducer is regular, i.e. decomposes into rational functions, map reverse and map duplicate (Theorem C.2.9 of Transducers, the hard implication). The run of the transducer is described by its snake graph, computed by a rational function, and the output of a snake graph of width at most is a regular function of its representation (the snake lemma, Lemma C.2.12), by induction on the width: a snake of width is cut, at the record-breaking columns, into looping and progressing parts of smaller width, whose outputs are computed by the induction hypothesis on factors cut out by rational functions and glued back by the closure properties of Lemma C.2.10. A run that halts visits every column at most times, so the transducer's function is its own width- snake output.
Lean source view on GitHub
| 1 | import Lax916827.RegularFunctions |
| 2 | import Lax916827.TwoWayTransducers |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Every two-way transducer computes a regular function |
| 7 | type: theorem |
| 8 | --- |
| 9 | Every function computed by a two-way transducer is regular, i.e. decomposes |
| 10 | into rational functions, map reverse and map duplicate (Theorem C.2.9 of |
| 11 | *Transducers*, the hard implication). The run of the transducer is described by |
| 12 | its *snake graph*, computed by a rational function, and the output of a snake |
| 13 | graph of width at most is a regular function of its representation (the |
| 14 | snake lemma, Lemma C.2.12), by induction on the width: a snake of width is |
| 15 | cut, at the record-breaking columns, into looping and progressing parts of |
| 16 | smaller width, whose outputs are computed by the induction hypothesis on factors |
| 17 | cut out by rational functions and glued back by the closure properties of |
| 18 | Lemma C.2.10. A run that halts visits every column at most times, so the |
| 19 | transducer's function is its own width- snake output. |
| 20 | |
| 21 | # Formalization notes |
| 22 | |
| 23 | Both alphabets are assumed finite, as in the book. |
| 24 | -/ |
| 25 | |
| 26 | namespace Lax916827.RegularOfTwoWay |
| 27 | |
| 28 | open Lax916827.RegularFunctions Lax916827.TwoWayTransducers |
| 29 | |
| 30 | /-- A function computed by a two-way transducer is regular. -/ |
| 31 | axiom isRegularFun_of_isTwoWay {A B : Type} [Finite A] [Finite B] {f : List A → List B} |
| 32 | (hf : IsTwoWay f) : IsRegularFun f |
| 33 | |
| 34 | end Lax916827.RegularOfTwoWay |
| 35 |
Formalization notes
Both alphabets are assumed finite, as in the book.
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments