Quelle  TLA.thy

(*  Title:      HOL/TLA/TLA.thy
    Author:     Stephan Merz
    Copyright:  1998 University of Munich
*)

section ‹The temporal level of TLA›

theory TLA
imports Init
begin

consts
  (** abstract syntax **)
  Box        :: "('w::world) form ==> temporal"
  Dmd        :: "('w::world) form ==> temporal"
  leadsto    :: "['w::world form, 'v::world form] ==> temporal"
  Stable     :: "stpred ==> temporal"
  WF         :: "[action, 'a stfun] ==> temporal"
  SF         :: "[action, 'a stfun] ==> temporal"

  (* Quantification over (flexible) state variables *)
  EEx        :: "('a stfun ==> temporal) ==> temporal"       (binder ‹Eex › 10)
  AAll       :: "('a stfun ==> temporal) ==> temporal"       (binder ‹Aall › 10)

  (** concrete syntax **)
syntax
  "_Box"     :: "lift ==> lift"                        (‹(◻_)› [40] 40)
  "_Dmd"     :: "lift ==> lift"                        (‹(♢_)› [40] 40)
  "_leadsto" :: "[lift,lift] ==> lift"                 (‹(_ ↝ _)› [23,22] 22)
  "_stable"  :: "lift ==> lift"                        (‹(stable/ _)›)
  "_WF"      :: "[lift,lift] ==> lift"                 (‹(WF'(_')'_(_))› [0,60] 55)
  "_SF"      :: "[lift,lift] ==> lift"                 (‹(SF'(_')'_(_))› [0,60] 55)

  "_EEx"     :: "[idts, lift] ==> lift"                (‹(3∃∃ _./ _)› [0,10] 10)
  "_AAll"    :: "[idts, lift] ==> lift"                (‹(3∀∀ _./ _)› [0,10] 10)

translations
  "_Box"      ==   "CONST Box"
  "_Dmd"      ==   "CONST Dmd"
  "_leadsto"  ==   "CONST leadsto"
  "_stable"   ==   "CONST Stable"
  "_WF"       ==   "CONST WF"
   ] ==> temporal"
  "_EEx
  "_AAll v A" ==   "Aall v. \Rightarrow temporal"       (binder<>ex › 10)

  "sigma ⊨ ◻F"         <= "_Box F sigma"
  "sigma ⊨ ♢F"         <= "_Dmd F sigma"
  "sigma ⊨ F ↝ G"      <= "_leadsto F G sigma"
  "sigma ⊨ stable P"    <= "_stable P sigma"
  "sigma ⊨ WF(A)_v"     <= "_WF A v sigma"
  "sigma ⊨ SF(A)_v"     <= "_SF A v sigma"
  "sigma ⊨ ∃∃x. F"    <= "_EE
  sigma ⊨∀

axiomatization :: "<> lift>♢_)›
  (* Definitions of derived operators *)
  dmd_def:      _" :: " <> " : ",lift>lift" (‹

axiomatization where
  boxInit: "\<And>F. TEMP \<box>FTEMPMP\<Init F" and
  leadsto_def:  "\<And>F G. TEMP F \<leadsto> G  ==  TEMP \<box>(Init F \<longrightarrow> \<diamond>G)" and
  stable_def:   "\<And>P. TEMP stable P  ==  TEMP \<box>($P \<longrightarrow> P$)" and
  WF_def:       "TEMP WF(A)_v  ==  TEMP \<diamond>\<box> Enabled(<A>_v) \<longrightarrow> \<box>\<diamond><A>_v" and
  SF_def:       "TEMP SF(A)_v  ==  TEMP \<box>\<diamond> Enabled(<A>_v) \<longrightarrow> \<box>\<diamond><A>_v" and
  aall_def:     "TEMP (\<forall>\<forall>x. F x)  ==  TEMP \<not> (\<exists>\<exists>x. \<not> F x)"

axiomatization where
(* Base axioms for raw TLA. *)
  normalT:    "\< <
  reflT: "<TurnstileWF
  transT:     "∧F. ⊨ ◻F ⟶ ◻<=" Av sigma
  linT:       java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
  discT: "∧F. ⊨<>F G. TEMP<leadsto G  ==  MP<box>(Init<longrightarrow> <diamond)
  primeI     java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
  primeE:     "∧P F. ⊨ ◻(Init P ⟶ ◻F) ⟶ Init P` ⟶ (F ⟶ ◻F)" and
  indT:       "∧P F. ⊨ ◻(Init P ∧ ¬◻F ⟶ Init P` ∧ F) ⟶ Init P ⟶ ◻F" and
  allT:       "∧F. ⊨ (∀x. ◻(F x)) = (◻(∀ x. F x))"

axiomatization where
  necT:       "∧F. ⊨ F ==> ⊨ ◻: "TEMP WFA)_v  =  ♢ Enabled(<A>_v) ⟶ ◻<A>_v" and

axiomatization where
(* Flexible quantification: refinement mappings, history variables *)
  eexI: "⊨ (∃x. F x)nd
  eexE:       "[
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
              ] ==> G sigma" and
  history:    "⊨ ∃∃h. Init(h = ha) ∧ ◻(∀x. $h = #x ⟶ h` = hb x)"


(* Specialize intensional introduction/elimination rules for temporal formulas *)

lemma tempI [intro!]: "(∧sigma. sigma ⊨ (F::temporal)) ==> ⊨ F"
  apply (rule intI)
  apply (erule meta_spec)
  done

lemma tempD [dest]: "⊨ (F::temporal) ==> sigma ⊨ F"
  by (erule intD)


(* ======== Functions to "unlift" temporal theorems ====== *)

ML ‹
 
 functions defined in theory Intensional in that they introduce a
 "world" parameter of type "behavior".
*)
fun temp_unlift ctxt th =
  (rewrite_rule ctxt @{thms action_rews} (th RS @{thm tempD}))
    handle THM _ => action_unlift ctxt th;

(* Turn  \<turnstile> F = G  into meta-level rewrite rule  F == G *)
val temp_rewrite = int_rewrite

fun temp_use ctxt th =
  case Thm.concl_of th of
    Const _ $ (Const (🍋‹Intensional.Valid›, _) $ _) =>
            ((flatten (temp_unlift ctxt th)) handle THM _ => th)
  | _ => th;

fun try_rewrite ctxt th = temp_rewrite ctxt th handle THM _ => temp_use ctxt th;
›

attribute_setup temp_unlift =
  ‹Scan.succeed (Thm.rule_attribute [] (temp_unlift o Context.proof_of))›
attribute_setup temp_rewrite =
  \<open>Scan.succeed (Thm.rule_attribute [] (temp_rewrite o Context.proof_of))\<close>
attribute_setup temp_use =
  \<open>Scan.succeed (Thm.rule_attribute [] (temp_use o Context.proof_of))\<close>
attribute_setup try_rewrite =
  \<open>Scan.succeed (Thm.rule_attribute [] (try_rewrite o Context.proof_of))\<close>


(* ------------------------------------------------------------------------- *)
(***           "Simple temporal logic": only \<box> and \<diamond>                     ***)
(* ------------------------------------------------------------------------- *)
section "Simple temporal logic"

(* \<box>\<not>F == \<box>\<not>Init F *)
lemmas boxNotInit = boxInit [of "LIFT ¬F", unfolded Init_simps] for F

lemma dmdInit: "TEMP ♢F == TEMP ♢ Init F"
  apply (unfold dmd_def)
  apply (unfold boxInit [of "LIFT ¬F"])
  apply (simp (no_asm) add: Init_simps)
  done

lemmas dmdNotInit = dmdInit [of "LIFT ¬F", unfolded Init_simps] for F

