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

Modal equations on input vertices

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

    Project winning regions to word-state/input positions. Marking positions are determined by universal successor conditions and terminals by their outcomes. The projection and its monotone section preserve the least and greatest solutions of each stopped priority game. The resulting nested equations have one coordinate per word state and are evaluated on the original input graph.

    Concept map
    17 concepts; 6 descendants hidden
    100%
    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.ModalAcceptanceGame
    2import Lax369799.FixedPointRetraction
    3
    4/-!
    5---
    6title: Modal equations on input vertices
    7type: theorem
    8---
    9Project winning regions to word-state/input positions. Marking positions
    10are determined by universal successor conditions and terminals by their
    11outcomes. The projection and its monotone section preserve the least and
    12greatest solutions of each stopped priority game. The resulting nested
    13equations have one coordinate per word state and are evaluated on the
    14original input graph.
    15-/
    16namespace Lax369799.ModalGameEquations
    17open TransitionSystems TransitionEncoding UnfoldAutomata ModalTransitions ModalAcceptanceGame
    18open FiniteParityGames ParityWinningRegions ParityFixedPoints
    19attribute [local instance] Classical.propDecidable
    20
    21def project {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) :
    22 Set (Vertex M S) →o Marking M S where
    23 toFun := fun X q => {v | position q v ∈ X}
    24 monotone' := fun _ _ h _ _ hv => h hv
    25
    26def lift {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P) :
    27 Marking M S →o Set (Vertex M S) where
    28 toFun := fun X t => match t with
    29 | .inl (q, v) => v ∈ X q
    30 | .inr (.inl (v, ρ)) => ∀ q w, S.edge v w → w ∈ ρ q → w ∈ X q
    31 | .inr (.inr b) => b = true
    32 monotone' := by
    33 intro X Y h t ht
    34 rcases t with ⟨q, v⟩ | (⟨v, ρ⟩ | b)
    35 · exact h q ht
    36 · exact fun q w hw hρ => h q (ht q w hw hρ)
    37 · exact ht
    38
    39def statePriority {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    40 (q : Fin M.condition.states) : ℕ := ceiling M.condition - M.condition.priority q
    41
    42def boundary {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) (S : TransitionSystem P)
    43 (B : Fin M.condition.states → S.Vertex → Prop) : Set (Vertex M S) :=
    44 {t | match t with
    45 | .inl (q, v) => B q v
    46 | _ => False}
    47
    48noncomputable def stopped {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    49 (S : TransitionSystem P) (n : ℕ) (ρ : ℕ → Marking M S) : Game (Vertex M S) :=
    50 stop (game M S) (boundary M S (fun q _ => n ≤ statePriority M q))
    51 (boundary M S (fun q v => OneStep M q S v (ρ (statePriority M q))))
    52
    53noncomputable def solve {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    54 (S : TransitionSystem P) : ℕ → (ℕ → Marking M S) → Marking M S
    55 | 0, ρ => fun q => {v | OneStep M q S v (ρ (statePriority M q))}
    56 | n + 1, ρ => if Even n then
    57 sSup {X : Marking M S | X ≤ solve M S n (Function.update ρ n X)}
    58 else sInf {X : Marking M S | solve M S n (Function.update ρ n X) ≤ X}
    59
    60axiom solve_stopped {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    61 (S : TransitionSystem P) (n : ℕ) (ρ : ℕ → Marking M S) :
    62 project M S (Winning (stopped M S n ρ) true) = solve M S n ρ
    63
    64axiom winning {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    65 (S : TransitionSystem P) (n : ℕ) (hn : ∀ q, statePriority M q < n)
    66 (ρ : ℕ → Marking M S) :
    67 project M S (Winning (game M S) true) = solve M S n ρ
    68
    69end Lax369799.ModalGameEquations
    70
    Show ProofShow Proof

    Discussion

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

    Loading discussion…