Lax765601.FlipFlopsOfAperiodic
Aperiodic Mealy machines are compositions of flip-flops
concepts/Lax765601/FlipFlopsOfAperiodic.lean · lax-765601
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
In the paper
- page 28 of the paper of lax-157538, Transducers
Theorem
Every aperiodic function computed by a Mealy machine is computed by a composition of flip-flop Mealy machines: the implication "aperiodic composition of flip-flops" of Theorem A.2.8 of Transducers, the hard half. By Lemma A.2.11 the function is computed by a machine whose state transformations satisfy the stabilisation condition (); the proof of the Krohn–Rhodes theorem is then run for this machine, and every machine arising in the induction inherits (), since it only uses state transformations of the original one, so that no reversible machine with more than one state ever appears and every prime in the decomposition is a flip-flop.
Lean source view on GitHub
| 1 | import Lax765601.PrimeMealyMachines |
| 2 | import Lax765601.Aperiodicity |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Aperiodic Mealy machines are compositions of flip-flops |
| 7 | type: theorem |
| 8 | --- |
| 9 | Every aperiodic function computed by a Mealy machine is computed by a |
| 10 | composition of flip-flop Mealy machines: the implication "aperiodic |
| 11 | composition of flip-flops" of Theorem A.2.8 of *Transducers*, the |
| 12 | hard half. By Lemma A.2.11 the function is computed by a machine whose state |
| 13 | transformations satisfy the stabilisation condition (*); the proof of the |
| 14 | Krohn–Rhodes theorem is then run for this machine, and every machine arising in |
| 15 | the induction inherits (*), since it only uses state transformations of the |
| 16 | original one, so that no reversible machine with more than one state ever |
| 17 | appears and every prime in the decomposition is a flip-flop. |
| 18 | |
| 19 | # Formalization notes |
| 20 | |
| 21 | The two alphabets are assumed finite, as for the Krohn–Rhodes theorem, whose |
| 22 | construction this statement repeats inside the class of flip-flops. The |
| 23 | conclusion is membership in `CompClosure FlipFlopFam`. |
| 24 | -/ |
| 25 | |
| 26 | namespace Lax765601.FlipFlopsOfAperiodic |
| 27 | |
| 28 | open Lax765601.MealyMachine Lax765601.CompositionClosure Lax765601.PrimeMealyMachines Lax765601.Aperiodicity |
| 29 | |
| 30 | /-- An aperiodic function computed by a Mealy machine is a composition of flip-flop |
| 31 | Mealy machines. -/ |
| 32 | axiom compClosure_flipFlop_of_aperiodic {A B : Type} [Finite A] [Finite B] |
| 33 | {f : List A → List B} (hf : IsMealy f) (ha : Aperiodic f) : |
| 34 | CompClosure FlipFlopFam A B f |
| 35 | |
| 36 | end Lax765601.FlipFlopsOfAperiodic |
| 37 |
Formalization notes
The two alphabets are assumed finite, as for the Krohn–Rhodes theorem, whose construction this statement repeats inside the class of flip-flops. The conclusion is membership in .
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