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

A computable finite-model bound under bisimulation invariance

Lax369799.QuantitativeFiniteTheorem · concepts/Lax369799/QuantitativeFiniteTheorem.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 quantitative construction of Theorem 2 gives a bounded modal certificate. Its small-model property provides a syntax-computed bound for every nonempty bisimulation-invariant MSO sentence on finite systems.

    Concept map
    50 concepts; 2 descendants 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 branchconditionsYield acceptance of finite presentationsFinite-state evaluation of terminating branchwordsContexts over finite presentationsContextual preorders on finite presentationsPositional determinacy of finite parity gamesFinite presentations without reachabilitypruningContextual quotient algebras of finitepresentationsFlattening and contextsFlattening, resolutions, and yield congruenceInfinite Ramsey theorem for pairsMSO-definable languages are algebraicallyrecognisableThe finite modal acceptance gameModal mu-calculusSmall finite models for modal parityacceptanceModal transitions obtained from typesupportsMonadic second-order logic on transitionsystemsMorphisms, unfoldings, and yieldsDeterminization of infinite-word automataRegular infinite products of linked pairsEliminating one priority by a fixed pointNested fixed-point equations for finite paritygamesWinning regions and controlled predecessorsQuantitative 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 acceptanceIdempotent 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.QuantitativeAutomata
    2import Lax369799.ModalSmallModels
    3import Lax369799.MonadicSecondOrder
    4
    5/-!
    6---
    7title: A computable finite-model bound under bisimulation invariance
    8type: theorem
    9---
    10The quantitative construction of Theorem 2 gives a bounded modal
    11certificate. Its small-model property provides a syntax-computed bound
    12for every nonempty bisimulation-invariant MSO sentence on finite systems.
    13-/
    14
    15namespace Lax369799.QuantitativeFiniteTheorem
    16
    17def modelBound {P : Type} (φ : MonadicSecondOrder.Sentence P) : ℕ :=
    18 QuantitativeAutomata.stateBound (QuantitativeRecognition.msoBound φ)
    19
    20open TransitionEncoding TransitionSystems UnfoldAutomata ParityWinningRegions
    21
    22axiom modal_certificate {P : Type} [Finite P] (φ : MonadicSecondOrder.Sentence P)
    23 (hφ : BisimulationInvariant {S | MonadicSecondOrder.Models S φ}) :
    24 ∃ M : UnfoldAutomaton (TransitionAlphabet P),
    25 M.unary ≤ QuantitativeAutomata.unaryBound (QuantitativeRecognition.msoBound φ) ∧
    26 M.nullary ≤ QuantitativeAutomata.nullaryBound (QuantitativeRecognition.msoBound φ) ∧
    27 M.condition.states ≤ modelBound φ ∧
    28 (∀ q,M.condition.priority q ≤ QuantitativeAutomata.priorityBound (QuantitativeRecognition.msoBound φ)) ∧
    29 ∀ S,MonadicSecondOrder.Models S φ ↔ Winning (ModalAcceptanceGame.game M S) true
    30 (ModalAcceptanceGame.position M.condition.initial S.initial)
    31
    32open TransitionEncoding TransitionSystems UnfoldAutomata ParityWinningRegions
    33
    34axiom nonempty_bound {P : Type} [Finite P] (φ : MonadicSecondOrder.Sentence P)
    35 (hφ : BisimulationInvariant {S | MonadicSecondOrder.Models S φ})
    36 (h : ∃ S,MonadicSecondOrder.Models S φ) :
    37 ∃ T : TransitionSystem P,T.size ≤ modelBound φ ∧ MonadicSecondOrder.Models T φ
    38
    39end Lax369799.QuantitativeFiniteTheorem
    Show ProofShow Proof

    Discussion

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

    Loading discussion…