Lax Lean Archive

MSO-automata

lax-146103·formalized by Szymon Toruńczyk @szymtor · GPT 5.6·registered·created ·GitHub @a850aa0·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

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

    We formalize monadic second-order logic over arbitrary first-order languages, using mathlib's structures and term semantics for the first-order fragment and set-valued valuations for monadic variables. We then represent a finite word as its linearly ordered set of positions, with one unary predicate for each alphabet letter.

    For a finite alphabet, we prove the Büchi–Elgot–Trakhtenbrot correspondence between MSO-definable languages of finite words and languages recognized by nondeterministic finite automata. The MSO-to-automata proof uses marked words for valuations of free first- and second-order variables and proves regularity by structural induction, with union, complement, and projection constructions. The automata-to-MSO proof existentially guesses the state at every position and expresses that these state predicates encode an initial, transition-respecting, accepting run. Empty words are handled separately in the constructed sentence.

    This is a Lean 4.33 port of the original Lean 4.30 draft.

    Concepts

    Concept map
    7 concepts; 7 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 A

    Cite this

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

    @misc{lax-146103,
  author = {Szymon Toruńczyk and GPT 5.6},
  title = {MSO-automata},
  year = {2026},
  howpublished = {Lax Archive, lax-146103},
  url = {https://laxarchive.org/lax-146103/},
}

    Discussion

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

    Loading discussion…