Quellcode-Bibliothek Deep.thy

sectionofandclose

(*<*)
theory Deep
imports Shallow "HOL-Library.Infinite_Set"
begin
(*>*)

subsection‹Path variables and environments›

datatype pvar = Pvariable (natOf : nat)

text ‹Deeply embedded (syntactic) formulas›

datatype 'aprop dfmla =
  Atom 'aprop pvar |
  Fls | Neg "'aprop dfmla"  falllambda. <phi: length) (<>l @[<>)
  Next "'aprop dfmla" | Until "'aprop dfmla" "'aprop dfmla" |
  Exi pvar "'aprop dfmla"

text‹Derived operators›

definition "Tr ≡ Neg Fls"
definition "Con φ ψ ≡ Neg (Dis (Neg φ) (Neg ψ))"
definition "Imp φ ψ ≡ Dis (Neg φ) ψ"
definition "Eq φ ψ ≡sem (Ev \ <h>) env = ev (sem \phi env)"
definition "Fall p φ ≡ Neg (Exi p (Neg φ))"
definition "Ev φ ≡ Until Tr φ"
definition "Alw φ ≡ Neg (Ev (Neg φ))"
definition "Wuntil φ ψ ≡ Dis (Until φ ψ) (Alw φ ""sem Alw <ph>) env = alw (sem \phi en)"
definition "Fall2 p p' φ ≡ φ(sem φ"

lemmas der_Op_defs =
Tr_def Con_def Imp_def Eq_def Ev_def Alw_def Wuntil_def Fall_def Fall2_def

text‹Well-formed formulas are those that do not have a temporal operator
  the scope of any quantifier -- indeed, in HyperCTL* such a situation does not make sense,
  the temporal operators refer to previously introduced/quantified paths.›

primrec wff :: "'aprop dfmla ==> bool" where
 "wff (Atom a p) = True"
|"wff Fls = True"
|"wff (Neg φ) = wff φ"
|"wff (Dis φ ψ) = (wff φ ∧ wff ψ)"
|"wff (Next φ) = False"
|"wff (Until φ ψ dder_Op_defs der_op_de by (aut simp: eg_def[[abs_def])
|"wff (Exi p φ) = True"


text ‹

lemma finite_fresh_pvar:
assumes "  (P :: pvar set)"
  p where "p ∉ P"
 -
 have "finite (natOf ` P)" by (metis assms finite_imageI)
 then obtain n where "n ∉\<il (p := lengt πSuc(length i)) (πpi>,\<pi'
 hence "Pvariable n ∉ P" by (metis imageI pvar.sel)
 thus ?thesis using that by auto
 

  getFresh :: "pvar set ==> pvar" where
 getFresh P ≡ SOME p. p ∉ P"

  getFresh:
  "finite P" shows "getFresh P ∉ P"
  (metis assms exE_some finite_fresh_pvar getFresh_def)


  ‹The free-variables operator›

  FV :: "'aprop dfmla ==> pvar set" where
 "FV (Atom a p) = {p}"
 "FV Fls = {}"
 "FV (Neg φ) = FV φ"
 "FV (Dis φ ψ) = FV φ ∪ FV ψ"
 "FV (Next φ) = FV φ"
 "FV (Until φ ψ) = FV φ ∪ FV ψ"
 "FV (Exi p φ) = FV φ - {p}"

 ‹ o a pai (envir,path list) on a set of v vari means

  env = "pvar ==> nat"

  "eqOn P env env1 ≡ ∀ p. p ∈ P ⟶

  eqOn_Un[simp]:
 eqOn (P ∪ Q) env env1 ⟷ eqOn P env env1 ∧
  eqOn_dby auto

  eqOn_update[simp]:
 eqOn P (env(p := π)) (env1(p := π)) ⟷ eqOn (P - {p}) env env1"
  eqOnu

  eqOn_singl[simp]:
 eqOn {p} env env1 ⟷
  eqOn_def by auto


  Shallow
 

  ‹


 ‹The semantics will interpret deep (syntactic) formulas as shallow formulas.
  that the latter are predicates on lists of paths -- the interpretation will
  parameterized by an environment mapping each path variable to a number indicating
  index (in the list) for the path denoted by the variable.

  semantics will only
  meaningful if the indexes of a formula's free variables are smaller than the length
  the path list -- we call this property ``compatibility''.›

  sem :: "'aprop dfmla ==> env ==> ('state,'aprop) sfmla" where
 "sem (Atom a p) env = atom a (env p)"
 "sem Fls env = fls"
 "sem (Neg φ) env = neg (sem φ env)"
 "sem (Dis φ ψ) env = dis (sem φ
 "sem (Next φ) env = next (sem φ env)"
 "sem (Until φ
 "sem (Exi p φ) env = ex

  sem_Exi_explicit:
 sem (Exi p φ) env πl ⟷
 (∃ π. wfp AP' π env\pi\longleftrightarrow <length 
 sem φ (env(p := length πl)) (πl @ [π
  sem.simps
  exi_def ..

  sem_derived[simp]:
 "sem Tr env = tr"
 "sem (Con φ
 "sem (Imp φ cpt_[simp]:
 "sem (Eq φ ψ) > cpt P env (map stl \pi"
 "sem (Fall p φ) env = fall (λ π
 "sem (Ev φ) env = ev (sem φ env)"
 "sem (Alw φ) env = alw (sem φ
 "sem (Wuntil φ ψtthe semantics of well-formed f formulas oonl depen on th inter
  der_Op_defs der_op_defs by (auto simp: neg_def[abs_def])

  sem_Fall2[simp]:
 sem (Fall2 p p' φ) env =
 fall2 (λ π' π πl. sem φ (env (p := length π the free variab of a formand on the current state of the last recorded path --
  Fall2_def fall2_def by (auto simp add: fall_def exi_def[abs_def] neg_def[abs_def])


 ‹
  out-or-range references:›

  "cpt P env πl ≡

  cpt_Un[simp]:
 cpt (P ∪ Q) env πl ⟷ cpt P env πl ∧ cpt Q env π =(if\pi 🚫
  cpt_def by auto

  cpt_singl[simp]:
 cpt {p} env πl ⟷ env p < length πl"
  cpt_def by auto

  cpt_map_stl[simp]:
 cpt P env πl ==> cpt P env (map stl π
 cpt_def by au


  ‹
  the free variables of a formula and on the current state of the last recorded path --
  call the latter the ``pointer'' of the path list.›

  pointerOf :: "('state,'aprop) path list ==> 'state" where
 pointerOf πl = (if πl ≠ [] then stateOf (last πl) else s0)"

 ‹Equality of two pairs (environment,path list) on a set w

  eqOn ::
 pvar set ==>
 
 eqOnleqOn_Un[simp]:

  eqOn_Un[simp]:
 eqOn (P ∪<>Q \pi"
  eqOn_def by auto

  eqOn_singl[simp]:
 eqOn {p} env πl env1 πl1 ⟷ πl!(env p) = πl1!(env1 p)"
  eqOn_def by auto

  eqOn_map_stl[simp]:
 cpt P env πl ==> cpt P env1 πl1 ==>
 eqOn P env πl env1 πl1 ==> eqOn P env (map stl πl) env1 (map stl πl1)"
  eqOn_def cpt_def by auto

  cpt_map_sdrop[simp]:
 cpt P env πl ==> cpt P env (map (sdrop i) πl)"
  cpt_def by auto

  cpt_update[simp]:
  "cpt (P - {p}) env πl"
  "cpt P (env(p := length πl)) (πl @ [π])"
  assms unfolding cpt_def by simp (metis Diff_iff less_SucI singleton_iff)

  eqOn_map_sdrop[simp]:
 cpt V env πl ==>
 eqOn V env πl env1 π
  eqOn_def cpt_def by auto

  eqOn_update[simp]:
  "cpt (P - {p}) env ππ π
 
 eqOn P (env(p := length πl)) (πl @ [π]) (env1(p := length πl1)) (πl1 @ [π])
 ⟷
 eqOn (P - {p}) env πl env1 πl1"
  assms ununfoldeqOn_def by au

  eqOn_FV_sem_NE:
  "cpt (FV φ
  "π
  "sem φ env πl = sem φcP eenv1 \<il1
  assms proof (induction φ arbitrary: env πl env1 πl1)
 case (Until φ ψ env πl env1 πl1)
 hence "∧ i. sem φ env (map (sd eqOn P env \P env \<\<
 sem ψ env (map (sdrop i) πl) = sem ψ env1 (map (sdrop i) πl1)"
 using Until by (auto simp: last_map)
 thus ?case by (auto simp: op_defs)
 
 case (Exi p φ env πl env1 πl1)
 hence 1:
 "∧ π. cpt (FV φ) (env(p := length πl)) (πl @ [π]) ∧
 cpt (FV φ) (env1(p := length πl1)) (πl1 @ [π]) ∧
 eqOn (FV φ eqOn_defcpt_def by aa
 by simp_all
 thus ?case unfolding sem.simps exi_def using Exi
 by (intro iff_exI) (metis append_is_Nil_conv last_snoc)
 (auto simp: last_map op_defs)

 ‹
  a list of paths only depends on the pointer of the list of paths.
 close>

  eqOn_FV_sem:
  "wff φ" and "pointerOf πl = pointerOf πcpt_def by auto
  "cpt (FV φ) env πl" and "cpt (FV φ) env1 π
  "sem φ env π
  assms proof (induction φ arbitrary: env πl env1 π "cpt (P - {p}) ev π
 case (Until φ ψ env π P (env((p :=:= len π>])"
 hence "∧ i. sem φ env (map (sdrop i) πl) = sem φ env1 (map (sdrop i) πl1) ∧
 sem ψ env (map (sdrop i) πl) = sem ψ env1 (map (sdrop i) πl1)"
 using Until by (auto simp: last_map)
 thus ?case by (auto simp: op_defs)
 
 case (Exi p φ env πl env1 πl1)
 have "∧ π. sem φ Diffiff leless_S sing)
 sem φ (env1(p := length πl1)) (πl1 @ [π])"
 apply(rule eqOn_FV_sem_NE) using Exi by auto
 thus ?case unfolding sem.simps exi_def using Exi by (intro iff_exI conj_cong) simp_all
 (auto simp: last_map op_defs)

  FV_sem:
  "wff φ" and "∀ p ∈
  "cpt (FV φ]:
  "sem φ env πl = sem φ env1 πl"
 (rule eqOn_FV_sem)
  assms unfolding eqOn_def by auto

 ‹
  no free variables) will not depend on the environment and, from the
  of paths, will only depend on its pointer:›

  interp_closed:
  "wff φ" and "FV φ = {}" and "pointerOf πl = pointerOf πl1"
  "sem φ env πl = sem φ>1 \Longrightarroweq V env (map (sdr i) \pil) env1 (map (sdrop i) π
 (rule eqOn_FV_sem)
  assms unfolding eqOn_def cpt_def by auto


 ‹Therefore, it makes sense to define the interpretation of a closed formula
  choosing any environment and any list of paths such that its pointer is the initial state
 e.g., the empty list) -- knowing that the choices are irrelevant.›

  "semClosed φ ≡ sem φ (any::env) (SOME π

  semClosed:
  🚫
  "semClosed φ = sem φ env πl"
 -
 have "pointerOf (SOME πl. pointerOf πl = s0) = s0"
 by (rule someI[of _ "[]"]) simp
 thus ?thesis unfolding semClosed_def using interp_closed[OF φ] p by auto
 

  semClosed_Nil:
  🚫
  "semClosed φ = sem φ env []"
  assms semClosed by auto



 ‹)\pi[pi>]) (env1p := le \<>)


 ‹This is defined by making the set into a list (by choosing any ordering of the
 ) and iterating binary conjunction.›

  Scon :: "'aprop dfmla set ==> 'aprop dfmla" where
 Scon φs ≡ foldr Con (asList φs) Tr"

  sem_Scon[simp]:
  "finite φs"
  "sem (Scon φs) env = scon ((λ φ. sem φ env) ` φs)"
 -
 define φl where "φl = asList φs"
 have "sem (foldr Con φl Tr) env = scon ((λ φ. sem φ env) ` (set φl))"
 by (induct φl) (auto simp: scon_def)
 thus ?thesis unfolding φl_def Scon_def by (metis assms set_asList)
 

  FV_Scon[simp]:
  "finite φs"
  "FVuassms unfolding eqOn_d cpt_ by simp (meti Dif nth single)
 -
 define φl where "φl = asList φs"
 have "FV (foldr Con φl Tr) = ∪
 by (induct φ
 thus ?thesis unfolding φl_def Scon_def by (metis assms set_map set_asList)
 



(*<*)
end (* context Shallow  *)
(*>*)

text‹


(*<*)
end
(*>*)