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

Modal transitions obtained from type supports

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

    Section 6.4 replaces each transition tuple by its support. Each type in the support must occur at some successor, and every successor must have some type in the support. Nullary transitions test the final word state and the absence of successors. These conditions are expressible by finite positive modal formulas.

    Concept map
    10 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

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

    Lean source view on GitHub

    1import Lax369799.BisimAutomata
    2import Lax369799.ModalMuCalculus
    3import Mathlib.Data.Fintype.Powerset
    4
    5/-!
    6---
    7title: Modal transitions obtained from type supports
    8type: theorem
    9---
    10Section 6.4 replaces each transition tuple by its support. Each type in
    11the support must occur at some successor, and every successor must have
    12some type in the support. Nullary transitions test the final word state
    13and the absence of successors. These conditions are expressible by
    14finite positive modal formulas.
    15-/
    16namespace Lax369799.ModalTransitions
    17open TransitionEncoding TransitionSystems UnfoldAutomata ModalMuCalculus
    18
    19def Realized {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    20 (ν : Set P) (B : Set (Fin M.unary)) : Prop :=
    21 ∃ (n : ℕ) (b : Fin (n + 1) → Fin M.unary), b ∈ M.transition n ν ∧ Set.range b = B
    22
    23def OneStep {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    24 (q : Fin M.condition.states) (S : TransitionSystem P) (v : S.Vertex)
    25 (ρ : Fin M.condition.states → Set S.Vertex) : Prop :=
    26 ((∃ a ∈ M.leafTransition (S.valuation v), M.condition.step q (.inr a) ∈ M.condition.final) ∧
    27 ∀ w, ¬ S.edge v w) ∨
    28 ∃ B, Realized M (S.valuation v) B ∧
    29 (∀ b ∈ B, ∃ w, S.edge v w ∧ w ∈ ρ (M.condition.step q (.inl b))) ∧
    30 (∀ w, S.edge v w → ∃ b ∈ B, w ∈ ρ (M.condition.step q (.inl b)))
    31
    32def conjunction {P : Type} {n : ℕ} (l : List (Formula P n)) : Formula P n :=
    33 l.foldr Formula.conj .top
    34
    35def disjunction {P : Type} {n : ℕ} (l : List (Formula P n)) : Formula P n :=
    36 l.foldr Formula.disj .bot
    37
    38noncomputable def valuationFormula {P : Type} [Fintype P] {n : ℕ} (ν : Set P) : Formula P n := by
    39 classical
    40 exact conjunction (Finset.univ.toList.map (fun p =>
    41 if p ∈ ν then .proposition p else .negProposition p))
    42
    43noncomputable def supportFormula {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    44 (q : Fin M.condition.states) (B : Set (Fin M.unary)) : Formula P M.condition.states := by
    45 classical
    46 let bs := (Finset.univ.filter (fun b => b ∈ B)).toList
    47 exact .conj
    48 (conjunction (bs.map (fun b => .diamond (.variable (M.condition.step q (.inl b))))))
    49 (.box (disjunction (bs.map (fun b => .variable (M.condition.step q (.inl b))))))
    50
    51noncomputable def transitionFormula {P : Type} [Fintype P]
    52 (M : UnfoldAutomaton (TransitionAlphabet P)) (q : Fin M.condition.states) :
    53 Formula P M.condition.states := by
    54 classical
    55 exact disjunction (Finset.univ.toList.map (fun ν : Set P =>
    56 Formula.conj (valuationFormula ν) (.disj
    57 (if ∃ a ∈ M.leafTransition ν, M.condition.step q (.inr a) ∈ M.condition.final
    58 then .box .bot else .bot)
    59 (disjunction ((Finset.univ.filter (Realized M ν)).toList.map (supportFormula M q))))))
    60
    61axiom eval_transition {P : Type} [Fintype P]
    62 (M : UnfoldAutomaton (TransitionAlphabet P)) (q : Fin M.condition.states)
    63 (S : TransitionSystem P) (ρ : Fin M.condition.states → Set S.Vertex) (v : S.Vertex) :
    64 v ∈ (transitionFormula M q).eval S ρ ↔ OneStep M q S v ρ
    65
    66axiom realized_nonempty {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    67 (ν : Set P) (B : Set (Fin M.unary)) (h : Realized M ν B) : B.Nonempty
    68
    69def marking {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    70 {S : RankedSystems.System (TransitionAlphabet P) 0} (r : Run M S)
    71 (q : Fin M.condition.states) (v : S.val.Vertex) :
    72 Fin M.condition.states → Set S.val.Vertex :=
    73 fun p => {w | ∃ i, S.val.graph.edge v i.val (.inl w) ∧
    74 M.condition.step q (.inl (r.edgeType v i)) = p}
    75
    76axiom run_marking {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P))
    77 {S : RankedSystems.System (TransitionAlphabet P) 0} (r : Run M S)
    78 (q : Fin M.condition.states) (v : S.val.Vertex)
    79 (hfinal : ∀ h : Rank S v = 0,
    80 M.condition.step q (.inr (r.leafType v h)) ∈ M.condition.final) :
    81 OneStep M q (decode S) v (marking M r q v)
    82
    83end Lax369799.ModalTransitions
    84
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…