Transducers, Part A: Mealy Machines
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
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 as an element of , since with there is no last letter and the printed definition is unsatisfiable; and Lemma A.2.11 speaks of some machine computing 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
- page 12 of the paper of lax-157538, Transducers
Concepts
- def
Lax765601.Aperiodicity - thm✓
Lax765601.AperiodicityMinimalMachine - thm✓
Lax765601.AperiodicMealy - thm✓
Lax765601.AperiodicOfFlipFlops - thm✓
Lax765601.AperiodicPumping - def
Lax765601.CompositionClosure - def
Lax765601.Continuity - def
Lax765601.Derivatives - def
Lax765601.ElementaryProperties - thm✓
Lax765601.FlipFlopsOfAperiodic - thm✓
Lax765601.KrohnRhodes - def
Lax765601.MapLifting - thm✓
Lax765601.MapLiftingDecomposition - thm✓
Lax765601.MealyComposition - thm✓
Lax765601.MealyContinuity - thm✓
Lax765601.MealyDerivatives - thm✓
Lax765601.MealyEquivalenceBound - def
Lax765601.MealyMachine - def
Lax765601.PrimeMealyMachines - thm✓
Lax765601.ReversibleComposition - thm✓
Lax765601.StateTransformationDecomposition - def
Lax765601.StateTransformations
Concept map
Proofs
Proof networkview on GitHub
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
Cite this
@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/},
note = {draft},
}
References
- Mikołaj Bojańczyk. Transducers. 2026. Book in preparation; sources at r̆lhttps://github.com/bojanczyk/transducer-book.
- 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
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