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

Effective translation of bisimulation-invariant finite MSO

Lax369799.EffectiveFiniteTranslation · concepts/Lax369799/EffectiveFiniteTranslation.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

    The algorithm is total on all MSO sentences over an explicitly encoded finite vocabulary. It enumerates bounded modal transition tables and selects a compiled sentence by finite graph tests. Under the promised finite bisimulation invariance, the selected sentence agrees on every finite reachable transition system. No invariance decision is required. This formalizes the effectivity argument following Theorem 2.

    Concept map
    61 concepts; 1 descendant hidden
    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 presentationsFinite-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

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.FiniteTesting
    2import Lax369799.QuantitativeFiniteTheorem
    3import Mathlib.Data.List.ProdSigma
    4
    5/-!
    6---
    7title: Effective translation of bisimulation-invariant finite MSO
    8type: theorem
    9---
    10The algorithm is total on all MSO sentences over an explicitly encoded
    11finite vocabulary. It enumerates bounded modal transition tables and
    12selects a compiled sentence by finite graph tests. Under the promised
    13finite bisimulation invariance, the selected sentence agrees on every
    14finite reachable transition system. No invariance decision is required.
    15This formalizes the effectivity argument following Theorem 2.
    16-/
    17
    18namespace Lax369799.EffectiveFiniteTranslation
    19open ModalMuCalculus
    20
    21def candidates {P : Type} [Fintype P] [Encodable P] [DecidableEq P]
    22 (φ : MonadicSecondOrder.Sentence P) : List (Sentence P) :=
    23 let f := QuantitativeRecognition.msoBound φ
    24 (List.range (QuantitativeAutomata.unaryBound f+1)).flatMap (fun u =>
    25 (List.range (QuantitativeAutomata.nullaryBound f+1)).flatMap (fun z =>
    26 (List.range (QuantitativeAutomata.stateBound f+1)).flatMap (fun d =>
    27 (FiniteModalData.elements (FiniteModalData.Data P u z d (QuantitativeAutomata.priorityBound f))).map
    28 FiniteModalData.compile)))
    29
    30def conjunction {P : Type} (φ ψ : MonadicSecondOrder.Sentence P) : MonadicSecondOrder.Sentence P :=
    31 .neg (.disj (.neg φ) (.neg ψ))
    32
    33def difference {P : Type} (ψ χ : Sentence P) : MonadicSecondOrder.Sentence P :=
    34 .disj (conjunction (UnrestrictedLogic.sentence ψ) (.neg (UnrestrictedLogic.sentence χ)))
    35 (conjunction (.neg (UnrestrictedLogic.sentence ψ)) (UnrestrictedLogic.sentence χ))
    36
    37def separationBound {P : Type} (cs : List (Sentence P)) : ℕ :=
    38 ((cs.product cs).map (fun e => QuantitativeFiniteTheorem.modelBound (difference e.1 e.2))).foldr max 0
    39
    40def compile {P : Type} [Fintype P] [Encodable P] [DecidableEq P]
    41 (φ : MonadicSecondOrder.Sentence P) : Sentence P :=
    42 let cs := candidates φ
    43 (cs.find? (fun ψ => FiniteTesting.test (separationBound cs) φ ψ)).getD .bot
    44
    45open TransitionSystems
    46
    47axiom mu_translation_correct {P : Type} (ψ : Sentence P) (S : TransitionSystem P) :
    48 Models S ψ ↔ MonadicSecondOrder.Models S (UnrestrictedLogic.sentence ψ)
    49
    50-- Compiler correctness is the effective theorem in FiniteBisimulationTheorem.
    51-- Keep one Archive statement for this result.
    52
    53end Lax369799.EffectiveFiniteTranslation
    54
    Show Proof

    Discussion

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

    Loading discussion…