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

Translating the modal acceptance game to a sentence

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

    Translate the projected priority equations into formulas by binding a finite vector of variables at each priority. Capture-avoiding substitution supplies the boundary parameters; finite equation elimination implements each vector binder in the scalar mu-calculus. The resulting sentence is independent of the input graph and defines the game's winning region.

    Concept map
    20 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

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

    Lean source view on GitHub

    1import Lax369799.ModalGameEquations
    2import Lax369799.FiniteMuEquations
    3
    4/-!
    5---
    6title: Translating the modal acceptance game to a sentence
    7type: theorem
    8---
    9Translate the projected priority equations into formulas by binding a
    10finite vector of variables at each priority. Capture-avoiding substitution
    11supplies the boundary parameters; finite equation elimination implements
    12each vector binder in the scalar mu-calculus. The resulting sentence is
    13independent of the input graph and defines the game's winning region.
    14-/
    15namespace Lax369799.ModalGameTranslation
    16open TransitionSystems TransitionEncoding UnfoldAutomata ModalTransitions ModalAcceptanceGame
    17open ModalMuCalculus MuSubstitution
    18open ModalGameEquations (statePriority)
    19attribute [local instance] Classical.propDecidable
    20
    21noncomputable def bindBoundary {P : Type}
    22 (M : UnfoldAutomaton (TransitionAlphabet P)) {m : ℕ}
    23 (n : ℕ) (θ : ℕ → Fin M.condition.states → Formula P m) :
    24 ℕ → Fin M.condition.states → Formula P (M.condition.states + m) :=
    25 fun p q => if p = n then .variable (Fin.castAdd m q)
    26 else rename (Fin.natAdd M.condition.states) (θ p q)
    27
    28noncomputable def formulas {P : Type} [Fintype P]
    29 (M : UnfoldAutomaton (TransitionAlphabet P)) :
    30 (n : ℕ) → {m : ℕ} → (ℕ → Fin M.condition.states → Formula P m) →
    31 Fin M.condition.states → Formula P m
    32 | 0, _, θ => fun q => substitute (θ (statePriority M q)) (transitionFormula M q)
    33 | n + 1, _, θ => Lax369799.FiniteMuEquations.solve
    34 (if Even n then .greatest else .least) (formulas M n (bindBoundary M n θ))
    35
    36noncomputable def sentence {P : Type} [Fintype P]
    37 (M : UnfoldAutomaton (TransitionAlphabet P)) (q : Fin M.condition.states) : Sentence P :=
    38 formulas M (ceiling M.condition + 1) (fun _ _ => .bot) q
    39
    40axiom formulas_correct {P : Type} [Fintype P]
    41 (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P)
    42 (n : ℕ) {m : ℕ} (θ : ℕ → Fin M.condition.states → Formula P m)
    43 (ρ : Fin m → Set S.Vertex) :
    44 (fun q => (formulas M n θ q).eval S ρ) =
    45 Lax369799.ModalGameEquations.solve M S n (fun p q => (θ p q).eval S ρ)
    46
    47axiom sentence_correct {P : Type} [Fintype P]
    48 (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P)
    49 (q : Fin M.condition.states) (v : S.Vertex) :
    50 v ∈ (sentence M q).eval S Fin.elim0 ↔
    51 Lax369799.ParityWinningRegions.Winning (game M S) true (position q v)
    52
    53axiom game_to_mu {P : Type} [Finite P]
    54 (M : UnfoldAutomaton (TransitionAlphabet P)) :
    55 ∃ φ : Sentence P, ∀ S,
    56 Lax369799.ParityWinningRegions.Winning (game M S) true
    57 (position M.condition.initial S.initial) ↔ Models S φ
    58
    59end Lax369799.ModalGameTranslation
    60
    Show ProofShow ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

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

    Loading discussion…