Tree algebras and bisimulation-invariant MSO on finite graphs
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
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 -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- translation with correctness under the finite bisimulation-invariance promise. Explicit algebra, profile, word-automaton and finite-model bounds justify its exhaustive finite search.
Concepts
- thm✓
AcceptanceObservations - thm✓
AcceptanceTheorems - thm✓
AlgebraicBranchCondition - thm✓
AlgebraicDecomposition - thm✓
AlgebraicOmegaWords - thm✓
AlgebraicTransitions - thm✓
AlgebraToAutomaton - thm✓
AlgebraToMuCalculus - thm✓
AutomatonPropertyTheorem - thm✓
AutomatonRunGame - thm✓
BisimAutomatonTheorem - thm✓
BisimulationQuotient - thm✓
BoundedProfileRefinement - thm✓
BranchMonotonicity - thm✓
ChoicePreservingUnary - thm✓
CloneGameRun - thm✓
CloneRunRefinement - thm✓
CloneTransitions - thm✓
ClosedExtremal - thm✓
ClosedUnaryLift - thm✓
CombinedWordCondition - thm✓
ContextChoices - thm✓
ContextDecomposition - thm✓
ContextPorts - thm✓
ContextRelabelling - thm✓
ContextResolutionApproximation - thm✓
ContextSmallification - thm✓
DeterministicElements - thm✓
DeterministicNormalForms - thm✓
DeterministicPieces - thm✓
DeterministicSyntacticOrder - thm✓
DirectionProjections - thm✓
DirectionReindexing - thm✓
EffectiveFiniteTranslation - thm✓
EncodingTheorems - thm✓
EvaluationTheorems - thm✓
ExpandedCertificates - thm✓
ExpandedContinuity - thm✓
ExpandedSyntacticAlgebra - thm✓
ExpandedTransitions - thm✓
ExtendedContextDecomposition - thm✓
ExtendedContexts - thm✓
ExtendedSetAlgebras - thm✓
ExtremalPaths - thm✓
ExtremalSituations - thm✓
ExtremalSuccessors - thm✓
ExtremalUnaryTypes - thm✓
FiniteAlgebraMeets - thm✓
FiniteAutomatonProperty - thm✓
FiniteBisimulationTheorem - thm✓
FiniteBranchWords - thm✓
FiniteContextCongruence - thm✓
FiniteContextualOrder - thm✓
FiniteContinuityOrder - thm✓
FiniteCoverFamilies - thm✓
FiniteDecomposition - thm✓
FiniteDeterministicElements - thm✓
FiniteEvaluation - thm✓
FiniteExtremal - thm✓
FiniteFlatteningMorphisms - thm✓
FiniteLocalReplacement - thm✓
FiniteMarkUnion - thm✓
FiniteModalData - thm✓
FiniteModelChecking - thm✓
FiniteMorphisms - thm✓
FiniteMuEquations - thm✓
FiniteNormalForms - thm✓
FiniteOrderedAlgebra - thm✓
FiniteParityGames - thm✓
FinitePathEvaluation - thm✓
FinitePlant - thm✓
FiniteProfiles - thm✓
FiniteRecurrence - thm✓
FiniteRenaming - thm✓
FiniteResolutionApproximation - thm✓
FiniteResolutionNormalForms - thm✓
FiniteStructureTheorems - thm✓
FiniteSyntacticAlgebra - thm✓
FiniteTesting - thm✓
FiniteVertexReplacement - thm✓
FiniteYieldContinuity - thm✓
FiniteYieldMeets - thm✓
FixedPointElimination - thm✓
FixedPointRetraction - thm✓
FlatteningTheorems - thm✓
GeneratedAlgebra - thm✓
GraphChoices - thm✓
InfiniteRamsey - thm✓
InitialAlgebra - thm✓
InitialResolutionApproximation - thm✓
LinkedPairFactorizations - thm✓
LocalRecognition - thm✓
ModalAcceptanceGame - thm✓
ModalGameEquations - thm✓
ModalGameTranslation - thm✓
ModalSmallModels - thm✓
ModalTransitions - thm✓
MorphismTheorems - thm✓
MSORecognition - thm✓
MuCalculusTheorems - thm✓
MuSubstitution - thm✓
NonemptyPowersets - thm✓
ObservedSubstitution - thm✓
OmegaDeterminization - thm✓
OmegaProducts - thm✓
OptimalResolutions - thm✓
ParallelCompression - thm✓
ParallelReplacement - thm✓
ParityFixedPoints - thm✓
ParityGameEquations - thm✓
ParityGameSimulation - thm✓
ParityWinningRegions - thm✓
PathAlgebra - thm✓
PeriodicPaths - thm✓
PolynomialContexts - thm✓
PolynomialQuotient - thm✓
PolynomialUnfolding - thm✓
PortReindexing - thm✓
PresentationObservations - thm✓
PriorityCompilation - thm✓
ProfileSubstitution - thm✓
QuantitativeAutomata - thm✓
QuantitativeDeterminization - thm✓
QuantitativeFiniteTheorem - thm✓
QuantitativeProfiles - thm✓
QuantitativeRecognition - thm✓
QuantitativeWordConditions - thm✓
RankedBisimulation - thm✓
RankedLifting - thm✓
RecognitionClosure - thm✓
RecognitionProjection - thm✓
RegularBranchWords - thm✓
Regularization - thm✓
Renaming - thm✓
ResolutionCompression - thm✓
ResolutionFamilies - thm✓
ResolutionLifting - thm✓
RootExpansion - thm✓
RootlessFlattening - thm✓
RootObservations - thm✓
RootProfileSubstitution - thm✓
RootResolutionApproximation - thm✓
RunAcceptance - thm✓
RunBranchObservations - thm✓
RunPresentations - thm✓
RunWordCondition - thm✓
SelectedChoicePreservation - thm✓
SelectedParallel - thm✓
SemigroupFactorization - thm✓
SetAlgebraTheorems - thm✓
SetLogic - thm✓
SetLogicRecognition - thm✓
SetLogicTranslation - thm✓
SetSystemAlgebras - thm✓
SmallProfileRefinement - thm✓
SplitExtremal - thm✓
SubstitutionProfiles - thm✓
SupportCompaction - thm✓
SupportedAlgebras - thm✓
SupportedCompletion - thm✓
SupportedContextSmallification - thm✓
SupportedMorphisms - thm✓
SupportedProfiles - thm✓
SupportedRecognition - thm✓
SupportedResolutions - thm✓
SupportedSystems - thm✓
SupportedYieldComparison - thm✓
SupportedYieldContinuity - thm✓
SupportedYields - thm✓
SupportEvaluation - thm✓
SupportIsomorphism - thm✓
SupportPorts - thm✓
SyntacticAlgebraTheorems - thm✓
SystemEvaluation - thm✓
SystemIsomorphisms - thm✓
SystemMonad - thm✓
SystemSubstitution - thm✓
UnaryChains - thm✓
UnaryComposition - thm✓
UnaryFactorization - thm✓
UnaryGraphEvaluation - thm✓
UnarySystemEvaluation - thm✓
UnarySystems - thm✓
UnaryTestContexts - thm✓
UnboundedSubstitution - thm✓
UnfoldBranches - thm✓
UnrestrictedLogic - thm✓
VariableCompression - thm✓
VertexContexts - thm✓
WordFactorization - thm✓
WordParity - thm✓
YieldContinuity - thm✓
YieldSubstitution - def✓
ExtremalContexts - def✓
FiniteAcceptance - def✓
FiniteContexts - def✓
FinitePresentations - def✓
PresentationCovers
- def
Algebras - def
AutomatonProperty - def
BisimAutomata - def
Flattening - def
ModalMuCalculus - def
MonadicSecondOrder - def
Morphisms - def
RankedSystems - def
Resolutions - def
SetAlgebras - def
SyntacticOrder - def
TransitionEncoding - def
TransitionSystems - def
UnfoldAutomata - def
UnrestrictedTransitionSystems
Concept map
Proofs
Proof networkview on GitHub
Proof list
-
⊢
Lax369799Proofs.AcceptanceObservations.accepting_iff_values -
⊢
Lax369799Proofs.AlgebraicDecomposition.algebraic_decomposition -
⊢
Lax369799Proofs.AlgebraicOmegaWords.recurrent_factorization -
⊢
Lax369799Proofs.BisimAutomatonTheorem.bisim_automaton_to_mu -
⊢
Lax369799Proofs.BoundedProfileRefinement.finite_carrier_recognizable -
⊢
Lax369799Proofs.ChoicePreservingUnary.word_preserves_choices -
⊢
Lax369799Proofs.ContextCongruence.unfold_context_congruence -
⊢
Lax369799Proofs.ContextDecomposition.decomposition_equivalence -
⊢
Lax369799Proofs.ContextResolutionApproximation.direct_approximation -
⊢
Lax369799Proofs.ContextResolutionApproximation.initial_yields -
⊢
Lax369799Proofs.ContinuationCompression.context_smallification -
⊢
Lax369799Proofs.ContinuationCompression.mapped_context_smallification -
⊢
Lax369799Proofs.DeterministicSyntacticOrder.accepting_class -
⊢
Lax369799Proofs.DeterministicSyntacticOrder.closed_membership -
⊢
Lax369799Proofs.DirectionProjections.extremal_decomposition -
⊢
Lax369799Proofs.DirectionProjections.parallel_projection_bound -
⊢
Lax369799Proofs.EffectiveFiniteTranslation.mu_translation_correct -
⊢
Lax369799Proofs.ExpandedCertificates.acceptance_iff_certificate -
⊢
Lax369799Proofs.ExpandedCertificates.language_iff_certificate -
⊢
Lax369799Proofs.ExpandedContinuity.representative_independence -
⊢
Lax369799Proofs.ExpandedSyntacticAlgebra.automaton_property -
⊢
Lax369799Proofs.ExpandedSyntacticAlgebra.expanded_normal_form -
⊢
Lax369799Proofs.ExpandedSyntacticAlgebra.expanded_yield_order -
⊢
Lax369799Proofs.ExpandedSyntacticAlgebra.representatives_exist -
⊢
Lax369799Proofs.ExpandedSyntacticAlgebra.syntactic_algebra_exists -
⊢
Lax369799Proofs.ExpandedSyntacticAlgebra.syntactic_automaton_property -
⊢
Lax369799Proofs.ExtendedContextDecomposition.context_decomposition -
⊢
Lax369799Proofs.FiniteAcceptance.syntactic_substitution_algebra -
⊢
Lax369799Proofs.FiniteAutomatonProperty.recognizable_automaton_property -
⊢
Lax369799Proofs.FiniteContextCongruence.context_iff_substitution -
⊢
Lax369799Proofs.FiniteContextualOrder.contextual_acceptance -
⊢
Lax369799Proofs.FiniteContextualOrder.contextual_congruence -
⊢
Lax369799Proofs.FiniteContinuityOrder.accepting_approximation -
⊢
Lax369799Proofs.FiniteDecomposition.decomposition_evaluation -
⊢
Lax369799Proofs.FiniteDeltaComparison.delta_boundary_comparison -
⊢
Lax369799Proofs.FiniteDeltaComparison.delta_piece_comparison -
⊢
Lax369799Proofs.FiniteDeterministicElements.substitution_closed -
⊢
Lax369799Proofs.FiniteResolutionApproximation.direct_approximation -
⊢
Lax369799Proofs.FiniteResolutionApproximation.finite_support -
⊢
Lax369799Proofs.FiniteResolutionNormalForms.bounded_normal_form -
⊢
Lax369799Proofs.FiniteResolutionNormalForms.contextual_normal_form -
⊢
Lax369799Proofs.FiniteSyntacticAlgebra.contextual_recognition -
⊢
Lax369799Proofs.FiniteVertexReplacement.simultaneous_replacement -
⊢
Lax369799Proofs.InitialResolutionApproximation.finite_support -
⊢
Lax369799Proofs.LinkedPairFactorizations.recurrent_factorization -
⊢
Lax369799Proofs.MainTheorems.effective_finite_bisimulation_invariant_mso -
⊢
Lax369799Proofs.MainTheorems.finite_bisimulation_invariant_mso -
⊢
Lax369799Proofs.MorphismTheorems.system_morphism_locally_surjective -
⊢
Lax369799Proofs.OptimalResolutions.optimal_flatten_resolution -
⊢
Lax369799Proofs.PolynomialUnfolding.quotient_unfold_invariant -
⊢
Lax369799Proofs.PresentationObservations.values_remove_roots -
⊢
Lax369799Proofs.QuantitativeDeterminization.determinization_bound -
⊢
Lax369799Proofs.QuantitativeFiniteTheorem.modal_certificate -
⊢
Lax369799Proofs.QuantitativeWordConditions.exists_condition -
⊢
Lax369799Proofs.RankedBisimulation.bisimilarity_equivalence -
⊢
Lax369799Proofs.ReachableFiniteness.syntactic_rankwise_finite -
⊢
Lax369799Proofs.ResolutionCompression.compress_flatten_resolution -
⊢
Lax369799Proofs.ResolutionFactorization.resolution_to_flatten_resolution -
⊢
Lax369799Proofs.RootProfileSubstitution.transfer_initial_value -
⊢
Lax369799Proofs.RootProfileSubstitution.transfer_root_value -
⊢
Lax369799Proofs.RunBranchObservations.regularPath_accepting -
⊢
Lax369799Proofs.SelectedChoicePreservation.selected_preserves_choices -
⊢
Lax369799Proofs.SupportedContextSmallification.smallification -
⊢
Lax369799Proofs.SupportedRecognition.syntactic_rankwise_finite -
⊢
Lax369799Proofs.SupportedYieldComparison.flatten_congruence -
⊢
Lax369799Proofs.SupportedYieldContinuity.initial_continuity -
⊢
Lax369799Proofs.SupportIsomorphism.profile_injective_rename -
⊢
Lax369799Proofs.UnboundedSubstitution.transfer_initial_value -
⊢
Lax369799Proofs.UnrestrictedLogic.mu_bisimulation_invariant -
⊢
Lax369799Proofs.UnrestrictedLogic.mu_definable_implies_mso_invariant
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
- 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
- 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.
- 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.
0 comments