Executable modal compilation from finite Boolean tables
Lax369799.FiniteModalData · concepts/Lax369799/FiniteModalData.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
An explicit encoding orders each finite table type and makes its complete enumeration executable. Boolean valuation, leaf and support tables compile to positive modal transitions and then to scalar fixed-point syntax. Every bounded word condition and its modal tests have such a finite code.
Concept map
Lean source view on GitHub
| 1 | import Lax369799.PriorityCompilation |
| 2 | import Mathlib.Data.Fintype.Prod |
| 3 | import Mathlib.Data.Fintype.Sum |
| 4 | import Mathlib.Data.Fintype.Pi |
| 5 | import Mathlib.Logic.Encodable.Pi |
| 6 | import Mathlib.Data.Finset.Sort |
| 7 | |
| 8 | /-! |
| 9 | --- |
| 10 | title: Executable modal compilation from finite Boolean tables |
| 11 | type: theorem |
| 12 | --- |
| 13 | An explicit encoding orders each finite table type and makes its complete |
| 14 | enumeration executable. Boolean valuation, leaf and support tables compile |
| 15 | to positive modal transitions and then to scalar fixed-point syntax. |
| 16 | Every bounded word condition and its modal tests have such a finite code. |
| 17 | -/ |
| 18 | |
| 19 | namespace Lax369799.FiniteModalData |
| 20 | open ModalMuCalculus ModalTransitions UnfoldAutomata |
| 21 | |
| 22 | def elements (α : Type) [Fintype α] [Encodable α] : List α := |
| 23 | letI : LinearOrder α := LinearOrder.lift' (fun a : α => Encodable.encode a) Encodable.encode_injective |
| 24 | Finset.univ.sort (· ≤ ·) |
| 25 | |
| 26 | abbrev Data (P : Type) (u z d p : ℕ) := |
| 27 | Fin d × (Fin d → (Fin u ⊕ Fin z) → Fin d) × |
| 28 | (Fin d → Fin (p+1)) × (Fin d → Bool) × |
| 29 | ((P → Bool) → Fin z → Bool) × ((P → Bool) → (Fin u → Bool) → Bool) |
| 30 | |
| 31 | def word {P : Type} {u z d p : ℕ} (t : Data P u z d p) : WordCondition u z where |
| 32 | states := d |
| 33 | initial := t.1 |
| 34 | step := t.2.1 |
| 35 | priority := fun q => (t.2.2.1 q).val |
| 36 | final := {q | t.2.2.2.1 q = true} |
| 37 | |
| 38 | def valuationFormula {P : Type} [Fintype P] [Encodable P] {n : ℕ} (ν : P → Bool) : Formula P n := |
| 39 | conjunction ((elements P).map (fun a => if ν a then .proposition a else .negProposition a)) |
| 40 | |
| 41 | def supportFormula {P : Type} {u z d p : ℕ} (t : Data P u z d p) (q : Fin d) |
| 42 | (B : Fin u → Bool) : Formula P d := |
| 43 | let bs := (elements (Fin u)).filter (fun b => B b = true) |
| 44 | .conj (conjunction (bs.map (fun b => .diamond (.variable (t.2.1 q (.inl b)))))) |
| 45 | (.box (disjunction (bs.map (fun b => .variable (t.2.1 q (.inl b)))))) |
| 46 | |
| 47 | def transition {P : Type} [Fintype P] [Encodable P] [DecidableEq P] {u z d p : ℕ} |
| 48 | (t : Data P u z d p) (q : Fin d) : Formula P d := |
| 49 | disjunction ((elements (P → Bool)).map (fun ν : P → Bool => |
| 50 | .conj (valuationFormula ν) (.disj |
| 51 | (if ∃ a : Fin z,t.2.2.2.2.1 ν a = true ∧ t.2.2.2.1 (t.2.1 q (.inr a)) = true |
| 52 | then .box .bot else .bot) |
| 53 | (disjunction (((elements (Fin u → Bool)).filter (fun B => t.2.2.2.2.2 ν B = true)).map (supportFormula t q)))))) |
| 54 | |
| 55 | def compile {P : Type} [Fintype P] [Encodable P] [DecidableEq P] {u z d p : ℕ} |
| 56 | (t : Data P u z d p) : Sentence P := |
| 57 | let D := word t |
| 58 | PriorityCompilation.sentence (fun q => ModalAcceptanceGame.ceiling D - D.priority q) |
| 59 | (transition t) (ModalAcceptanceGame.ceiling D+1) D.initial |
| 60 | |
| 61 | open TransitionEncoding TransitionSystems |
| 62 | |
| 63 | axiom exists_table {P : Type} [Fintype P] [Encodable P] [DecidableEq P] |
| 64 | (M : UnfoldAutomaton (TransitionAlphabet P)) (p : ℕ) |
| 65 | (hp : ∀ q,M.condition.priority q ≤ p) : |
| 66 | ∃ t : Data P M.unary M.nullary M.condition.states p, |
| 67 | ∀ S,Models S (compile t) ↔ ParityWinningRegions.Winning (ModalAcceptanceGame.game M S) true |
| 68 | (ModalAcceptanceGame.position M.condition.initial S.initial) |
| 69 | |
| 70 | end Lax369799.FiniteModalData |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments