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

Executable modal compilation from finite Boolean tables

Lax369799.FiniteModalData · concepts/Lax369799/FiniteModalData.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 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
    21 concepts; 3 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.PriorityCompilation
    2import Mathlib.Data.Fintype.Prod
    3import Mathlib.Data.Fintype.Sum
    4import Mathlib.Data.Fintype.Pi
    5import Mathlib.Logic.Encodable.Pi
    6import Mathlib.Data.Finset.Sort
    7
    8/-!
    9---
    10title: Executable modal compilation from finite Boolean tables
    11type: theorem
    12---
    13An explicit encoding orders each finite table type and makes its complete
    14enumeration executable. Boolean valuation, leaf and support tables compile
    15to positive modal transitions and then to scalar fixed-point syntax.
    16Every bounded word condition and its modal tests have such a finite code.
    17-/
    18
    19namespace Lax369799.FiniteModalData
    20open ModalMuCalculus ModalTransitions UnfoldAutomata
    21
    22def elements (α : Type) [Fintype α] [Encodable α] : List α :=
    23 letI : LinearOrder α := LinearOrder.lift' (fun a : α => Encodable.encode a) Encodable.encode_injective
    24 Finset.univ.sort (· ≤ ·)
    25
    26abbrev 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
    31def 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
    38def 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
    41def 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
    47def 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
    55def 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
    61open TransitionEncoding TransitionSystems
    62
    63axiom 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
    70end Lax369799.FiniteModalData
    Show Proof

    Discussion

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

    Loading discussion…