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

Executable compilation of modal priority equations

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

    An explicit finite family of positive modal transition formulas and a priority map compile to a scalar sentence by structural recursion. The compiler uses only finite syntax operations. A semantic certificate for the transition formulas identifies its output with the modal acceptance game. This is the effective final stage, with the finite transition table provided as input.

    Concept map
    20 concepts; 4 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.FiniteMuEquations
    2import Lax369799.ModalGameEquations
    3
    4/-!
    5---
    6title: Executable compilation of modal priority equations
    7type: theorem
    8---
    9An explicit finite family of positive modal transition formulas and a
    10priority map compile to a scalar sentence by structural recursion. The
    11compiler uses only finite syntax operations. A semantic certificate for
    12the transition formulas identifies its output with the modal acceptance
    13game. This is the effective final stage, with the finite transition table
    14provided as input.
    15-/
    16
    17namespace Lax369799.PriorityCompilation
    18open ModalMuCalculus MuSubstitution TransitionEncoding TransitionSystems UnfoldAutomata
    19open ModalAcceptanceGame
    20
    21def boundary {P : Type} {d m : ℕ} (n : ℕ)
    22 (θ : ℕ → Fin d → Formula P m) : ℕ → Fin d → Formula P (d+m) :=
    23 fun p q => if p = n then .variable (Fin.castAdd m q)
    24 else rename (Fin.natAdd d) (θ p q)
    25
    26def compile {P : Type} {d : ℕ} (priority : Fin d → ℕ)
    27 (transition : Fin d → Formula P d) :
    28 (n : ℕ) → {m : ℕ} → (ℕ → Fin d → Formula P m) → Fin d → Formula P m
    29 | 0, _, θ => fun q => substitute (θ (priority q)) (transition q)
    30 | n+1, _, θ => FiniteMuEquations.solve
    31 (if n % 2 = 0 then .greatest else .least) (compile priority transition n (boundary n θ))
    32
    33def sentence {P : Type} {d : ℕ} (priority : Fin d → ℕ)
    34 (transition : Fin d → Formula P d) (depth : ℕ) (initial : Fin d) : Sentence P :=
    35 compile priority transition depth (fun _ _ => .bot) initial
    36
    37axiom compile_correct {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    38 (δ : Fin M.condition.states → Formula P M.condition.states)
    39 (S : TransitionSystem P)
    40 (hδ : ∀ q ρ v, v ∈ (δ q).eval S ρ ↔ ModalTransitions.OneStep M q S v ρ)
    41 (n : ℕ) {m : ℕ} (θ : ℕ → Fin M.condition.states → Formula P m)
    42 (ρ : Fin m → Set S.Vertex) :
    43 (fun q => (compile (ModalGameEquations.statePriority M) δ n θ q).eval S ρ) =
    44 ModalGameEquations.solve M S n (fun p q => (θ p q).eval S ρ)
    45
    46axiom sentence_correct {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    47 (δ : Fin M.condition.states → Formula P M.condition.states)
    48 (S : TransitionSystem P)
    49 (hδ : ∀ q ρ v, v ∈ (δ q).eval S ρ ↔ ModalTransitions.OneStep M q S v ρ) :
    50 Models S (sentence (ModalGameEquations.statePriority M) δ (ceiling M.condition+1)
    51 M.condition.initial) ↔
    52 ParityWinningRegions.Winning (game M S) true (position M.condition.initial S.initial)
    53
    54end Lax369799.PriorityCompilation
    55
    Show ProofShow Proof

    Discussion

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

    Loading discussion…