Local Diamond Unfolding (Section 3.2 and 3.3)

Diamonds: Dset, Y and Φ_⋄

def Dset : Program → List (List Formula × List Program)

Unfold a given program into combinations of test formulas and lists of programs, assuming the program is used inside a diamond.

Equations

• One or more equations did not get rendered due to their size.
• Dset (·a) = [([], [·a])]
• Dset (?'τ) = [([τ], [])]
• Dset (α⋓β) = Dset α ∪ Dset β

def Dl : List Program → List (List Formula × List Program)

Like Dset, but applied to a whole list of programs. This is used to deal with loaded diamonds.

Equations

• One or more equations did not get rendered due to their size.
• Dl [] = [([], [])]
• Dl [α] = Dset α

@[simp]

theorem Dl_singleton {α : Program} : Dl [α] = Dset α

@[simp]

theorem Dl_atomic_cons {a : ℕ} {αs : List Program} : Dl (·a :: αs) = [([], ·a :: αs)]

theorem relateSeq_Dset_imp_relate {α : Program} {W✝ : Type} {M : KripkeModel W✝} {w v : W✝} {X : List Formula} {δ : List Program} : (X, δ) ∈ Dset α → (M, w) ⊨ con X → relateSeq M δ w v → relate M α w v

theorem Dset_mem_test (α : Program) (φ : Formula) {Fs : List Formula} {δ : List Program} (in_D : (Fs, δ) ∈ Dset α) (φ_in_Fs : φ ∈ Fs) : ∃ (τ : Formula) (_ : τ ∈ testsOfProgram α), φ = τ

A test formula coming from Dset comes from a test in the given program.

theorem Dset_mem_sequence (α : Program) {Fs : List Formula} {δ : List Program} (in_D : (Fs, δ) ∈ Dset α) : δ = [] ∨ ∃ (a : ℕ) (δ' : List Program), δ = ·a :: δ'

A list of programs coming from H is either empty or starts with an atom.

theorem keepFreshDset {x : ℕ ⊕ ℕ} (α : Program) : x ∉ α.voc → ∀ (F : List Formula) (δ : List Program), (F, δ) ∈ Dset α → x ∉ F.fvoc ∧ x ∉ δ.pvoc

theorem Dset_goes_down_prog (α : Program) {Fs : List Formula} {δ : List Program} (in_D : (Fs, δ) ∈ Dset α) {γ : Program} (in_δ : γ ∈ δ) : if α.isAtomic then γ = α else if α.isStar then lengthOfProgram γ ≤ lengthOfProgram α else lengthOfProgram γ < lengthOfProgram α

This is used by PreState.loadedExists

def Yset : List Formula × List Program → Formula → List Formula

An intermediate step to define unfoldDiamond. This is not used in the paper.

Equations

• Yset (F, δ) x✝ = F ∪ [~⌈⌈δ⌉⌉x✝]

def unfoldDiamond (α : Program) (φ : Formula) : List (List Formula)

Φ_◇(α,ψ)

Equations

• unfoldDiamond α φ = List.map (fun (Fδ : List Formula × List Program) => Yset Fδ φ) (Dset α)

theorem unfoldDiamondContent (α : Program) (ψ : Formula) (X : List Formula) : X ∈ unfoldDiamond α ψ → ∀ φ ∈ X, φ = ~ψ ∨ (∃ τ ∈ testsOfProgram α, φ = τ) ∨ ∃ (a : ℕ) (δ : List Program), φ = ~⌈·a⌉⌈⌈δ⌉⌉ψ

Where formulas in the diamond unfolding can come from. Inspired by unfoldBoxContent.

theorem unfoldDiamond_voc {x : ℕ ⊕ ℕ} {α : Program} {φ : Formula} {L : List Formula} (L_in : L ∈ unfoldDiamond α φ) {ψ : Formula} (ψ_in : ψ ∈ L) (x_in_voc_ψ : x ∈ ψ.voc) : x ∈ α.voc ∨ x ∈ φ.voc

theorem unfoldDiamond_voc_fin {x : ℕ ⊕ ℕ} {α : Program} {φ : Formula} {X : Finset Formula} (X_in : X ∈ (unfoldDiamond α φ).toFinFin) {ψ : Formula} (ψ_in : ψ ∈ X) (x_in_voc_ψ : x ∈ ψ.voc) : x ∈ α.voc ∨ x ∈ φ.voc

Finset version of unfoldDiamond_voc.

theorem guardToStarDiamond {β : Program} {σ0 σ1 ρ ψ : Formula} (x : ℕ) (x_notin_beta : Sum.inl x ∉ β.voc) (beta_equiv : (~⌈β⌉~·x) ≡ ·x ⋀ σ0 ⋁ σ1) (repl_imp_rho : repl_in_F x ρ σ1 ⊨ ρ) (notPsi_imp_rho : ~ψ ⊨ ρ) : (~⌈∗β⌉ψ) ⊨ ρ

theorem localDiamondTruth (γ : Program) (ψ : Formula) : (~⌈γ⌉ψ) ≡ dis (List.map (fun (Fδ : List Formula × List Program) => con (Yset Fδ ψ)) (Dset γ))

def pairRel {W : Type} (M : KripkeModel W) : Program × W → Program × W → Prop

Helper function to trick "List.Chain r" to use a different r at each step.

Equations

• pairRel M (fst, v) (α, w) = relate M α v w

theorem relateSeq_toChain' {W : Type} {M : KripkeModel W} {δ : List Program} {v w : W} : relateSeq M δ v w → δ ≠ [] → ∃ (l : List W), l.length + 1 = δ.length ∧ List.IsChain (pairRel M) (((?'⊤) :: δ).zip (v :: l ++ [w]))

