Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax765601.FlipFlopsOfAperiodic

Aperiodic Mealy machines are compositions of flip-flops

concepts/Lax765601/FlipFlopsOfAperiodic.lean · lax-765601

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Evidence

    Each proof establishes this claim relative to its assumptions.

    In the paper

    Theorem

    Every aperiodic function computed by a Mealy machine is computed by a composition of flip-flop Mealy machines: the implication "aperiodic \Rightarrow 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

    1import Lax765601.PrimeMealyMachines
    2import Lax765601.Aperiodicity
    3
    4/-!
    5---
    6title: Aperiodic Mealy machines are compositions of flip-flops
    7type: theorem
    8---
    9Every aperiodic function computed by a Mealy machine is computed by a
    10composition of flip-flop Mealy machines: the implication "aperiodic
    11\Rightarrow composition of flip-flops" of Theorem A.2.8 of *Transducers*, the
    12hard half. By Lemma A.2.11 the function is computed by a machine whose state
    13transformations satisfy the stabilisation condition (*); the proof of the
    14Krohn–Rhodes theorem is then run for this machine, and every machine arising in
    15the induction inherits (*), since it only uses state transformations of the
    16original one, so that no reversible machine with more than one state ever
    17appears and every prime in the decomposition is a flip-flop.
    18
    19# Formalization notes
    20
    21The two alphabets are assumed finite, as for the Krohn–Rhodes theorem, whose
    22construction this statement repeats inside the class of flip-flops. The
    23conclusion is membership in `CompClosure FlipFlopFam`.
    24-/
    25
    26namespace Lax765601.FlipFlopsOfAperiodic
    27
    28open Lax765601.MealyMachine Lax765601.CompositionClosure Lax765601.PrimeMealyMachines Lax765601.Aperiodicity
    29
    30/-- An aperiodic function computed by a Mealy machine is a composition of flip-flop
    31Mealy machines. -/
    32axiom 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
    36end Lax765601.FlipFlopsOfAperiodic
    37
    Show Proof

    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 CompClosureFlipFlopFamCompClosure FlipFlopFam.

    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

    Loading discussion…