Transducers, Part A: Mealy Machines

lax-765601·formalized by Mikołaj Bojańczyk · Aristotle (Harmonic)·registered·created ·GitHub @6980467·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Sign in with ORCID

Community review

Flags

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

No flags have been submitted.

    Community review

    Flag this submission

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

    Abstract

    Part A of the book Transducers (M. Bojańczyk), together with the definition of its introduction, as concepts and proofs. The Lean development is Aristotle's formalisation of the book, re-presented in the archive's form: the definitions and statements of the book are the concept package, and the original development is the proof package.

    The definition-concepts are continuity (Definition 0.1: the inverse image of every regular language is regular), the closure of a family of functions under composition through finite alphabets (the "composition of primes" idiom of every transducer class of the book), Mealy machines and the functions they compute, their state transformations, the prime Mealy machines (reversible and flip-flop), map lifting, aperiodicity, and the derivatives of a string-to-string function.

    The theorem-concepts are the numbered results of Part A: decidable equivalence of Mealy machines in the form of a finite check on inputs of length at most the product of the numbers of states (A.1.2), closure under composition (A.1.3), continuity (A.1.4), the Krohn–Rhodes theorem that every Mealy machine is a composition of reversible and flip-flop machines (A.2.2), its two lemmas on map lifting (A.2.4) and on the state transformation transducer of a pre-automaton (A.2.5), closure of reversible machines under composition (A.2.6), the characterisation of aperiodic Mealy functions as the compositions of flip-flops (A.2.8, stated as its two implications and their conjunction), aperiodicity as a pumping property (A.2.9), the Myhill–Nerode lemma for Mealy machines (A.2.10), and the stabilisation condition on the minimal machine (A.2.11). All of them are proved.

    Two statements are not the printed ones. Aperiodicity (A.2.7) asks for the last letter of f(uvnw)f(uv^nw) as an element of B+1B + 1, since with u=v=w=εu = v = w = \varepsilon there is no last letter and the printed definition is unsatisfiable; and Lemma A.2.11 speaks of some machine computing ff rather than of the minimal machine, which it does not construct. The decidability sentence of Theorem A.2.8 is not formalised. The exercises of Part A are not part of this submission.

    In the paper

    Concepts

    Concept map
    22 concepts; 56 descendants hidden
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-765601,
      author = {Mikołaj Bojańczyk and Aristotle (Harmonic)},
      title = {Transducers, Part A: Mealy Machines},
      year = {2026},
      howpublished = {Lax Archive, lax-765601},
      url = {https://laxarchive.org/lax-765601/},
    }

    References

    1. Mikołaj Bojańczyk. Transducers. 2026. Book in preparation; sources at https://github.com/bojanczyk/transducer-book.
    2. Kenneth Krohn and John Rhodes. Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines. Transactions of the American Mathematical Society 116:450–464, 1965. doi:10.2307/1994127

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…