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

Tree algebras and bisimulation-invariant MSO on finite graphs

lax-369799·formalized by Denis Kuperberg · Codex 6 · Codex 6.1·created ·GitHub @3d81adf·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

    This submission formalizes Theorem 2 of the revised manuscript of 13 November 2026: over a finite proposition alphabet, the bisimulation-invariant fragment of monadic second-order logic on finite reachable transition systems is exactly the modal μ\mu-calculus. Both implications and their supporting proof network are proved. The algebraic construction uses finite ranked systems, yield-syntactic set-algebras, and unfold-automata.

    The submission also provides a total executable MSO-to-μ\mu translation with correctness under the finite bisimulation-invariance promise. Explicit algebra, profile, word-automaton and finite-model bounds justify its exhaustive finite search.

    Concepts

    Concept map
    213 concepts
    100%
    Acceptance through resolution valuesAcceptance and the syntactic preorderRankwise-finite recognition impliesautomaton recognitionBisimulation-invariant algebraic recognitionimplies mu-calculus definabilityA common condition for finite and infinitealgebraic branch wordsAlgebraic decomposition with boundary dataThe algebraic condition on infinite branchwordsAlgebraic transition tables forunfold-automataAlgebras and recognitionDeterministic elements and the earlierreplacement propertyThe automaton property of syntacticset-algebrasAccepting runs and modal game playsClone-automataClone-automaton normal form and modaltranslationQuotients of graphs by vertex bisimilarityBounded profiles refine finite contextualequivalenceMonotonicity of algebraic branch conditionsUnary types preserving explicit choicesRealizing winning clone-automaton strategiesRefining runs of the clone tableCompressed transitions and their cloneclosureThe closed extremal witnessClosed values as unary piecesCombining finite and infinite branchconditionsSplitting outgoing choices in cyclic unarycontextsContext decomposition with hole boundarydataRestricting and resizing the directions of acontextRelabelling and deterministic contextsubstitutionFinite resolution approximation in a contextSmallification preserving identitycontinuationsUnary normal form of deterministic elementsDeterministic normal forms with identitycontinuationsUnary continuations of deterministiccontextsContextual equivalence of deterministicsystemsDirection projections of extremal elementsReindexing the outgoing directions at eachvertexEffective translation of bisimulation-invariantfinite MSOCorrectness of ranked transition encodingsEvaluation of sums and contextsAcceptance certificates retaining expandedresolutionsContinuity through expanded representativesSyntactic algebras with expanded continuityTransition tables for the algebra withexpanded continuityEvaluation of closed contexts throughextended unary piecesFormal unary pieces and extremal acceptedsituationsExtended set-algebras and extremal acceptedsituationsPlanted normal contexts and deterministicwitnessesThe path criterion and the automatonpropertyExtremal accepted situations in the syntacticalgebraSuccessor confinement in the extremalwitnessUnary types selected by extremal refinementYield acceptance of finite presentationsFinite meets in a set-algebraAutomaton property of the unprunedsyntactic algebraBisimulation-invariant MSO on finite graphsFinite-state evaluation of terminating branchwordsContext tests and simultaneous substitutionContexts over finite presentationsContextual preorders on finite presentationsFinite yield approximation of contextualacceptance and orderAcceptance from finite families of coveringcomponentsContext decomposition without pruningSubstitution closure of deterministic valuesContext evaluation in finite-presentationalgebrasExtremal unary data for finite presentationsUnpruned substitution preserves morphismsand unfold-equivalenceFinite iteration of context-preserving localchoicesUnions of initial and root marksExecutable modal compilation from finiteBoolean tablesExecutable finite model checking for bothlogicsMorphisms of unpruned finite presentationsScalar formulas for finite fixed-point equationsystemsUnary normal forms without pruningOrdered syntactic algebras of finitepresentationsPositional determinacy of finite parity gamesEvaluation of finite path graphsPlanting finite presentationsFinite presentations without reachabilitypruningSmall profiles of finite presentationsEventual membership in finite familiesVariable renaming and inverse renamingwithout pruningFinite approximation of a flatteningresolutionNormal forms retaining split-variableresolutionsComposition and pullbacks withoutreachability pruningContextual quotient algebras of finitepresentationsExecutable bounded comparison of MSO andmodal formulasSimultaneous deterministic replacements infinite presentationsYield continuity for finite-presentationcontextsFinite sums are contextual meetsElimination of simultaneous fixed pointsFixed points through a monotone retractionFlattening and contextsFlattening, resolutions, and yield congruenceThe subalgebra generated by a recognizingalphabetFunctional restrictions of selected unarygraphsInfinite Ramsey theorem for pairsThe initial-label algebraFinite support for initial observationsRecurrent cuts in a linked-pair factorizationRecognition of local vertex and edge testsMSO-definable languages are algebraicallyrecognisableThe finite modal acceptance gameModal equations on input verticesTranslating the modal acceptance game to asentenceModal mu-calculusSmall finite models for modal parityacceptanceModal transitions obtained from typesupportsMonadic second-order logic on transitionsystemsMorphism and yield theoremsMorphisms, unfoldings, and yieldsMSO translation and bisimulation invarianceof the mu-calculusSubstitution in modal fixed-point formulasNonempty powerset algebrasBounded profiles in root-free substitutionpatternsDeterminization of infinite-word automataRegular infinite products of linked pairsBounded optimal flatten-resolutionsEvaluation after compressing parallel tuplesParallel replacements in accepting contextsEliminating one priority by a fixed pointNested fixed-point equations for finite paritygamesTransfer of winning through alternatinggame simulationWinning regions and controlled predecessorsFinite path-summary algebrasUltimately periodic witnesses in finite paritygraphsPolynomial contexts of a system algebraQuotients by polynomial acceptance testsUnfolding through polynomial contextsSubstitution after reindexing directionsLocally surjective maps of finitepresentationsResolution values of finite presentationsExecutable compilation of modal priorityequationsTransfer of resolutions through boundedprofilesQuantitative 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 branchautomatonBisimulation under ranked decodingRanking a functional bisimulationRanked sets, set-systems, and systemsBoolean closure and inverse relabelling ofrecognizable languagesExistential projection of recognizablelanguagesTesting infinite runs on finite branch graphsRegular-tree recognition fromunfold-invariant recognitionRenaming variables in systems andresolutionsCompression of the variables offlatten-resolutionsFinite families of split-variable resolutionsLifting unfoldings through variable renamingResolutions and bounded profilesRoot entries in substituted presentationsInitial and root observations of set-systemsInitial and root observations underbounded-profile substitutionFinite support for root observationsReachable substitution with root-freecomponentsWord acceptance and evaluation of algebraicrunsFinite branch observations of a runUnary presentations associated with legalrunsThe terminating-word condition for algebraicrunsChoice preservation of extremally selectedunary typesParallel transitions with selected unarycomponentsStable factorization with recurrent verticesOrder and yield properties of set-algebrasThe earlier continuity-bearing set-algebrainterfacePure second-order syntaxRecognition induction for pure second-orderlogicTranslation to pure second-order logicSet-algebras with retained verticesSmall profiles and the yield-syntacticcongruenceExtremal witnesses with separate rootedcomponentsSubstitution congruence for compactedevaluationsFactoring out unused output variablesFinite observations after output compactionIsomorphisms and compacted output valuesSubstitution after restricting inner outputportsAlgebras on fully supported systemsExtending supported algebras and preservingrecognitionSmallification in supported contextsSelection and common unfoldings of fullysupported systemsProfiles of fully supported resolutionsLanguage invariance, closure, and syntacticfiniteness for supported algebrasFlatten-resolutions with supported systemsand explicit output mapsSystems with all output variables reachableSupported yields, contextual order, andsubstitution congruenceFinite yield approximation with supportedwitnessesYields with explicit variable maps and fullsupportSyntactic set-algebras and rankwise finitenessYield-syntactic order and quotientEvaluation and variable renaming inregular-tree algebrasIsomorphisms of deterministic substitutionsUnit and associativity for deterministicsubstitutionUnfolding congruence for deterministicsubstitutionRanked encodings of transition systemsFinite transition systems and bisimulationEvaluation of unary chains in every sortThe unary semigroup and its actionStable factorization of algebraic branchwordsEvaluation of finite unary branch graphsAlgebraic evaluation and the words of aregular branchVariable exits of unary systemsNormal data for a unary type with a closedcontinuationFull-profile transfer in every output rankUnfold-automata and regular-tree acceptancePeriodic branch test for unfold-automataLogic on arbitrary transition systemsArbitrary transition systems andbisimulationsCompression of variable maps by finiteobservationsContexts obtained by marking a vertexIdempotent factorization of infinite wordsRecurring priorities in finite-state runsContinuity of yields in a contextSubstitution and yield inclusion
    Proven claimDefinitionThis submissionA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Proofs

    Proof networkview on GitHub

    100%
    AcceptanceObservationsAcceptanceTheoremsAlgebraToAutomatonAlgebraToMuCalculusAlgebraicBranchConditionAlgebraicDecompositionAlgebraicOmegaWordsAlgebraicTransitionsAutomatonPropertyTheoremAutomatonRunGameBisimAutomatonTheoremBisimulationQuotientBoundedProfileRefinementBranchMonotonicityChoicePreservingUnaryCloneGameRunCloneRunRefinementCloneTransitionsClosedExtremalClosedUnaryLiftCombinedWordConditionContextChoicesContextDecompositionContextPortsContextRelabellingContextResolutionApproximationContextSmallificationDeterministicElementsDeterministicNormalFormsDeterministicPiecesDeterministicSyntacticOrderDirectionProjectionsDirectionReindexingEffectiveFiniteTranslationEncodingTheoremsEvaluationTheoremsExpandedCertificatesExpandedContinuityExpandedSyntacticAlgebraExpandedTransitionsExtendedContextDecompositionExtendedContextsExtendedSetAlgebrasExtremalContextsExtremalPathsExtremalSituationsExtremalSuccessorsExtremalUnaryTypesFiniteAcceptanceFiniteAlgebraMeetsFiniteAutomatonPropertyFiniteBisimulationTheoremFiniteBranchWordsFiniteContextCongruenceFiniteContextsFiniteContextualOrderFiniteContinuityOrderFiniteCoverFamiliesFiniteDecompositionFiniteDeterministicElementsFiniteEvaluationFiniteExtremalFiniteFlatteningMorphismsFiniteLocalReplacementFiniteMarkUnionFiniteModalDataFiniteModelCheckingFiniteMorphismsFiniteMuEquationsFiniteNormalFormsFiniteOrderedAlgebraFiniteParityGamesFinitePathEvaluationFinitePlantFinitePresentationsFiniteProfilesFiniteRecurrenceFiniteRenamingFiniteResolutionApproximationFiniteResolutionNormalFormsFiniteStructureTheoremsFiniteSyntacticAlgebraFiniteTestingFiniteVertexReplacementFiniteYieldContinuityFiniteYieldMeetsFixedPointEliminationFixedPointRetractionFlatteningTheoremsGeneratedAlgebraGraphChoicesInfiniteRamseyInitialAlgebraInitialResolutionApproximationLinkedPairFactorizationsLocalRecognitionMSORecognitionModalAcceptanceGameModalGameEquationsModalGameTranslationModalSmallModelsModalTransitionsMorphismTheoremsMuCalculusTheoremsMuSubstitutionNonemptyPowersetsObservedSubstitutionOmegaDeterminizationOmegaProductsOptimalResolutionsParallelCompressionParallelReplacementParityFixedPointsParityGameEquationsParityGameSimulationParityWinningRegionsPathAlgebraPeriodicPathsPolynomialContextsPolynomialQuotientPolynomialUnfoldingPortReindexingPresentationCoversPresentationObservationsPriorityCompilationProfileSubstitutionQuantitativeAutomataQuantitativeDeterminizationQuantitativeFiniteTheoremQuantitativeProfilesQuantitativeRecognitionQuantitativeWordConditionsRankedBisimulationRankedLiftingRecognitionClosureRecognitionProjectionRegularBranchWordsRegularizationRenamingResolutionCompressionResolutionFamiliesResolutionLiftingRootExpansionRootObservationsRootProfileSubstitutionRootResolutionApproximationRootlessFlatteningRunAcceptanceRunBranchObservationsRunPresentationsRunWordConditionSelectedChoicePreservationSelectedParallelSemigroupFactorizationSetAlgebraTheoremsSetLogicSetLogicRecognitionSetLogicTranslationSetSystemAlgebrasSmallProfileRefinementSplitExtremalSubstitutionProfilesSupportCompactionSupportEvaluationSupportIsomorphismSupportPortsSupportedAlgebrasSupportedCompletionSupportedContextSmallificationSupportedMorphismsSupportedProfilesSupportedRecognitionSupportedResolutionsSupportedSystemsSupportedYieldComparisonSupportedYieldContinuitySupportedYieldsSyntacticAlgebraTheoremsSystemEvaluationSystemIsomorphismsSystemMonadSystemSubstitutionUnaryChainsUnaryCompositionUnaryFactorizationUnaryGraphEvaluationUnarySystemEvaluationUnarySystemsUnaryTestContextsUnboundedSubstitutionUnfoldBranchesUnrestrictedLogicVariableCompressionVertexContextsWordFactorizationWordParityYieldContinuityYieldSubstitution
    premise files concept fileProven claimClaim from this submissionAll proofs of one concept — hover for individual statements and proofs
    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

    No other submission in the archive builds on this one, and this one builds on none.

    Cite this

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

    @misc{lax-369799,
      author = {Denis Kuperberg and Codex 6 and Codex 6.1},
      title = {Tree algebras and bisimulation-invariant MSO on finite graphs},
      year = {2026},
      howpublished = {Lax Archive, lax-369799},
      url = {https://laxarchive.org/lax-369799/},
      note = {draft},
    }

    References

    1. Mikołaj Bojańczyk, Antonio Casares, Sven Manthe and Paweł Parys. Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches. 2026. Lean ancillary proofs of word-automaton determinization and finite parity-game determinacy. arXiv:2611.10136 · arxiv.org/abs/2611.10136v1
    2. Thomas Colcombet, Amina Doumane and Denis Kuperberg. Tree algebras and bisimulation-invariant MSO on finite graphs. 2026. Revised manuscript dated 13 November 2026; local source: main_tree_algebra_longversion.pdf.
    3. Thomas Colcombet, Amina Doumane and Denis Kuperberg. Tree algebras and bisimulation-invariant MSO on finite graphs. 2026. arXiv:2407.12677 · arxiv.org/abs/2407.12677v6

    Discussion

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

    Loading discussion…