Lax132576.RationalMealyCharacterisation
Which rational functions are Mealy machines
concepts/Lax132576/RationalMealyCharacterisation.lean · lax-132576
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 50 of the paper of lax-157538, Transducers
Theorem
A rational function is computed by a Mealy machine if and only if it is letter-to-letter — the output has the length of the input — and deterministic: input strings that agree on their first letters have outputs that agree on their first letters (Theorem B.2.7 of Transducers). Mealy machines are the special case of the rational functions that the theorem pins down; the proof goes through the machine-independent characterisation of Theorem B.4.1, since a rational function is continuous.
Lean source view on GitHub
| 1 | import Lax765601.MealyMachine |
| 2 | import Lax765601.ElementaryProperties |
| 3 | import Lax132576.RationalFunctions |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Which rational functions are Mealy machines |
| 8 | type: theorem |
| 9 | --- |
| 10 | A rational function is computed by a Mealy machine if and only |
| 11 | if it is letter-to-letter — the output has the length of the input — and |
| 12 | deterministic: input strings that agree on their first letters have outputs |
| 13 | that agree on their first letters (Theorem B.2.7 of *Transducers*). Mealy |
| 14 | machines are the special case of the rational functions that the theorem |
| 15 | pins down; the proof goes through the machine-independent characterisation of |
| 16 | Theorem B.4.1, since a rational function is continuous. |
| 17 | |
| 18 | # Formalization notes |
| 19 | |
| 20 | "Letter-to-letter" is `LengthPreserving` and "deterministic" is |
| 21 | `PrefixDetermined` of `Lax765601.ElementaryProperties`. Both alphabets are |
| 22 | assumed finite, as Theorem B.4.1 needs. |
| 23 | -/ |
| 24 | |
| 25 | namespace Lax132576.RationalMealyCharacterisation |
| 26 | |
| 27 | open Lax765601.MealyMachine Lax765601.ElementaryProperties Lax132576.RationalFunctions |
| 28 | |
| 29 | /-- A rational function is computed by a Mealy machine if and only if it is |
| 30 | letter-to-letter and prefix determined. -/ |
| 31 | axiom isMealy_iff_of_isRationalFun {A B : Type} [Finite A] [Finite B] {f : List A → List B} |
| 32 | (hf : IsRationalFun f) : IsMealy f ↔ LengthPreserving f ∧ PrefixDetermined f |
| 33 | |
| 34 | end Lax132576.RationalMealyCharacterisation |
| 35 |
Formalization notes
"Letter-to-letter" is and "deterministic" is of . Both alphabets are assumed finite, as Theorem B.4.1 needs.
Used by
none
From Mathlib
none
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