Modal transitions obtained from type supports
Lax369799.ModalTransitions · concepts/Lax369799/ModalTransitions.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Evidence
Lean source view on GitHub
| 1 | import Lax369799.BisimAutomata |
| 2 | import Lax369799.ModalMuCalculus |
| 3 | import Mathlib.Data.Fintype.Powerset |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Modal transitions obtained from type supports |
| 8 | type: theorem |
| 9 | --- |
| 10 | Section 6.4 replaces each transition tuple by its support. Each type in |
| 11 | the support must occur at some successor, and every successor must have |
| 12 | some type in the support. Nullary transitions test the final word state |
| 13 | and the absence of successors. These conditions are expressible by |
| 14 | finite positive modal formulas. |
| 15 | -/ |
| 16 | namespace Lax369799.ModalTransitions |
| 17 | open TransitionEncoding TransitionSystems UnfoldAutomata ModalMuCalculus |
| 18 | |
| 19 | def 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 | |
| 23 | def 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 | |
| 32 | def conjunction {P : Type} {n : ℕ} (l : List (Formula P n)) : Formula P n := |
| 33 | l.foldr Formula.conj .top |
| 34 | |
| 35 | def disjunction {P : Type} {n : ℕ} (l : List (Formula P n)) : Formula P n := |
| 36 | l.foldr Formula.disj .bot |
| 37 | |
| 38 | noncomputable 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 | |
| 43 | noncomputable 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 | |
| 51 | noncomputable 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 | |
| 61 | axiom 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 | |
| 66 | axiom realized_nonempty {P : Type} (M : UnfoldAutomaton (TransitionAlphabet P)) |
| 67 | (ν : Set P) (B : Set (Fin M.unary)) (h : Realized M ν B) : B.Nonempty |
| 68 | |
| 69 | def 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 | |
| 76 | axiom 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 | |
| 83 | end Lax369799.ModalTransitions |
| 84 |
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments