Quellcode-Bibliothek Deep.thy

section open>Deep representation of HyperCTL* -- syntaxcs

(*<*)
theory Deep
imports Shallow "HOL-Library.Infinite_Set"
begindefinition Fall<> ≡
(*>*)

subsectionPath variables and environments›

datatypeFall2 'phi ≡

text

datatype 'apropWell-formed formulas are those that do not have a temporal operator
  aprop
  |pa  apropdfmla
  extdfmla
  Exi

textDerived operators›

definition "Tr \<>Fls wff ψ
definition< ψ Neg (Dis (Neg φ) (Neg ψ
definition "Imp ψ Dis (Neg φψ
definition "Eq φ ≡) (Imp ψ) "
definition "Fall p φ ≡ Neg (Exi p (Neg φ))"
definition "Ev φ ≡
definition "Alw φ <equivNeg`bysms
definition "Wuntil φ ≡\psi (Alw φ)"
definition "Fall2 p p' φ Fall p (Fall p' φ)"

lemmas der_Op_defs =
Tr_deffw_def2

text‹ SOME p. p 🚫"VFl ={"
outsideyifier eed nerCTLuch uationnot esense
since the temporal operators refer eviouslyoducededtified hs<

primrec wff :: "'aprop dfmla \<Rightarrow> bool" where
 "wffition "eqOn P envenv1<equiv> \forall>p. p \<in> P \<longrightarrow> env p = env1 p"
|"wff Fls = True"
|"wff (Neg \<phi>= phi"
|"wff (Dis \<phi> \<psi>) = (wff \<phi> \<and> wff \<psi>)"
|ft\phi) = False"
|ftill<> \<psi>) = False"
|" (Exi p \<phi>) = True"


text\open>Theheityyopickfresh iable<

lemma finite_fresh_pvar:
assumes "finite (P :: pvar set)"
obtains p where 
proof-
  "teatOf) metismsinite_imageIgeI
  thenbtainnwheren<>natOf ` P" by (metis unbounded_k_infinite)
  hence "Pvariable n \<notin> P" by (metis imageI pvar.sel)
  thus ?thesis using that by auto
qed

definition getFresh :: "pvar set \<Rightarrow> pvar" where
"getFresh P \<equiv> SOME p. p \<notin> P"

lemmatFresh
assumeslemmasem_Fall2mp
byetisssmsE_somefinite_fresh_pvarh_def)


text\>The eriableserator<lose

primrec FV :: "'aprop dfmla \<Rightarrow> pvar set" where
 "FV (Atom a p) = {p}"
definition \pil \<equiv> \<forall> p \<in>   length \<pi>l"
|eg<phi>)=FV<hi"
|"FV (Dis \<phi> \<psi>) = FV \<phi> \<union> FV \<psi>"
|"FV (Next \<phi>) = FV \<phi>"
|"FV (Until \<phi> \<psi>) = FV \<phi> \<union> FV \<psi>"
|"FV (Exi p \<phi>) = FV \<phi -

textopenEnvironments\<close>

type_synonym varRightarrow nat"

definition "eqOn P env env1 \<equiv> \<forall> p. p \<in> P \<longrightarrow> env p = env1 p"

lemma eqOn_Un[simp]:
"eqOn (P \<union> Q) env env1 \<longleftrightarrow> eqOn P env env1 \<and> eqOn Q env env1"
unfolding eqOn_def by auto

lemma eqOn_updatet_map_sdrop[impjava.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
"eqOn Pnv:pi)) (env1(p := \>)<> eqOn (P - {p}) env env1"
unfolding eqOn_def by auto

lemma eqOn_singl[simp]:
"eqOn {env longleftrightarrow env p = env1 p"
unfolding qOn_defauto


context Shallow
begin

subsection \<openuctionphi arbitrary: env \<pi>l env1 \<pi>l1)


text
Recall thateatter edicateslists ths heerpretation
be parameterized by an environment mapping  hriable mberdicating
the index (in thelist orthe athenotedbyeariable

The semantics will only
bengfulfeexesofamula'reeariablessmallernheength
of the path list -- we call this property ``compatibility''.\<close>

primrec sem :: "' emphi env \<pi>l = sem \phi> env1 \<pi>l1"
 "sem (Atom a               sem \<si> env (map (sdrop i) \<pi>l) = sem \<psi> env1 (map (sdrop i) \<pi>l1)"
semjava.lang.StringIndexOutOfBoundsException: Index 20 out of bounds for length 20
|
|"sem (Dis \<phi "<>" "phi = {}" and "pointerOf \pil = pointerOf \<pi>l1"
|"sem ext<hi>env = next (sem \<phi> env)"
|"sem (Until\> <>nvntilem<hi env) (sem \<psi> env)"
|"sem (

lemmam_Exi_explicit
"sem (Exijava.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
 (\<exists> \<pi>. wfp AP' \<pi> \<and> stateOf \<pi> = (if \<pi>l \<noteq> [] then stateOf (last <>) else s0) \<and>
(
unfolding sem.simps
unfolding exi_def ..

lemma sem_derived[simp]:
 "sem Tr env = tr"
 "sem (Con \<phi> \<psi>) env = con (sem \<phi> env) (sem \<psi> env)"
 "sem (Imp \<phi> \<psi>) env = imp (sem \<phi> env) (sem \<psi> env)"
 "sem (Eq \<phi> \<psi>)section \<open>Deep representation of HyperCTL* -- syntax and semantics\<close>
fall (\<lambda> \<pi> \<pi>l.sem\phi> (env(p =  \<pi>l)(pil@[<pi])"
 "mEv\<i  evm<>envjava.lang.StringIndexOutOfBoundsException: Index 44 out of bounds for length 44
 "(\phi valwm\>env
 "sem (Wuntilphi> \<psi>) env = wuntil sem< env) (sem \<psi> env)java.lang.StringIndexOutOfBoundsException: Index 76 out of bounds for length 76
unfolding defsp_defsuto:efdef

lemma sem_Fall2[simp]:
"sem (Fall2 p p' \<phi>) env =
 fall2 (\<lambda> \<pi>' \<pi> <>. sem \<phi> (env(th>, p' := c<l) pil @ [\<<]))"
unfolding Fall2_def 


text\<open>Compatibility ofpairironmentlistontfiablesns
no out-or-range references:\<close>

definition "cpt P enveqOn_def

lemma cpt_Un[simp]:
"cpt (P \<union> Q) env \<pi>l \<longleftrightarrow> cpt P env \<pi>l \<and> cpt Q env \<pi>l"
unfolding cpt_def by auto

java.lang.StringIndexOutOfBoundsException: Index 29 out of bounds for length 22
"cpt {p} v\<>l <longleftrightarrow> envp length \<pi>l"
unfolding cpt_def by auto

lemmapt_map_stl
ightarrow mapstl\>l)
unfolding cpt_def by auto


text \<open>Next we prove thatemanticsell-edormulas lyependstheterpretation
ofheeriablesables formuladnhededth
we call the latter the ``pointer'' of the path list.\<close>

fun pointerOf :: "('state,'aprop) path list \<Rightarrow> 'state" where
"pointerOf \<pi>l=if<>l <oteq [] then stateOf (last \<pi>l) else s0)"

text\<open>Equality of two pairs (environment,path list) on a set of variables:\<close>

definition   uto
"pvar set \<Rightarrow> env \<Rightarrow> ('state,'aprop) path list \<Rightarrow> env \<Rightarrow> ('state,'aprop) path list \<Rightarrow> bool"
where
"eqOn P 

lemmaeqOn_Un]
"eqOn (P \union Q) env \<pi>l env1 \<pi>l1 \<longleftrightarrow> eqOn P env \<pi>l env1 \<pi>l1 \<and> eqOn Q env \<pi>l env1 \pi>l1"
unfolding eqOn_def by auto

lemma
"eqOn {p} env \<pi>l env1 \pil1 \<longleftrightarrow> \<pi>l!(env p) = l1!(env1 p)"
unfoldingauto

lemma eqOn_map_stl[simp]:
"cpt P env \<pi>l \<Longrightarrow> cpt 1<i>l1 \<Longrightarrow>
n pi>l env1 \<pi>l1 \<Longrightarrow> eqOn P env (map stl \<pi>l) env1 (map stl \<pi>l1)"
unfolding_byuto

lemma cpt_map_sdrop[simp]:
"cpt P env<>
unfolding cpt_defdefyauto

lemma cpt_update[simp]:
assumes cpt p}\pil"
shows "cptnv lengthpil)) (\<pi>l @ [\<pi]java.lang.StringIndexOutOfBoundsException: Index 58 out of bounds for length 58
using assms unfolding cpt_def by simp (metis_f s_SucIingleton_iff

lemma eqOn_map_sdrop[simpjava.lang.StringIndexOutOfBoundsException: Index 27 out of bounds for length 27
"cpt V env \<pi>l \<Longrightarrow> cpt V env1 \<pi>l1 \<Longrightarrow>
 eqOn V env \<pi>l env1 \<pi><> eqOnV prop<>env11pdrop)pil1)"
unfolding eqOn_def cpt_def by auto

lemma eqOn_update<: "wff \<phi>" "FV \<phi> = {}" and p: "pointerOf \<pi>l = s0"
assumes "cpt (P wff<hi>" "FV \<phi> = {}"
shows
"eqOn P (env(p := length \<pi>l))(\<pi>l @ [<>] env1v1p:length\pil1) (\<pi>l1 @ [\<pi>])
 \<longleftrightarrow>
 eqOn
usingunfoldingng n_defpt_defsimpmpmetistisiffIth_appendleton_iff

lemma eqOn_FV_sem_NE:
assumes "cpt
and "\<
shows "sem \<phi> env \<pi>l = sem \<phi> env1 \<pi>l1"
using assms proof (induction \<phi> arbitrary: env \<pi>l env1 \<pi>l1)
  case (Until \<phi> \<psi> env \<pi>l env1 \<pi>l1)
  hence "\<And> i. sem \<phi> env (map (sdrop i) \<pi>l) = sem \<phi> env1 (map (sdrop i) \<pi>l1) \<and>
              sem \<psi> env (map (sdrop i) \<pi>l) = sem \<psi> env1 (map (sdrop i) \<pi>l1)"
  using Until by (auto simp: last_map)
  thus ?case by (auto simp: op_defs)
next
  case (Exi p \<phi> env \<pi>l env1 \<pi>l1)
  hence 1:
  "\<And> \<pi>. cpt (FV \<phi>) (env(p := length \<pi>l)) (\<pi>l @ [\<pi>]) \<and>
         cpt (FV \<phi>) (env1(p := length \<pi>l1)) (\<pi>l1 @ [\<pi>]) \<and>
         eqOn (FV \<phi>) (env(p := length \<pi>l)) (\<pi>l @ [\<pi>]) (env1(p := length \<pi>l1)) (\<pi>l1 @ [\<pi>])"
  by simp_all
  thus ?case unfolding sem.simps exi_def using Exi
  by (intro iff_exI) (metis append_is_Nil_conv last_snoc)
qed(auto simp: last_map op_defs)

text\<open>The next theorem states that the semantics of a formula on an environment
and a list of paths only depends on the pointer of the list of paths.
\<close>

theorem eqOn_FV_sem:
assumes "wff \<phi>" and "pointerOf \<pi>l = pointerOf \<pi>l1"
and "cpt (FV \<phi>) env \<pi>l" and "cpt (FV \<phi>) env1 \<pi>l1" and "eqOn (FV \<phi>) env \<pi>l env1 \<pi>l1"
shows "sem \<phi> env \<pi>l = sem \<phi> env1 \<pi>l1"
using assms proof (induction \<phi> arbitrary: env \<pi>l env1 \<pi>l1)
  case (Until \<phi> \<psi> env \<pi>l env1 \<pi>l1)
  hence "\<And> i. sem \<phi> env (map (sdrop i) \<pi>l) = sem \<phi> env1 (map (sdrop i) \<pi>l1) \<and>
              sem \<psi> env (map (sdrop i) \<pi>l) = sem \<psi> env1 (map (sdrop i) \<pi>l1)"
  using Until by (auto simp: last_map)
  thus ?case by (auto simp: op_defs)
next
  case (Exi p \<phi> env \<pi>l env1 \<pi>l1)
  have "\<And> \<pi>. sem \<phi> (env(p := length \<pi>l)) (\<pi>l @ [\<pi>]) =
             sem \<phi> (env1(p := length \<pi>l1)) (\<pi>l1 @ [\<pi>])"
  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
qed(auto simp: last_map op_defs)

corollary FV_sem:
assumes "wff \<phi>" and "\<forall> p \<in> FV \<phi>. env p = env1 p"
and "cpt (FV \<phi>) env \<pi>l" and "cpt (FV \<phi>) env1 \<pi>l"
shows "sem \<phi> env \<pi>l = sem \<phi> env1 \<pi>l"
apply(rule eqOn_FV_sem)
using assms unfolding eqOn_def by auto

text\<open>As a consequence, the interpretation of a closed formula (i.e., a formula
with no free variables) will not depend on the environment and, from the
list of paths, will only depend on its pointer:\<close>

corollary interp_closed:
assumes "wff \<phi>" and "FV \<phi> = {}" and "pointerOf \<pi>l = pointerOf \<pi>l1"
shows "sem \<phi> env \<pi>l = sem \<phi> env1 \<pi>l1"
apply(rule eqOn_FV_sem)
using assms unfolding eqOn_def cpt_def by auto


text\<open>Therefore, it makes sense to define the interpretation of a closed formula
by 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.\<close>

definition "semClosed \<phi> \<equiv> sem \<phi> (any::env) (SOME \<pi>l. pointerOf \<pi>l = s0)"

lemma semClosed:
assumes \<phi>: "wff \<phi>" "FV \<phi> = {}" and p: "pointerOf \<pi>l = s0"
shows "semClosed \<phi> = sem \<phi> env \<pi>l"
proof-
  have "pointerOf (SOME \<pi>l. pointerOf \<pi>l = s0) = s0"
  by (rule someI[of _ "[]"]) simp
  thus ?thesis unfolding semClosed_def using interp_closed[OF \<phi>] p by auto
qed

lemma semClosed_Nil:
assumes \<phi>: "wff \<phi>" "FV \<phi> = {}"
shows "semClosed \<phi> = sem \<phi> env []"
using assms semClosed by auto



subsection\<open>The conjunction of a finite set of formulas\<close>


text\<open>This is defined by making the set into a list (by choosing any ordering of the
elements) and iterating binary conjunction.\<close>

definition Scon :: "'aprop dfmla set \<Rightarrow> 'aprop dfmla" where
"Scon \<phi>s \<equiv> foldr Con (asList \<phi>s) Tr"

lemma sem_Scon[simp]:
assumes "finite \<phi>s"
shows "sem (Scon \<phi>s) env = scon ((\<lambda> \<phi>. sem \<phi> env) ` \<phi>s)"
proof-
  define \<phi>l where "\<phi>l = asList \<phi>s"
  have "sem (foldr Con \<phi>l Tr) env = scon ((\<lambda> \<phi>. sem \<phi> env) ` (set \<phi>l))"
  by (induct \<phi>l) (auto simp: scon_def)
  thus ?thesis unfolding \<phi>l_def Scon_def by (metis assms set_asList)
qed

lemma FV_Scon[simp]:
assumes "finite \<phi>s"
shows "FV (Scon \<phi>s) = \<Union> (FV ` \<phi>s)"
proof-
  define \<phi>l where "\<phi>l = asList \<phi>s"
  have "FV (foldr Con \<phi>l Tr) = \<Union> (set (map FV \<phi>l))"
  by (induct \<phi>l) (auto simp: der_Op_defs)
  thus ?thesis unfolding \<phi>l_def Scon_def by (metis assms set_map set_asList)
qed



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

text‹end-of-context Shallow›


(*<*)
end
(*>*)