While this submission is a draft, it cannot be used by other submissions.

Bisimulation-invariant MSO on finite graphs

Lax369799.FiniteBisimulationTheorem · concepts/Lax369799/FiniteBisimulationTheorem.lean · lax-369799

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.

    Natural Language Statement

    Theorem

    For a finite set of proposition letters, a property of finite reachable transition systems is MSO-definable and bisimulation-invariant if and only if it is definable in the modal mu-calculus. This is the main theorem theorem:bisim−invariant−finitetheorem:bisim-invariant-finite of Colcombet, Doumane and Kuperberg, revised local manuscript of 13 November 2026. Invariance is required only between finite systems.

    Concept map
    62 concepts
    100%
    A common condition for finite and infinitealgebraic branch wordsThe algebraic condition on infinite branchwordsAlgebras and recognitionClone-automataClone-automaton normal form and modaltranslationCombining finite and infinite branchconditionsEffective translation of bisimulation-invariantfinite MSOYield acceptance of finite presentationsBisimulation-invariant MSO on finite graphsFinite-state evaluation of terminating branchwordsContexts over finite presentationsContextual preorders on finite presentationsExecutable modal compilation from finiteBoolean tablesExecutable finite model checking for bothlogicsScalar formulas for finite fixed-point equationsystemsPositional determinacy of finite parity gamesFinite presentations without reachabilitypruningContextual quotient algebras of finitepresentationsExecutable bounded comparison of MSO andmodal formulasFixed points through a monotone retractionFlattening and contextsFlattening, resolutions, and yield congruenceInfinite Ramsey theorem for pairsMSO-definable languages are algebraicallyrecognisableThe finite modal acceptance gameModal equations on input verticesModal mu-calculusSmall finite models for modal parityacceptanceModal transitions obtained from typesupportsMonadic second-order logic on transitionsystemsMorphisms, unfoldings, and yieldsSubstitution in modal fixed-point formulasDeterminization of infinite-word automataRegular infinite products of linked pairsEliminating one priority by a fixed pointNested fixed-point equations for finite paritygamesWinning regions and controlled predecessorsExecutable compilation of modal priorityequationsQuantitative automata for the finitebisimulation theoremExplicit state and priority bounds for worddeterminizationA computable finite-model bound underbisimulation invarianceComputable bounds on the syntactic nullaryand unary sortsComputable bounds for MSO recognizingalgebrasComputable bounds for the algebraic branchautomatonRanked sets, set-systems, and systemsRenaming variables in systems andresolutionsResolutions and bounded profilesStable factorization with recurrent verticesThe earlier continuity-bearing set-algebrainterfacePure second-order syntaxTranslation to pure second-order logicAlgebras on fully supported systemsSystems with all output variables reachableYield-syntactic order and quotientRanked encodings of transition systemsFinite transition systems and bisimulationThe unary semigroup and its actionStable factorization of algebraic branchwordsUnfold-automata and regular-tree acceptanceLogic on arbitrary transition systemsArbitrary transition systems andbisimulationsIdempotent factorization of infinite words
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.EffectiveFiniteTranslation
    2import Lax369799.MonadicSecondOrder
    3import Lax369799.ModalMuCalculus
    4
    5/-!
    6---
    7title: Bisimulation-invariant MSO on finite graphs
    8type: theorem
    9---
    10For a finite set of proposition letters, a property of finite reachable
    11transition systems is MSO-definable and bisimulation-invariant if and only
    12if it is definable in the modal mu-calculus. This is the main theorem
    13`theorem:bisim-invariant-finite` of Colcombet, Doumane and Kuperberg,
    14revised local manuscript of 13 November 2026. Invariance is required only between finite systems.
    15-/
    16
    17namespace Lax369799.FiniteBisimulationTheorem
    18open TransitionSystems
    19
    20axiom finite_bisimulation_invariant_mso {P : Type} [Finite P]
    21 (L : Set (TransitionSystem P)) :
    22 (MonadicSecondOrder.Definable L ∧ BisimulationInvariant L) ↔
    23 ModalMuCalculus.Definable L
    24
    25/-- A total executable translation, correct under the finite-invariance promise. -/
    26axiom effective_finite_bisimulation_invariant_mso {P : Type}
    27 [Fintype P] [Encodable P] [DecidableEq P]
    28 (φ : MonadicSecondOrder.Sentence P)
    29 (hφ : BisimulationInvariant {S | MonadicSecondOrder.Models S φ}) :
    30 ∀ S : TransitionSystem P, MonadicSecondOrder.Models S φ ↔
    31 ModalMuCalculus.Models S (EffectiveFiniteTranslation.compile φ)
    32
    33end Lax369799.FiniteBisimulationTheorem
    34
    Show ProofShow Proof

    Discussion

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

    Loading discussion…