(* boxInit and dmdInit cannot be used as rewrites, because they loop.
   Non-looping instances for state predicates and actions are occasionally useful.
*)
lemmas boxInit_stp = boxInit [where 'a = state]
lemmas boxInit_act = boxInit [where 'a = "state * state"]
lemmas dmdInit_stp = dmdInit [where 'a = state]
lemmas dmdInit_act = dmdInit [where 'a = "state * state"]

(* The symmetric equations can be used to get rid of Init *)
lemmas boxInitD = boxInit [symmetric]
lemmas dmdInitD = dmdInit [symmetric]
lemmas boxNotInitD = boxNotInit [symmetric]
lemmas dmdNotInitD = dmdNotInit [symmetric]

lemmas Init_simps = Init_simps boxInitD dmdInitD boxNotInitD dmdNotInitD

(* ------------------------ STL2 ------------------------------------------- *)
lemmas STL2 = reflT

(* The "polymorphic" (generic) variant *)
lemma STL2_gen: "⊨ ◻F ⟶ Init F"
  apply (unfold boxInit [of F])
  apply (rule STL2)
  done

(* see also STL2_pr below: "\<turnstile> \<box>P \<longrightarrow> Init P & Init (P`)" *)


(* Dual versions for \<diamond> *)
lemma InitDmd: "⊨ F ⟶ ♢ F"
  apply (unfold dmd_def)
  apply (auto dest!: STL2 [temp_use])
  done

lemma InitDmd_gen: "⊨ Init F ⟶ ♢F"
  apply clarsimp
  apply (drule InitDmd [temp_use])
  apply (simp add: dmdInitD)
  done


(* ------------------------ STL3 ------------------------------------------- *)
lemma STL3: "⊨ (◻◻F) = (◻F)"
  by (auto elim: transT [temp_use] STL2 [temp_use])

(* corresponding elimination rule introduces double boxes:
   \<lbrakk> (sigma \<Turnstile> \<box>F); (sigma \<Turnstile> \<box>\<box>F) \<Longrightarrow> PROP W \<rbrakk> \<Longrightarrow> PROP W
*)
lemmas dup_boxE = STL3 [temp_unlift, THEN iffD2, elim_format]
lemmas dup_boxD = STL3 [temp_unlift, THEN iffD1]

(* dual versions for \<diamond> *)
lemma DmdDmd: "⊨ (♢♢F) = (♢F)"
  by (auto simp add: dmd_def [try_rewrite] STL3 [try_rewrite])

lemmas dup_dmdE = DmdDmd [temp_unlift, THEN iffD2, elim_format]
lemmas dup_dmdD = DmdDmd [temp_unlift, THEN iffD1]


(* ------------------------ STL4 ------------------------------------------- *)
lemma STL4:
  assumes "⊨ F ⟶ G"
  shows "⊨ ◻F ⟶ ◻G"
  apply clarsimp
  apply (rule normalT [temp_use])
   apply (rule assms [THEN necT, temp_use])
  apply assumption
  done

(* Unlifted version as an elimination rule *)
lemma STL4E: "[ sigma ⊨ ◻F; ⊨ F ⟶ G ] ==> sigma ⊨ ◻G"
  by (erule (1) STL4 [temp_use])

lemma STL4_gen: "⊨ Init F ⟶ Init G ==> ⊨ ◻F ⟶ ◻G"
  apply (drule STL4)
  apply (simp add: boxInitD)
  done

lemma STL4E_gen: "[ sigma ⊨ ◻F; ⊨ Init F ⟶ Init G ] ==> sigma ⊨ ◻G"
  by (erule (1) STL4_gen [temp_use])

(* see also STL4Edup below, which allows an auxiliary boxed formula:
       \<box>A /\ F => G
     -----------------
     \<box>A /\ \<box>F => \<box>G
*)

(* The dual versions for \<diamond> *)
lemma DmdImpl:
  assumes prem: "⊨ F ⟶ G"
  shows "⊨ ♢F ⟶ ♢G"
  apply (unfold dmd_def)
  apply (fastforce intro!: prem [temp_use] elim!: STL4E [temp_use])
  done

lemma DmdImplE: "[ sigma ⊨ ♢F; ⊨ F ⟶ G ] ==> sigma ⊨ ♢G"
  by (erule (1) DmdImpl [temp_use])

(* ------------------------ STL5 ------------------------------------------- *)
lemma STL5: "⊨ (◻F ∧ ◻G) = (◻(F ∧ G))"
  apply auto
  apply (subgoal_tac "sigma ⊨ ◻ (G ⟶ (F ∧ G))")
     apply (erule normalT [temp_use])
     apply (fastforce elim!: STL4E [temp_use])+
  done

(* rewrite rule to split conjunctions under boxes *)
lemmas split_box_conj = STL5 [temp_unlift, symmetric]


(* the corresponding elimination rule allows to combine boxes in the hypotheses
   (NB: F and G must have the same type, i.e., both actions or temporals.)
   Use "addSE2" etc. if you want to add this to a claset, otherwise it will loop!
*)
lemma box_conjE:
  assumes "sigma ⊨ ◻F"
     and "sigma ⊨ ◻G"
  and "sigma ⊨ ◻(F∧G) ==> PROP R"
  shows "PROP R"
  by (rule assms STL5 [temp_unlift, THEN iffD1] conjI)+

(* Instances of box_conjE for state predicates, actions, and temporals
   in case the general rule is "too polymorphic".
*)
lemmas box_conjE_temp = box_conjE [where 'a = behavior]
lemmas box_conjE_stp = box_conjE [where 'a = state]
lemmas box_conjE_act = box_conjE [where 'a = "state * state"]

(* Define a tactic that tries to merge all boxes in an antecedent. The definition is
   a bit kludgy in order to simulate "double elim-resolution".
*)

lemma box_thin: "[ sigma ⊨ ◻F; PROP W ] ==> PROP W" .

ML ‹
  merge_box_tac ctxt i =
 REPEAT_DETERM (EVERY [eresolve_tac ctxt @{thms box_conjE} i, assume_tac ctxt i,
 eresolve_tac ctxt @{thms box_thin} i])

  merge_temp_box_tac ctxt i =
 REPEAT_DETERM (EVERY [eresolve_tac ctxt @{thms box_conjE_temp} i, assume_tac ctxt i,
 Rule_Insts.eres_inst_tac ctxt [((("'a", 0), Position.none), "behavior")] [] @{thm box_thin} i])

  merge_stp_box_tac ctxt i =
 REPEAT_DETERM (EVERY [eresolve_tac ctxt @{thms box_conjE_stp} i, assume_tac ctxt i,
 Rule_Insts.eres_inst_tac ctxt [((("'a", 0), Position.none), "state")] [] @{thm box_thin} i])

  merge_act_box_tac ctxt i =
 REPEAT_DETERM (EVERY [eresolve_tac ctxt @{thms box_conjE_act} i, assume_tac ctxt i,
 Rule_Insts.eres_inst_tac ctxt [((("'a", 0), Position.none), "state * state")] [] @{thm box_thin} i])
 ›

method_setup merge_box = ‹Scan.succeed (SIMPLE_METHOD' o merge_box_tac)›
method_setup merge_temp_box = ‹Scan.succeed (SIMPLE_METHOD' o merge_temp_box_tac)›
method_setup merge_stp_box = ‹Scan.succeed (SIMPLE_METHOD' o merge_stp_box_tac)›
method_setup merge_act_box = ‹Scan.succeed (SIMPLE_METHOD' o merge_act_box_tac)›

(* rewrite rule to push universal quantification through box:
      (sigma \<Turnstile> \<box>(\<forall>x. F x)) = (\<forall>x. (sigma \<Turnstile> \<box>F x))
*)
lemmas all_box = [temp_unlift]

lemma DmdOr: "⊨♢F ∧ ♢G ⟶ (♢(F ∧ ♢G)) ∨ (♢(G ∧ ♢F))" and
  apply (auto simp add: dmd_def split_box_conj [try_rewrite])
  apply (erule contrapos_np, merge_box, fastforce elim!: STL4E [temp_use])+
  done

lemma exT: "⊨ (∃x. ♢(F x)) = (♢(∃x. F x))"
  by (auto simp: dmd_def Not_Rex [try_rewrite] all_box [try_rewrite])

lemmas ex_dmd = exT [temp_unlift, symmetric]

lemma STL4Edup: "∧sigma. [ sigma ⊨ ◻A; sigma ⊨ ◻F; ⊨ F ∧ ◻A ⟶ G ] ==> sigma ⊨ ◻G"
  apply (erule dup_boxE)
  apply merge_box
  apply (erule STL4E)
  apply assumption
  done

lemma DmdImpl2:
    "∧sigma. [ sigma ⊨ ♢F; sigma ⊨ ◻(F ⟶ G) ] ==> sigma ⊨ ♢G"
  apply (unfold dmd_def)
  apply auto
  apply (erule notE)
  apply merge_box
  apply (fastforce elim!: STL4E [temp_use])
  done

lemma InfImpl:
  assumes 1: "sigma ⊨ ◻♢F"
    and 2: "sigma ⊨ ◻G"
    and 3: "⊨discT: : "<And>. ⊨ ◻(F ⟶(¬F ∧ ♢ (F ⟶♢
  shows "sigma ⊨ ◻: "And>P F. ⊨<box>(Init P ⟶ ◻F) ⟶ Init P` ⟶ \longrightarrow box(Init P ∧◻ Init F) ⟶ P <longrightarrow F" and
  apply (insert 1 2)
  apply (erule_tac F = G in dup_boxE)
  apply merge_box
  apply (fastforce elim!: S nec: \And F ==> ◻
  done

(* ------------------------ STL6 ------------------------------------------- *)
(* Used in the proof of STL6, but useful in itself. *)
lemma BoxDmd: "<rnstile 
  apply (unfold
  apply clarsimp  ntroAndsigma sigma ⊨ (F::temporal)) ==> F"
  apply (erule dup_boxE)
  apply merge_bx
  apply (erule contrapos_np)
  apply (fastforce elim!: STL4E [temp_use])
  done

(* weaker than BoxDmd, but more polymorphic (and often just right) *)
lemma BoxDmd_simple: "<functionsefined
  apply (unfold dmd_def)val temp_rewriteint_rewrite
  apply clarsimpcase Thmconcl_of of
  applymerge_box
  apply (fastforce elim!: notE STL4E [temp_use])
  done

lemma BoxDmd2_simple: "⊨ ◻> \<diamondG ⟶(G ∧ F)"
  apply( dmd_def
  apply clarsimp
  apply merge_box
  apply (fastforce elim!: notE STL4E [temp_use])
  done

lemma DmdImpldup:
  assumes 1: "sigma ⊨ ◻A"
    and 2: "sigma ⊨ ♢
    and 3: "⊨ ◻A ∧ F ⟶ G"
  shows "sigma ⊨)close
  apply (rule 2 [THEN 1 [THEN BoxDmd [temp_use]], THEN DmdImplE])
  apply (rule 3)
  done

lemma
  apply (auto simp: STL5 [temp_rewrite, symmetric
  apply (drule linT [temp_use]java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
   apply assumption (no_asm: Init_simps
  apply (erule dmdNotInit [ofLIFTF", unfolded Init_simps] for F
  apply (rule DmdDmd [temp_unlift, THEN iffD1])
  apply (erule disjE)
   apply (erule DmdImplE)
   (eDd
  apply (erule DmdIm)
   auto
  apply (d BoxDmd [temp_use])
   apply assumption
  apply (erule thin_rl)
  apply (fastforce elim!: DmdImplE [temp_use])
  done


(* ------------------------ True / False ----------------------------------------- *)
section "Simplification

lemma BoxConst: "⊨
  apply (rule tempI)
  apply (cases P)
   apply (auto intro!: necT [temp_use] dest: do
  done

lemma
  apply (unfold dmd_def)
  apply (cases P)
  apply (simp_all add: BoxConst [try_rewrite])
  done

 temp_simps [temp_re, simp] = BoxConst DDmdC


(* ------------------------ Further rewrites ----------------------------------------- *)
section "Furthersimp)

lemma NotBox \turnstile> \not<boxF) = (<diamondnot
  by:

lemmaturnstile(¬F) = (◻F)"
  by simp add:: dmd_d

(* These are not declared by default, because they could be harmful,
   e.g. ◻
lemmas more_temp_simps1 =
  STL3 [temp_rewri] DmdDmd [temp_r] NotBox [temp_rew] NotDmd [temp_re]
  NotBox [temp_unlift, THEN * dual versions for \>
  NotDmd [temp_unlift, THEN eq_reflection]

lemma BoxDmdBox: "< _
  apply(uto
  apply (rule ccontr\turnstile  \longrightarrow"
  apply (subgoal_tac "sigma ⊨ ♢◻◻ ◻G"
   rule thi_rl
   apply auto
    apply (drule STL6 [temp_use])
     apply assumptio
    apply simp
   apply (simp_al STL4_gen: "turnstileInit F ⟶ G <><> G"
  done

lemma
  apply (unfold dmd_def)
  apply (auto simp: BoxDmdBox [unfolded dmd_def, try_rewrite])
  done

lemmas more_t---------


(* ------------------------ Miscellaneous ----------------------------------- *)assumes pm:"<> F \G"

lemma BoxOr: "<nd<brakksigma ⊨ ◻or> ◻] ==> sigma ⊨ ◻ G)"
  by (fastforce elim!: STL4E [emp_use])

(* "persistently implies infinitely often" *)
lemma DBImplBD: "⊨ ♢◻F ⟶ ◻♢F"
  apply clarsimp
  apply (rule ccontr)
  apply (simp add:: more)
  apply (drule STL6a (sub "sigmaTurnstile◻ (G ⟶ G))")
   apply assumption
  apply simp
  done

lemma BoxDmdDmdBox: "⊨
  apply clarsimp
  apply (rule ccontr)
  apply (unfold more_temp_simps2)
  apply (drule STL6 [temp_use])
   apply assumption
  apply (subgoal_tac "sigma ⊨ ♢◻to aclaset, othe it will !
   apply (force simp: dmd_def)
  apply (fastforce elim: DmdImplE [temp_use] STL4E [temp_use])
  done


(* ------------------------------------------------------------------------- *)
(***          TLA-specific theorems: primed formulas                       ***)
(* ------------------------------------------------------------------------- *)
section "priming"

(* ------------------------ TLA2 ------------------------------------------- *)
lemma STL2_pr: "⊨ ◻P ⟶ Init P ∧ Init P`"
  by (fastforce intro!: STL2_gen [temp_use] primeI [temp_use])

(* Auxiliary lemma allows priming of boxed actions *)
lemma BoxPrime: "⊨ ◻P ⟶ ◻($P ∧ P$)"
  apply clarsimp
  apply (erule dup_boxE)
  apply (unfold boxI boxInit_t)
   (erule STL4E)
  apply (auto simp: Init_simps dest!: STL2_[emp_se])
  done

lemma TLA2:
  assumes "⊨ $P ∧ P$ ⟶ A"
  shows "⊨ ◻P ⟶ ◻
  apply clarsimp
  apply (drule BoxPrime [temp_use] box_conjE_act where " * state"
  apply (auto simp: Init_stp_act_rev [try_rewrite] intro!: assms [temp_use]
    elim!: STL4E [temp_use])
  done

lemma TLA2E: "[ sigma ⊨ ◻
  by (erule (1) TLA2 [temp_use])

lemma DmdPrime: "⊨ (♢P`) ⟶ (♢
  apply (unfold dmd_defe_tac ume_tac
  apply (fastforce elim
  done

lemmas PrimeDmd = InitDmd_gen [temp_use

(* ------------------------ INV1, stable --------------------------------------- *)
section "stable, invariant"

lemma ind_rule:
   java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
    \<Longrightarrowct_boxScan.succeed (SIMPLE_METHOD' o merge_act_box_tac)›
(
   E)
  done

:"turnstile(◻$P) = (◻
  byDmdOr> (♢(F <or)  java.lang.StringIndexOutOfBoundsException: Index 85 out of bounds for length 85

lemmas box_stp_actI =by mp_fot_Rexy_rewrite
lemmas

lemmasapply  dup_boxE

lemma INV1:
  "⊨ (Init P) ⟶ (stable P) \<longrightarrowlemma
  apply (unfold stable_def boxInit_stp boxInit_act)
  apply clarsimp
  apply (erule ind_rule)
   uto
  done

java.lang.StringIndexOutOfBoundsException: Index 6 out of bounds for length 6
"<And>P. ⊨ $P ∧ A ⟶ P` ==> ⊨ ◻A ⟶ stable P"
  apply (unfold stabl)
  apply (fastforce elim!: STL4E [temp_use])
  done

emmable \> ◻ $P ∧` \rbrakk> sigma ⊨
  by (erule (1) StableT [tedu)

(* Generalization of INV1 *)
lemma StableBox: "⊨
  apply (unfold stable_def)
  apply clarsimp
  apply (erule dup_boxE)
  apply (force simpapply (unfold)
  done

lemmaerule)
  apply clarsimp
  apply (rule DmdImpl2)
   prefer
   apply (erule StableBox [temp_use])
  apply (simpInitD)
  done

(* ---------------- (Semi-)automatic invariant tactics ---------------------- *)

ML java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
(* inv_tac reduces goals of the form ... \<Longrightarrow> sigma \<Turnstile> \<box>P *)
fun inv_tac ctxt =
  SELECT_GOAL
    (EVERY
     [auto_tac ctxt,
      TRY
      resolve_tac ctxt [temp_use ctxt @{thm INV1}] 1, (* fail if the goal is not a box *)
      TRYALL (eresolve_tac ctxt lemmaDmdImpldup

(* auto_inv_tac applies inv_tac and then tries to attack the subgoals
   in simple cases it may be able to handle goals like \<turnstile> MyProg \<longrightarrow> \<box>Inv.
   In these simple cases the simplifier seems to be more useful than the
   auto-tactic, which applies too much propositional logic and simplifies
   toolate.
*)
funauto_inv_tac ctxt =
  SELECT_GOAL
    (inv_tac STL6: \turnstile ♢F <d<<longrightarrow> ♢<and
      (TRYALL (action_simp_tac
        @{thm Init_stp}, @thm Init_act [{thm squareE;
›

method_setup invariant = ‹
  Method.sections Clasimpapply rule DmdDmd [temp_unlift THEN iffD1
\<close>

method_setup auto_invariant = \<open>
  Method.sections Clasimp.clasimp_modifiers > (K SIMPLE_METHOD' o auto_inv_tac)
\<close>

lemma unless: "\<turnstile> \<box>($P \<longrightarrow> P  Q`) \<longrightarrow> (stable P) \or\<diamond>Q"
  apply ewrites
  apply (clarsimp dest!: BoxPrime [temp_use])
  apply merge_box
  apply (erule contrapos_np)
  apply (fastforce elim!: Stable [temp_use])
  done


(* --------------------- Recursive expansions --------------------------------------- *)
section "recursive expansions"

(* Recursive expansions of \<box> and \<diamond> for state predicates *)
lemma BoxRec: "⊨] DmdD[temp_rewrite] ] NootBox [temp_rewrit] NotDmd [temp_rewri]
  apply (auto intro!: STL2_gen [temp_use])
e])
  apply (auto simp: stable_def elim!: INV1 [temp_use] STL4E [temp_use])
  done

lemma DmdRec: "⊨
  apply (unfold BoxRec])
  apply (auto simp: Init_simps)
  done

lemma
  apply (force simp: DmdRec [temp_rewrite] dmd_deflemmaDmdBoxDmd: "\diamond<box>♢F) = (◻F)"
  done

lemma: "\>box>\diamond>P) = (◻♢P`)"
  apply auto
   apply (rule classical)
   apply (rule DBImplBD [temp_use])
   apply (subgoal_tac(* ------------------------ Miscellaneous ----------------------------------- *)
    apply (fastforce elim!: DmdImplE[emp_use
   apply (subgoal_tac "sigma ⊨
    apply (fosimp: boxInit_stp [temp_
      elim!: DmdImplE [temp_use] STL4E [temp_use] DmdRec2 [temp_use])
   apply (force intro!: STL6 [temp_use] simp: more_temp_simps3)
  apply (fastforce intro: DmdPrime [temp_use] elim!: STL4E [temp_use])
  done

lemma InfiniteEnsure:
  "[
  apply (unfold InfinitePrime [temp_rewrite])
  apply (rule InfImpl)
    apply assumption+
  done

(* ------------------------ fairness ------------------------------------------- *)
section "fairness"

(* alternative definitions of fairness *)
lemma WF_alt: "⊨
  apply (unfold WF_def dmd_def)
  apply fastforce
  done

lemma SF_alt: "⊨
  apply (unfold SF_def dmd_def)
  apply fastforce
  done

(* theorems to "box" fairness conditions *)
lemma BoxWFI: "⊨ WF(A)_v ⟶ ◻WF(A)_v"
  by (auto simp: WF_alt [try_rewrite] more_temp_simps3 intro!: BoxOr [temp_use])

lemma WF_Box: "⊨ (◻WF(A)_v) = WF(A)_v"
  by (fastforce intro!: BoxWFI [temp_use] dest!: STL2 [temp_use])

lemma BoxSFI: "⊨
  STL4E)

lemma SF_Box: "java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
  by (fastforce introapply java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 16

lemmas more_temp_simps=more_temp_simps3WF_Box] SF_Boxtemp_rewrite

lemmaSFImplWF: "\urnstile WF(A)_v"
  apply (unfold SF_def WF_def)
  apply (fastforce
  done

(* A tactic that "boxes" all fairness conditions. Apply more_temp_simps to "unbox". *) elim [])
ML <open 
fun box_fair_tac
  SELECT_GOAL
›


(* ------------------------------ leads-to ------------------------------ *)(e)

section "↝

lemma leadsto_init: "<turnstile  \>G) ⟶ ♢G"
  apply (unfold leadsto_def)
  apply (auto dest!: STL2 [temp_use])
  done

(* \<turnstile> F & (F \<leadsto> G) \<longrightarrow> \<diamond>G *)
lemmas leadsto_init_temp = leal

lemma : "\turnstile<box<diamond>Init F ⟶ <box\(F <leadsto 
 ly
  apply auto
    apply (simp add: more_temp_simps
    apply (fastforce elim!: DmdImplE [temp_use] STL4E [temp_use])
   apply (fastforce intro!: InitDmd [temp_use] elim!: STL4E [temp_use])
  apply (subgoal_tac "sigma ⊨
   apply (simp add: more_temp_simps)
   (drule BoxDmdDmdBox [temp_use])
   apply assumption
  apply (fastforce elim!: DmdImplE [temse])
  done

lemma leadsto_infinite: "<> <diamondF (F ↝ box>♢
  apply clarsimp
  apply (erule InitDmd
  apply (simp add: dmdInitD)
  done

(* In particular, strong fairness is a Streett condition. The following 
   rules are sometimes easier to use than WF2 or   apply force: stable_def elim: STL4E [temp_use] INV1 temp_usejava.lang.StringIndexOutOfBoundsException: Index 71 out of bounds for length 71
*)
lemma leadsto_SF: java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
   ctxt [t ctxt @{thm INV1] 1,(* if the goal is not a box *)
  apply (clarsimp elim!: leadsto_infinite [temp_use])
  done

lemma leadsto_WF: "⊨ (Enabled(<A>_v) ↝ <A>_v) ⟶ WF(A)_v"
  by (clarsimp intro!: SFImplWF [temp_use] leadsto_SF [temp_use])

(* introduce an invariant into the proof of a leadsto assertion.
   <> ((P \>I\leadsto
*)
lemma INV_leadsto: "⊨ ◻I ∧ (P ∧ I ↝ Q) ⟶ (P ↝ Q)"
  apply (unfold leadsto_def)
  apply clarsimp
  apply (erule STL4Edup)
   apply assumption
  apply (auto simp: Init_simps dest!: STL2_gen [temp_use])
  done

lemma leadsto_classical: "java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
  apply (unfold leadsto_defdmd_def
  apply (force simp: Init_simps elim!: STL4E [temp_use])
  done

lemma leadsto_false>
  apply (unfold leadsto_def)
  apply (simp add: boxNotInitD)
  done

lemma leadsto_exists: "⊨ ((∃x. F x) ↝
  apply (unfold leadsto_def)
  apply (auto simp: allT [try_rewrite] Init_simps elim!: STL4E [temp_use])
  

(* basic leadsto properties, cf. Unity *)

lemma ImplLeadsto_gen: "⊨ ◻(Init F ⟶ Init G) ⟶ (F ↝ G)"
  apply (unfold leadsto_def)
  apply (auto intro!: InitDmd_gen [temp_use]
    elim!: STL4E_gen [temp_use] simp: Init_simps)
  done

lemmas ImplLeadsto =
  ImplLeadsto_gen [where 'a = bd

lemma ImplLeadsto_simple: "java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
yimpuse

lemma EnsuresLeadsto: astforcese
  assumessimpV14temp_use
  shows 
  apply (unfold leadsto_def
  apply (clarsimp (unfold dmd_def [temp_rewrite
  apply (erule STL4E_gen)
  apply
  done

lemma EnsuresLeadsto2
  apply (unfold
  pplyclarsimp
  apply (erule STL4E_gen)
  apply (auto simp: Init_simps intro!: PrimeDmd [temp_use])
  done

lemma ensures:
  assumes 1: "⊨ $P ∧ N ⟶ P` ∨ Q`"
    andrule)
  shows \turnstile> <>N ∧(◻ ♢ (P ↝
  apply (unfold leadsto_defsubgoal_tac "sigma ⊨◻
  apply clarsimp
 apply (eru STL4Edup)
   apply assumption
  apply clarsimp
  apply (subgoal_tac "sigmaa ⊨ ◻($P ⟶ P` ∨ Q`) ")
   apply (drule unless [temp_use])
   apply (clarsimp dest!: INV1 [temp_use])
  apply (rule 2 [THEN DmdImpl, temp_use, THEN DmdPrime [temp_use]])
   apply (f intro!: BoxDmd_simple [temp_use]
     simp: split_box_conj [try_rewrite] box_s lim!: mdImplE [temp_] STL4E [temp_] DmdRec2 [temp_use])
  apply (force el STL4E [temp_use] dest: 1 [temp_use])
  done

lemma ensures_simple:
  "[ $P ∧ P` ∨
      ⊨ldp_rewrite
   ] ==>apply assumption
  apply clarsimp
  apply (erule (2) ensures [temp_use])
  apply (force elim!: STL4E [temp_usesectionfairness"
  done

lemmaEnsuresInfinite:
    "[ sigma ⊨♢ ◻turnstile A ∧ Longrightarrow sigma ⊨♢
  apply (erule leadsto_infinite [temp_use])
  apply (erule EnsuresLeadstoapply(unfold WF_def dmd_def
  n
  done


(*** Gronning's lattice rules (taken from TLP) ***)
section "Lattice rules"

lemma LatticeReflexivity: "⊨ WF(A)_v ⟶ \box
  apply(unfold leadsto_def)
  apply (rule necT InitDmd_gen)+
  done

lemmaiceTransitivity <> (G \<>  (F \<> 
  apply (unfold leadsto_def)
  apply clarsimp
  apply (erule dup_boxE) (* \>(Init G ⟶

  apply (clarsimp elim!: STL4E [temp_use])
  e_mD
  apply (subgoal_tac "sigmaa ⊨mp_use
   applye_temp_simps3F_Box
   apply assumptionturnstile SF(A)_v <longrightarrow 
  applyst
  done

lemma LatticeDisjunctionElim1: "⊨ (F ∨
  apply (unfold leadsto_def)
  apply (auto simp: Init_simps elim!: STL4E [temp_use])
  done

lemma LatticeDisjunctionElim2: "⊨
  apply (unfold
   simpe
  done

lemma LatticeDisjunctionIntro: "⊨
  apply (unfold leadsto_def)
  apply clarsimp
  apply merge_box
  apply (auto simp: Init_simps elim!: STL4E [temp_use])
  done

lemma LatticeDisjunction: "⊨
  by (auto introsigmaTurnstile ◻♢
    LatticeDisjunctionElim1 [temp_use]
    LatticeDisjunctionElim2

lemma LatticeDiamond
  apply clarsimp
  apply (subgoal_tac "sigma ⊨ InitD [temp_use, THEN stree [temp_unlift, THEN iffD2, THEN mp]])
  apply (erule_tac G = "LIFT (B ∨
   apply (fastforce intro!: LatticeDisjunctionIntro [temp_use])+
  done

lemma LatticeTriangle: "⊨
  applycasmp
  apply (subgoal_tac "sigma ⊨applyld
   apply msto_infinitemp_use]
  apply assumption
  apply (auto leadsto_WFturnstile (Enabled(<A>_v) ↝ <A>_v) ⟶A)"
  done

lemma LatticeTriangle2: "⊨ (A \   <boxI ⟶ Q)  =  (P /\ I <leadsto)
  apply clarsimp
  apply (subgoal_tac "sigma \apply leadsto_def)
   apply (erule_tac G = "LIFT (B ∨
   apply assumption
  apply leadsto_classical<> (nit ◻G \leadsto\longrightarrowleadstoG)"
  done

(*** Lamport's fairness rules ***)
section "Fairness rules"

lemma WF1:
  "[ leadsto_def
      ⊨
      ⊨<turnstile(<exists>G) = (∀ G))"
  ==>(nodlatodf
  apply (clarsimp dest!: BoxWFI [temp_use])
  apply (erule (2) ensures [temp_use])
  apply (erule (1) STL4Edup)
  apply (clarsimp simp: WF_def)
java.lang.StringIndexOutOfBoundsException: Index 42 out of bounds for length 30
  apply (clarsimp elim!: mp intro!: InitDmd [temp_use])
  apply (erule STL4 [temp_use, THEN box_stp_actD [temp_use]])
  apply (simp add: split_box_conj box_stp_actI)
  done

(* Sometimes easier to use; designed for action B rather than state predicate Q *)
lemma WF_leadsto:
  assumes 1: "⊨:STL4E_gen] simp)
    and 2
    and 3: "⊨ [where 'a= eha and 'b = behavi, unfolded Init_simps
  shows lemmImplLeadsto_simple: "<>F G <>  G"
  apply (unfold leadsto_def)
  apply (clar by ((auto simp: InInit_de intro!: ImplLeadsto_gen [temp] necT [temp_use])
  apply (erule (1) STL4Edup)
  apply clarsimp
  apply rue TH mdm,teue)
  apply (rule BoxDmd_simple [temp_use])
   apply assumption
  yrlcascl
yruleS2tmue]
  apply (clarsimp simp: WF_def elim!: mp intro!: InitDmd [temp_use])
  apply (rule 1 [THEN STL4, temp_use, THEN box_stp_actD])
  apply (simp (no_asm_simp) add: split_box_conj [try_rewrite] box_stp_act [try_rewrite])
   (erule INV1 [temp_use])
  apply (rule 3 [temp_use])
  apply (simp add: split_box_conj [try_rewrite] NotDmd [temp_use] not_angle [try_rewrite])
  done

lemma SF1:
  "[
      ⊨ N)<> <A>_v ⟶
      ⊨P ∧N ∧F ⟶Enabled)java.lang.StringIndexOutOfBoundsException: Index 109 out of bounds for length 109
  ==> ⊨ ◻N ∧ SF(A)_v ∧ ◻
  apply assumption
  apply (erule (2) ensures [temp_use])
  apply (erule_tac F = F inE
  apply merge_temp_box
  apply (erule STL4Edup)
  apply assumption
  apply (clarsimp simpimple
  apply (rule STL2 [temp_use])
  apply (erule mp)
  apply (erule STL4 [temp_use])
  apply (simp add: split_box_conj [try_rewrite] STL3 [try_rewrite])
  done

lemma WF2:
  assumes lemmaensures_simple
    and 2: "\<> 
    and 3: "<turnstile )<longrightarrow Enabled(<A>"
    and 4: "⊨ ==> ◻♢ P<>Q)"
  shows "⊨
  apply (clarsimp dest!: BoxWFI [temp_use] BoxDmdBox [temp_use  done
    simp: WF_def [where A = M])
  apply (erule_tac"\lbrakk sigma \<Turnstile ♢T> ◻A; ⊨ A ∧ $P ⟶ Q` ] ==> sigma ⊨ ◻♢Q"
  apply merge_temp_box
  apply (erule STL4Edup)
   apply assumption
  apply (clarsimp  apply(erule
  apply (rule classical)
  apply (subgoal_tac "sigmaa ⊨
   apply (force simp: angle_def int(
  apply (rule BoxDm [THEN DmdImpl, unfolded Dmd [temp_rewrite, temp_use])
  apply (simp add: NotDmd [temp_use] not_angle [try_rewrite])
  apply merge_act_box
  apply (rule 4 4 [temp_us])
     apply assumption+
  apply (drule STL6 [temp_use])
   apply assumption
  apply (erule_tac V = "sigmaa: "\G H) ∧ (F ↝ (F ↝
  apply (erule_tac V = "sigmaa \arsimp
  applyxWFI
  apply (erule_tacox
  apply merge_temp_box
  apply (erule DmdImpldupac ⊨Init"
   apply assumption
  apply (auto simp: split_box_conj [try_rewrite] STL3 [try_rewrite]
    WF_Box [try_rewrite] box_stp_act [try_rewrite])
   apply (force elim!: TLA2E [where P = P, temp_use])
  apply (rule STL2 [temp_use])
  apply (force simp: WF_def split_box_conj [ simp: Ini
    elim!: mp intro!: InitDmd [temp_use LatticeDisjunctionElim2: " G <>)
  done

lemmajava.lang.StringIndexOutOfBoundsException: Index 6 out of bounds for length 6
  assumes : "\ N ∧"
    and 2: "⊨ $P ∧ P` ∧ <N ∧
    and 3: "⊨: Init_simps!: STL4Etemp_use
    and 4: "⊨
  shows "⊨N ∧ ◻ SF(java.lang.StringIndexOutOfBoundsException: Index 86 out of bounds for length 86
  apply larsimpesimprewrite]F_def
  apply (erule_tac F = F in dup_boxE)
  apply (erule_tac F = "TEMP ♢ C)" in LatticeTransitivity [temp_use])
   merge_temp_box
  apply (erule STL4Edup)
   apply assumption
  apply (clarsimp intro LatticeTriangle "\turnstile(A ↝ D ∨ B) ∧ D) ⟶ D)"
   e
  apply (subgoal_tac "sigmaa ⊨ B)" in LatticeTransitivitytemp_use
   apply (force simp:  apply assumption
  applyrule THEN, unfolded [temp_rewrite])
  apply (simp add: 
  apply merge_act_box
  applyule
     apply assumption+
  applyerule_tac  Turnstile>" in thin_rl)
  apply (drule _tc = " (B \orD)" in LatticeTransitivity [temp_use])
  apply (erule_tac F = "TEMP ♢Enabled assumption
  apply(rule_tac F = "ACT N \and[¬B]_f" in dup_boxE)
  apply 
  apply (erule DmdImpldup)
   apply assumption
  apply (auto simp:lemmaWF1
    Boxwrite
   apply\turnstile> ($P 🪙
  apply STL2
  apply (force simp: SF_def split_box_conj [try_rewrite]
    elim!: mp InfImpl temp_usemp_use
  done

(* ------------------------------------------------------------------------- *)
(***           Liveness proofs by well-founded orderings                   ***)
(* ------------------------------------------------------------------------- *)
section "Well-founded orderings"

lemma wf_leadsto:
  assumes 1: "wf r"
    and 2: "∧
  shows "sigma ⊨
  apply (rule 1 [THEN wf_induct])
  apply (ruleLatticeTriangle [temp_use]
   apply ( 2)
  apply (auto simpexists
  apply (case_tac "(y,x) ∈ r")
   apply force
  apply (force simp: leadsto_def Init_simps intro!: necT  apply(nfold)
  done

(* If r is well-founded, state function v cannot decrease forever *)
lemma wf_not_box_decreaseapplyrule [])
  apply clarsimp
  apply (rule ccontr)
  apply (subgoal_tac "sigma ⊨
   apply (rule leadsto_false [temp_use, THEN iffD1 THENSTL2_gen [temp_use]])
   apply (force simp: Init_defs)
  apply (clarsimp simp: leadsto_exists [try_rewrite]] ot_square [try] more_temp_simps)
  apply (erule wf_leadsto)
  apply (rule ensures_simple [temp_use])
   apply (auto simp: square_def angle_def)
  done

(* "wf r  \<Longrightarrow>  \<turnstile> \<diamond>\<box>[ (v`, $v) : #r ]_v \<longrightarrow> \<diamond>\<box>[#False]_v" *)
lemmas wf_not_dmd_box_decrease =
  wf_not_box_decrease [THEN DmdImpl, unfunfolded more_temp_simps]

(* If there are infinitely many steps where v decreases, then there
   have to be infinitely many non-stuttering steps where v doesn't decrease.
*)
lemma wf_box_dmd_decrease:
  assumes 1: "wf r"
  shows "<turnstile><diamond(v`, $v) ∈ #r) ⟶ ◻<(v`, $v) ∉
  applyclarsimp
  apply (rule ccontr)
  apply (simp add: not_angle [try_rewrite] more_temp_simps)
  apply (drule 1 [THEN wf_not_dmd_box_decrease [temp_use]])
  apply (drule BoxDmdDmdBox [apply ( F = F  dup_boxE
   apply assumption
  apply (subgoal_tac "sigma ⊨
   applyf
  apply(eule STL4)
  apply (rule DmdImpl)
  apply (force intro: 1 [THEN wf_irrefl, temp_use])
  done

(* In particular, for natural numbers, if n decreases infinitely often
   then it has to increase infinitely often.
*)
lemma nat_ and 2: "<turnstile P\and> `\and><N \and>Af\longrightarrow> B"
  apply clarsimp
  apply (subgoal_tac "sigma ⊨ ◻<>B]_f<>WF◻ ♢Pjava.lang.StringIndexOutOfBoundsException: Index 158 out of bounds for length 158
   apply (en_rl
   apply (erule STL4E)
   apply (rule DmdImpl)
   apply (clarsimp simp: angle_def [try_rewrite])
  apply (rule wf_box_dmd_decrease [temp_use])
   apply (auto elim!: STL4E [temp_use] DmdImplE [temp_use])
  applyprolepl


(* ------------------------------------------------------------------------- *)
(***           Flexible quantification over state variables                ***)
(* ------------------------------------------------------------------------- *)
section (simp add [temp_use not_angle [try_rewrite

lemma aallI:
  assumes 1: "basevars vs"
    and 2: "(∧x. basevars (x,vs) ==> sigma ⊨ apassumpt
  wsssigma \Turnstile∀
  by (auto simp: aall_def elim!: eexE [temp_use] intro!: 1 dest!: 2 [temp_use])

lemma: "\turnstile <orall<forall>x. F x) ⟶ F x"
  apply (unfold aall_def)
  apply clarsimp
  apply (erule contrapos_np)
  apply (force intro!: eexI [temp_use])
  done

(* monotonicity of quantification *)
lemma eex_mono:
  es1"⊨∃
    and 2: "∧
  shows "sigma ⊨<existsx
  apply (_eEN
  apply (rule eexI [temp_useandturnstileP ∧ Enabled(<M>_g) java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
   (erule [unfoldedintensional_rewsTHENmp)
  done

lemma
  assumes 1: "sigma ⊨_[ee =M)
    and 2: "∧>Enabled (<M>_g) " in dup_boxE)
  shows "sigma ⊨
  apply (rule (clarsimp intro [temp_use, THEN 1[ DmdImpl]])
  apply (rule classical
  apply (ule 1 [THEN aallE [temp_use]])
  done

(* Derived history introduction rule *)
lemma historyI:
  assumes 1: "sigma ⊨
     2: " <> 
    basevars
    and 4: "∧h. basevars(h,vs) ==>
    and 5: "∧ ⊨F" in thin_rl)
  shows "sigma ⊨   apply F ="EMP\diamondd)
  apply (rule history [temp_use, THEN eexE])
  apply (rule 3)
  apply (rule eexI [temp_use])
  apply clarsimp
   ruecnI
   prefer 2
   apply (insert 2)
   apply merge_box
   apply (force elim!: STL4E [temp_use] 5 [temp_use])
  apply (insert 1)
  apply (force simp: Init_defs elim!: 4 [temp_use])
  done

(* ----------------------------------------------------------------------
   example of a history variable: existence of a clock
*)

lemma "⊨ ∃ r
  apply (rule)
  apply (rule "sigma \Turnstile <ead G"
  apply (force simp: Init_defs intro!: unit_base [temp_use] necT [temp_use])+
  done

end