Lax765601.AperiodicityMinimalMachine
Aperiodicity through the state transformations of the minimal machine
concepts/Lax765601/AperiodicityMinimalMachine.lean · lax-765601
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 29 of the paper of lax-157538, Transducers
Theorem
A function computed by a Mealy machine is aperiodic if and only if its minimal Mealy machine satisfies the stabilisation condition (): for every state transformation that arises from some input string, the sequence eventually stabilises on a single state transformation (Lemma A.2.11 of Transducers). If any machine computing satisfies (), then is aperiodic; conversely, if the minimal machine violates (*) for the state transformation of a string , then two powers recur infinitely often, and minimality yields strings for which the last letters of and differ, contradicting aperiodicity. This lemma is what the book's decision procedure for aperiodicity rests on.
Lean source view on GitHub
| 1 | import Lax765601.MealyMachine |
| 2 | import Lax765601.StateTransformations |
| 3 | import Lax765601.Aperiodicity |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Aperiodicity through the state transformations of the minimal machine |
| 8 | type: theorem |
| 9 | --- |
| 10 | A function computed by a Mealy machine is aperiodic if and only if its minimal |
| 11 | Mealy machine satisfies the stabilisation condition (*): for every state |
| 12 | transformation that arises from some input string, the |
| 13 | sequence eventually stabilises on a single state |
| 14 | transformation (Lemma A.2.11 of *Transducers*). If any machine computing |
| 15 | satisfies (*), then is aperiodic; conversely, if the minimal machine violates |
| 16 | (*) for the state transformation of a string , then two powers |
| 17 | recur infinitely often, and minimality yields strings for which |
| 18 | the last letters of and differ, contradicting |
| 19 | aperiodicity. This lemma is what the book's decision procedure for aperiodicity |
| 20 | rests on. |
| 21 | |
| 22 | # Formalization notes |
| 23 | |
| 24 | The minimal machine is not constructed. Condition (*) is inherited by the |
| 25 | minimal machine from any machine that has it, so "the minimal machine of |
| 26 | satisfies (*)" is equivalent to "some Mealy machine computing satisfies (*)", |
| 27 | which is the form stated: `TransAperiodic M.transFun` is condition (*) for the |
| 28 | pre-automaton underlying `M`. The book's finiteness assumptions on the alphabets |
| 29 | are not used and are dropped. |
| 30 | -/ |
| 31 | |
| 32 | namespace Lax765601.AperiodicityMinimalMachine |
| 33 | |
| 34 | open Lax765601.MealyMachine Lax765601.StateTransformations Lax765601.Aperiodicity |
| 35 | |
| 36 | /-- A Mealy function is aperiodic if and only if some Mealy machine computing it |
| 37 | satisfies the stabilisation condition (*) on its state transformations. -/ |
| 38 | axiom aperiodic_iff_transAperiodic {A B : Type} {f : List A → List B} (hf : IsMealy f) : |
| 39 | Aperiodic f ↔ |
| 40 | ∃ (Q : Type) (_ : Finite Q) (M : Mealy A B Q), M.eval = f ∧ TransAperiodic M.transFun |
| 41 | |
| 42 | end Lax765601.AperiodicityMinimalMachine |
| 43 |
Formalization notes
The minimal machine is not constructed. Condition () is inherited by the minimal machine from any machine that has it, so "the minimal machine of satisfies ()" is equivalent to "some Mealy machine computing satisfies ()", which is the form stated: is condition () for the pre-automaton underlying . The book's finiteness assumptions on the alphabets are not used and are dropped.
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