theorem existsDiamondDset {W✝ : Type} {M : KripkeModel W✝} {γ : Program} {v w : W✝} (v_γ_w : relate M γ v w) : ∃ Fδ ∈ Dset γ, (M, v) ⊨ Fδ.1 ∧ relateSeq M Fδ.2 v w

Loaded Diamonds (Section 3.3)

The Option is used here because unfolding of tests can lead to free nodes.

def YsetLoad : List Formula × List Program → LoadFormula → List Formula × Option NegLoadFormula

Equations

• YsetLoad (F, δ) x✝ = (F, some (~'⌊⌊δ⌋⌋x✝))

def YsetLoad' : List Formula × List Program → Formula → List Formula × Option NegLoadFormula

Equations

• YsetLoad' (F, δ) x✝ = match splitLast δ with | none => (F ∪ [~x✝], none) | some (δ, β) => (F, some (~'loadMulti δ β x✝))

def unfoldDiamondLoaded (α : Program) (χ : LoadFormula) : List (List Formula × Option NegLoadFormula)

Loaded unfolding for ~'⌊α⌋(χ : LoadFormula)

Equations

• unfoldDiamondLoaded α χ = List.map (fun (Fδ : List Formula × List Program) => YsetLoad Fδ χ) (Dset α)

def unfoldDiamondLoaded' (α : Program) (φ : Formula) : List (List Formula × Option NegLoadFormula)

Loaded unfolding for ~'⌊α⌋(φ : Formula)

Equations

• unfoldDiamondLoaded' α φ = List.map (fun (Fδ : List Formula × List Program) => YsetLoad' Fδ φ) (Dset α)

def pairUnload : List Formula × Option NegLoadFormula → List Formula

Equations

• pairUnload (xs, none) = xs
• pairUnload (xs, some nlf) = xs ∪ [negUnload nlf]

def pairUnloadSet : Finset Formula × Option NegLoadFormula → Finset Formula

Equations

• pairUnloadSet (xs, none) = xs
• pairUnloadSet (xs, some nlf) = xs ∪ {negUnload nlf}

theorem unfoldDiamondLoaded_eq (α : Program) (χ : LoadFormula) : List.map pairUnload (unfoldDiamondLoaded α χ) = unfoldDiamond α χ.unload

theorem unfoldDiamondLoaded'_eq (α : Program) (φ : Formula) : List.map pairUnload (unfoldDiamondLoaded' α φ) = unfoldDiamond α φ