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

Lax765601.AperiodicityMinimalMachine

Aperiodicity through the state transformations of the minimal machine

concepts/Lax765601/AperiodicityMinimalMachine.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

    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 δ:QQ\delta : Q \to Q that arises from some input string, the sequence δ1,δ2,\delta^1, \delta^2, \ldots eventually stabilises on a single state transformation (Lemma A.2.11 of Transducers). If any machine computing ff satisfies (), then ff is aperiodic; conversely, if the minimal machine violates (*) for the state transformation of a string vv, then two powers δiδj\delta^i \neq \delta^j recur infinitely often, and minimality yields strings u,wu, w for which the last letters of f(uviw)f(u v^i w) and f(uvjw)f(u v^j w) differ, contradicting aperiodicity. This lemma is what the book's decision procedure for aperiodicity rests on.

    Lean source view on GitHub

    1import Lax765601.MealyMachine
    2import Lax765601.StateTransformations
    3import Lax765601.Aperiodicity
    4
    5/-!
    6---
    7title: Aperiodicity through the state transformations of the minimal machine
    8type: theorem
    9---
    10A function computed by a Mealy machine is aperiodic if and only if its minimal
    11Mealy machine satisfies the stabilisation condition (*): for every state
    12transformation δ:QQ\delta : Q \to Q that arises from some input string, the
    13sequence δ1,δ2,\delta^1, \delta^2, \ldots eventually stabilises on a single state
    14transformation (Lemma A.2.11 of *Transducers*). If any machine computing ff
    15satisfies (*), then ff is aperiodic; conversely, if the minimal machine violates
    16(*) for the state transformation of a string vv, then two powers δiδj\delta^i \neq \delta^j
    17 recur infinitely often, and minimality yields strings u,wu, w for which
    18the last letters of f(uviw)f(u v^i w) and f(uvjw)f(u v^j w) differ, contradicting
    19aperiodicity. This lemma is what the book's decision procedure for aperiodicity
    20rests on.
    21
    22# Formalization notes
    23
    24The minimal machine is not constructed. Condition (*) is inherited by the
    25minimal machine from any machine that has it, so "the minimal machine of ff
    26satisfies (*)" is equivalent to "some Mealy machine computing ff satisfies (*)",
    27which is the form stated: `TransAperiodic M.transFun` is condition (*) for the
    28pre-automaton underlying `M`. The book's finiteness assumptions on the alphabets
    29are not used and are dropped.
    30-/
    31
    32namespace Lax765601.AperiodicityMinimalMachine
    33
    34open Lax765601.MealyMachine Lax765601.StateTransformations Lax765601.Aperiodicity
    35
    36/-- A Mealy function is aperiodic if and only if some Mealy machine computing it
    37satisfies the stabilisation condition (*) on its state transformations. -/
    38axiom 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
    42end Lax765601.AperiodicityMinimalMachine
    43
    Show Proof

    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 ff satisfies ()" is equivalent to "some Mealy machine computing ff satisfies ()", which is the form stated: TransAperiodicM.transFunTransAperiodic M.transFun is condition () for the pre-automaton underlying MM. The book's finiteness assumptions on the alphabets are not used and are dropped.

    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…