diff --git a/thys/CSP_RefTK/Assertions_ext.thy b/thys/CSP_RefTK/Assertions_ext.thy deleted file mode 100644 --- a/thys/CSP_RefTK/Assertions_ext.thy +++ /dev/null @@ -1,818 +0,0 @@ -(*<*) -\\ ******************************************************************** - * Project : CSP-RefTK - A Refinement Toolkit for HOL-CSP - * Version : 1.0 - * - * Author : Burkhart Wolff, Safouan Taha, Lina Ye. - * - * This file : Assertions on DF and LF and their Relations - * - * Copyright (c) 2020 Université Paris-Saclay, France - * - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following - * disclaimer in the documentation and/or other materials provided - * with the distribution. - * - * * Neither the name of the copyright holders nor the names of its - * contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - ******************************************************************************\ -(*>*) - -chapter\Basic CSP\_RefTk-Theories\ - -theory Assertions_ext - imports "HOL-CSP.Assertions" -begin - -section \Preliminaries\ - -lemma DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold : "DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A = ((\ z \ A \ DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) \ SKIP)" - by(simp add: DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def, rule trans, rule fix_eq, simp) - -section \All refinements definitions\ - -thm failure_divergence_refine_def[simplified le_ref_def] trace_refine_def failure_refine_def - -definition divergence_refine :: "'a process \ 'a process \ bool" (infix "\\<^sub>D" 60) - where "P \\<^sub>D Q \ D Q \ D P" - -definition trace_divergence_refine :: "'a process \ 'a process \ bool" (infix "\\<^sub>D\<^sub>T" 60) - where "P \\<^sub>D\<^sub>T Q \ P \\<^sub>T Q \ P \\<^sub>D Q" - -section \Relations between refinements\ - -lemma le_F_T: "P \\<^sub>F Q \ P \\<^sub>T Q" - by (simp add: F_subset_imp_T_subset failure_refine_def trace_refine_def) - -lemma FD_F: "P \\<^sub>F\<^sub>D Q \ P \\<^sub>F Q" - by (simp add: failure_divergence_refine_def failure_refine_def le_ref_def) - -lemma FD_D: "P \\<^sub>F\<^sub>D Q \ P \\<^sub>D Q" - by (simp add: divergence_refine_def failure_divergence_refine_def le_ref_def) - -lemma DT_D: "P \\<^sub>D\<^sub>T Q \ P \\<^sub>D Q" - by (simp add: trace_divergence_refine_def) - -lemma DT_T: "P \\<^sub>D\<^sub>T Q \ P \\<^sub>T Q" - by (simp add: trace_divergence_refine_def) - -lemma F_D_FD:"P \\<^sub>F Q \ P \\<^sub>D Q \ P \\<^sub>F\<^sub>D Q" - by (simp add: divergence_refine_def failure_divergence_refine_def failure_refine_def le_ref_def) - -lemma D_T_DT:"P \\<^sub>D Q \ P \\<^sub>T Q \ P \\<^sub>D\<^sub>T Q" - by (simp add: trace_divergence_refine_def) - -section \Some obvious refinements\ - -lemma bot_FD[simp]: "\ \\<^sub>F\<^sub>D Q" - by (simp add: failure_divergence_refine_def) - -corollary bot_F[simp]: "\ \\<^sub>F Q" - and bot_D[simp]: "\ \\<^sub>D Q" - and bot_T[simp]: "\ \\<^sub>T Q" - and bot_DT[simp]: "\ \\<^sub>D\<^sub>T Q" - by (simp_all add: FD_F FD_D le_F_T D_T_DT) - -lemma STOP_leDT[simp]: "P \\<^sub>D\<^sub>T STOP" - by (simp add: D_STOP D_T_DT Nil_elem_T T_STOP divergence_refine_def trace_refine_def) - -\\For refinement proofs, we need admissibility and monotony starting with idempotency and - transitivity\ - -section \Idempotency\ - -lemma idem_F[simp]: "P \\<^sub>F P" - by (simp add: failure_refine_def) - -lemma idem_D[simp]: "P \\<^sub>D P" - by (simp add: divergence_refine_def) - -lemma idem_T[simp]: "P \\<^sub>T P" - by (simp add: trace_refine_def) - -lemma idem_FD[simp]: "P \\<^sub>F\<^sub>D P" - by (simp add: failure_divergence_refine_def) - -lemma idem_DT[simp]: "P \\<^sub>D\<^sub>T P" - by (simp add: trace_divergence_refine_def) - -section \Transitivity\ - -lemma trans_F: "P \\<^sub>F Q \ Q \\<^sub>F S \ P \\<^sub>F S" - by (meson failure_refine_def order_trans) - -lemma trans_D: "P \\<^sub>D Q \ Q \\<^sub>D S \ P \\<^sub>D S" - by (meson divergence_refine_def order_trans) - -lemma trans_T: "P \\<^sub>T Q \ Q \\<^sub>T S \ P \\<^sub>T S" - by (meson trace_refine_def order_trans) - -lemma trans_FD: "P \\<^sub>F\<^sub>D Q \ Q \\<^sub>F\<^sub>D S \ P \\<^sub>F\<^sub>D S" - by (meson failure_divergence_refine_def order_trans) - -lemma trans_DT: "P \\<^sub>D\<^sub>T Q \ Q \\<^sub>D\<^sub>T S \ P \\<^sub>D\<^sub>T S" - by (meson trace_divergence_refine_def order_trans trans_D trans_T) - -section \Admissibility\ - -lemma le_F_adm: "cont (u::('a::cpo) \ 'b process) \ monofun v \ adm(\x. u x \\<^sub>F v x)" -proof(auto simp add:cont2contlubE adm_def failure_refine_def) - fix Y a b - assume 1:"cont u" - and 2:"monofun v" - and 3:"chain Y" - and 4:"\i. F (v (Y i)) \ F (u (Y i))" - and 5:" (a, b) \ F (v (\x. Y x))" - hence "v (Y i) \ v (\i. Y i)" for i by (simp add: is_ub_thelub monofunE) - hence "F (v (\i. Y i)) \ F (u (Y i))" for i using 4 le_approx_lemma_F by blast - then show "(a, b) \ F (\i. u (Y i))" - using F_LUB[OF ch2ch_cont[OF 1 3]] limproc_is_thelub[OF ch2ch_cont[OF 1 3]] 5 by force -qed - -lemma le_T_adm: "cont (u::('a::cpo) \ 'b process) \ monofun v \ adm(\x. u x \\<^sub>T v x)" -proof(auto simp add:cont2contlubE adm_def trace_refine_def) - fix Y x - assume 1:"cont u" - and 2:"monofun v" - and 3:"chain Y" - and 4:"\i. T (v (Y i)) \ T (u (Y i))" - and 5:" x \ T (v (\i. Y i))" - hence "v (Y i) \ v (\i. Y i)" for i by (simp add: is_ub_thelub monofunE) - hence "T (v (\i. Y i)) \ T (u (Y i))" for i using 4 le_approx_lemma_T by blast - then show "x \ T (\i. u (Y i))" - using T_LUB[OF ch2ch_cont[OF 1 3]] limproc_is_thelub[OF ch2ch_cont[OF 1 3]] 5 by force -qed - -lemma le_D_adm: "cont (u::('a::cpo) \ 'b process) \ monofun v \ adm(\x. u x \\<^sub>D v x)" -proof(auto simp add:cont2contlubE adm_def divergence_refine_def) - fix Y x - assume 1:"cont u" - and 2:"monofun v" - and 3:"chain Y" - and 4:"\i. D (v (Y i)) \ D (u (Y i))" - and 5:" x \ D (v (\i. Y i))" - hence "v (Y i) \ v (\i. Y i)" for i by (simp add: is_ub_thelub monofunE) - hence "D (v (\i. Y i)) \ D (u (Y i))" for i using 4 le_approx1 by blast - then show "x \ D (\i. u (Y i))" - using D_LUB[OF ch2ch_cont[OF 1 3]] limproc_is_thelub[OF ch2ch_cont[OF 1 3]] 5 by force -qed - -lemma le_DT_adm: "cont (u::('a::cpo) \ 'b process) \ monofun v \ adm(\x. u x \\<^sub>D\<^sub>T v x)" - using adm_conj[OF le_T_adm[of u v] le_D_adm[of u v]] by (simp add:trace_divergence_refine_def) - -lemmas le_FD_adm = le_adm[simplified failure_divergence_refine_def[symmetric]] - -section \Monotonicity\ - -lemma mono_det_D[simp]: "\P \\<^sub>D P'; S \\<^sub>D S'\ \ (P \ S) \\<^sub>D (P' \ S')" - by (metis D_det Un_mono divergence_refine_def) - -lemma mono_det_T[simp]: "\P \\<^sub>T P'; S \\<^sub>T S'\ \ (P \ S) \\<^sub>T (P' \ S')" - by (metis T_det Un_mono trace_refine_def) - -corollary mono_det_DT[simp]: "\P \\<^sub>D\<^sub>T P'; S \\<^sub>D\<^sub>T S'\ \ (P \ S) \\<^sub>D\<^sub>T (P' \ S')" - by (simp_all add: trace_divergence_refine_def) - -lemmas mono_det_FD[simp]= mono_det_FD[simplified failure_divergence_refine_def[symmetric]] - -\\Deterministic choice monotony doesn't hold for \\\<^sub>F\\ - - -lemma mono_ndet_F[simp]: "\P \\<^sub>F P'; S \\<^sub>F S'\ \ (P \ S) \\<^sub>F (P' \ S')" - by (metis F_ndet Un_mono failure_refine_def) - -lemma mono_ndet_D[simp]: "\P \\<^sub>D P'; S \\<^sub>D S'\ \ (P \ S) \\<^sub>D (P' \ S')" - by (metis D_ndet Un_mono divergence_refine_def) - -lemma mono_ndet_T[simp]: "\P \\<^sub>T P'; S \\<^sub>T S'\ \ (P \ S) \\<^sub>T (P' \ S')" - by (metis T_ndet Un_mono trace_refine_def) - -corollary mono_ndet_DT[simp]: "\P \\<^sub>D\<^sub>T P'; S \\<^sub>D\<^sub>T S'\ \ (P \ S) \\<^sub>D\<^sub>T (P' \ S')" - by (auto simp add: trace_divergence_refine_def) - -lemmas mono_ndet_FD[simp]= - mono_ndet_FD[simplified failure_divergence_refine_def[symmetric]] - -lemma mono_ndet_F_left[simp]: "P \\<^sub>F Q \ (P \ S) \\<^sub>F Q" - by (simp add: F_ndet failure_refine_def order_trans) - -lemma mono_ndet_D_left[simp]: "P \\<^sub>D Q \ (P \ S) \\<^sub>D Q" - by (simp add: D_ndet divergence_refine_def order_trans) - -lemma mono_ndet_T_left[simp]: "P \\<^sub>T Q \ (P \ S) \\<^sub>T Q" - by (simp add: T_ndet trace_refine_def order_trans) - -corollary mono_ndet_DT_left[simp]: "P \\<^sub>D\<^sub>T Q \ (P \ S) \\<^sub>D\<^sub>T Q" - and mono_ndet_F_right[simp]: "P \\<^sub>F Q \ (S \ P) \\<^sub>F Q" - and mono_ndet_D_right[simp]: "P \\<^sub>D Q \ (S \ P) \\<^sub>D Q" - and mono_ndet_T_right[simp]: "P \\<^sub>T Q \ (S \ P) \\<^sub>T Q" - and mono_ndet_DT_right[simp]: "P \\<^sub>D\<^sub>T Q \ (S \ P) \\<^sub>D\<^sub>T Q" - by (simp_all add: trace_divergence_refine_def Ndet_commute) - -lemmas -mono_ndet_FD_left[simp] = - mono_ndet_FD_left[simplified failure_divergence_refine_def[symmetric]] and -mono_ndet_FD_right[simp] = - mono_ndet_FD_right[simplified failure_divergence_refine_def[symmetric]] - -lemma mono_ndet_det_FD[simp]: "(P \ S) \\<^sub>F\<^sub>D (P \ S)" - by (metis det_id failure_divergence_refine_def mono_det_FD mono_ndet_FD_left - mono_ndet_FD_right order_refl) - -corollary mono_ndet_det_F[simp]: "(P \ S) \\<^sub>F (P \ S)" - and mono_ndet_det_D[simp]: "(P \ S) \\<^sub>D (P \ S)" - and mono_ndet_det_T[simp]: "(P \ S) \\<^sub>T (P \ S)" - and mono_ndet_det_DT[simp]: "(P \ S) \\<^sub>D\<^sub>T (P \ S)" - by (simp_all add: FD_F FD_D le_F_T D_T_DT) - - -lemma mono_seq_F_right[simp]: "S \\<^sub>F S' \ (P `;` S) \\<^sub>F (P `;` S')" - apply (auto simp: failure_refine_def F_seq append_single_T_imp_tickFree) - using NF_ND by fastforce+ - -lemma mono_seq_D_right[simp]: "S \\<^sub>D S' \ (P `;` S) \\<^sub>D (P `;` S')" - by (auto simp: divergence_refine_def D_seq) - -lemma mono_seq_T_right[simp]: "S \\<^sub>T S' \ (P `;` S) \\<^sub>T (P `;` S')" - apply (auto simp: trace_refine_def T_seq append_single_T_imp_tickFree) - using D_T by fastforce+ - -corollary mono_seq_DT_right[simp]: "S \\<^sub>D\<^sub>T S' \ (P `;` S) \\<^sub>D\<^sub>T (P `;` S')" - by (simp add: trace_divergence_refine_def) - -lemma mono_seq_DT_left[simp]: "P \\<^sub>D\<^sub>T P' \ (P `;` S) \\<^sub>D\<^sub>T (P' `;` S)" - apply (auto simp: trace_divergence_refine_def divergence_refine_def trace_refine_def D_seq T_seq) - by (metis (no_types, lifting) Nil_elem_T Process.F_T T_F append.right_neutral - is_processT5_S3 subset_eq) - -\\left sequence monotony doesn't hold for \\\<^sub>F\, \\\<^sub>D\ and \\\<^sub>T\\ - -corollary mono_seq_DT[simp]: "P \\<^sub>D\<^sub>T P' \ S \\<^sub>D\<^sub>T S' \ (P `;` S) \\<^sub>D\<^sub>T (P' `;` S')" - using mono_seq_DT_left mono_seq_DT_right trans_DT by blast - -lemmas mono_seq_FD[simp]= mono_seq_FD[simplified failure_divergence_refine_def[symmetric]] - - -lemma mono_mprefix_F_process[simp]: "\x. P x \\<^sub>F Q x \ Mprefix A P \\<^sub>F Mprefix A Q" - by (auto simp: failure_refine_def F_Mprefix) - -lemma mono_mprefix_D_process[simp]: "\x. P x \\<^sub>D Q x \ Mprefix A P \\<^sub>D Mprefix A Q" - by (auto simp: divergence_refine_def D_Mprefix) - -lemma mono_mprefix_T_process[simp]: "\x. P x \\<^sub>T Q x \ Mprefix A P \\<^sub>T Mprefix A Q" - by (auto simp: trace_refine_def T_Mprefix) - -corollary mono_mprefix_DT_process[simp]: "\x. P x \\<^sub>D\<^sub>T Q x \ Mprefix A P \\<^sub>D\<^sub>T Mprefix A Q" - by (simp add: trace_divergence_refine_def) - -lemmas -mono_mprefix_FD_process[simp] = - mono_mprefix_FD[simplified failure_divergence_refine_def[symmetric]] - -lemma mono_mprefix_DT_set[simp]: "A \ B \ Mprefix B P \\<^sub>D\<^sub>T Mprefix A P" - by (auto simp add:T_Mprefix D_Mprefix trace_divergence_refine_def - trace_refine_def divergence_refine_def) - -corollary mono_mprefix_D_set[simp]: "A \ B \ Mprefix B P \\<^sub>D Mprefix A P" - and mono_mprefix_T_set[simp]: "A \ B \ Mprefix B P \\<^sub>T Mprefix A P" - by (simp_all add: DT_D DT_T) - -\\Mprefix set monotony doesn't hold for \\\<^sub>F\ and \\\<^sub>F\<^sub>D\ where it holds for deterministic choice\ - - -lemma mono_hide_F[simp]: "P \\<^sub>F Q \ P \\ A \\<^sub>F Q \\ A" - apply(cases "A={}", simp_all add: hide_set_empty failure_refine_def F_hiding, intro conjI, blast) -proof(subst (2) Un_commute, rule subsetI, rule UnCI, auto, goal_cases) - case (1 b t u) - then obtain a where a:"a \ A" by blast - define f where A:"f = rec_nat t (\i t. t @ [ev a])" - hence AA:"f (Suc i) = (f i) @ [ev a]" for i by simp - hence B:"strict_mono f" by (simp add:strict_mono_def lift_Suc_mono_less_iff) - from A have C:"t \ range f" by (metis (mono_tags, lifting) old.nat.simps(6) range_eqI) - { fix i - have "f i \ D Q \ tickFree (f i) \ trace_hide (f i) (ev ` A) = (trace_hide t (ev ` A))" - proof(induct i) - case 0 - then show ?case by (simp add: 1(4) 1(7) A) - next - case (Suc i) - then show ?case - apply (simp add:AA a) - using is_processT7[rule_format, of "f i" Q "[ev a]"] front_tickFree_single by blast - qed - } - with B C have "isInfHiddenRun f P A \ t \ range f" - by (metis 1(1) D_T F_subset_imp_T_subset subsetD) - with 1 show ?case by metis -next - case (2 b u f x) - then show ?case using F_subset_imp_T_subset by blast -qed - -lemma mono_hide_T[simp]: "P \\<^sub>T Q \ P \\ A \\<^sub>T Q \\ A" - apply(cases "A={}", simp add: hide_set_empty, simp add:trace_refine_def T_hiding, intro conjI) -proof(goal_cases) - case 1 - then show ?case - proof(subst Un_commute, rule_tac subsetI, rule_tac UnCI, auto, goal_cases) - case 11:(1 t a) - hence tt:"t \ T P" by (meson Process.F_T subset_eq) - with 11(1) inf_hidden[of A t P] obtain f where "isInfHiddenRun f P A \ t \ range f" by auto - with 11(4)[rule_format, of t "[]"] show ?case - by (metis 11(1) tt append_Nil2 front_tickFree_Nil is_processT2_TR - nonTickFree_n_frontTickFree tick_T_F) - qed -next - case 2 - then show ?case - proof(subst Un_commute, auto, goal_cases) - case 21:(1 t u a) - define f where A:"f = rec_nat t (\i t. t @ [ev a])" - hence AA:"f (Suc i) = (f i) @ [ev a]" for i by simp - hence B:"strict_mono f" by (simp add:strict_mono_def lift_Suc_mono_less_iff) - from A have C:"t \ range f" - by (metis (mono_tags, lifting) old.nat.simps(6) range_eqI) - { fix i - have "f i \ D Q \ tickFree (f i) \ trace_hide (f i) (ev ` A) = (trace_hide t (ev ` A))" - proof(induct i) - case 0 - then show ?case by (simp add: 21(4) 21(7) A) - next - case (Suc i) - then show ?case - apply (simp add:AA 21(6)) - using is_processT7[rule_format, of "f i" Q "[ev a]"] front_tickFree_single by blast - qed - } - with B C have "isInfHiddenRun f P A \ t \ range f" by (metis 21(1) D_T subsetD) - with 21 show ?case by metis - next - case 22:(2 b u f x) - then show ?case by blast - qed -qed - -lemma mono_hide_DT[simp]: "P \\<^sub>D\<^sub>T Q \ P \\ A \\<^sub>D\<^sub>T Q \\ A" -proof - - assume as:"P \\<^sub>D\<^sub>T Q" - then have "P \\ A \\<^sub>D Q \\ A" - apply(auto simp:trace_divergence_refine_def divergence_refine_def - trace_refine_def D_hiding T_hiding) - by blast+ - with DT_T[THEN mono_hide_T, OF as] show ?thesis by (simp add: trace_divergence_refine_def) -qed - -lemmas mono_hide_FD[simp] = - mono_hide_FD[simplified failure_divergence_refine_def[symmetric]] - -\\Obviously, Hide monotony doesn't hold for \\\<^sub>D\\ - - -lemma mono_sync_DT[simp]: "P \\<^sub>D\<^sub>T P' \ Q \\<^sub>D\<^sub>T Q' \ (P \ A \ Q) \\<^sub>D\<^sub>T (P' \ A \ Q')" - by (simp add:trace_divergence_refine_def divergence_refine_def trace_refine_def T_sync D_sync) - blast - -lemmas mono_sync_FD[simp] = - mono_sync_FD[simplified failure_divergence_refine_def[symmetric]] - -\\synchronization monotony doesn't hold for \\\<^sub>F\, \\\<^sub>D\ and \\\<^sub>T\\ - - -lemma mono_mndet_F_process[simp]: "\x\A. P x \\<^sub>F Q x \ mndet A P \\<^sub>F mndet A Q" - by (cases "A = {}", auto simp: failure_refine_def F_mndet write0_def F_Mprefix) - -lemma mono_mndet_D_process[simp]: "\x\A. P x \\<^sub>D Q x \ mndet A P \\<^sub>D mndet A Q" - by (cases "A = {}", auto simp: divergence_refine_def D_mndet write0_def D_Mprefix) - -lemma mono_mndet_T_process[simp]: "\x\A. P x \\<^sub>T Q x \ mndet A P \\<^sub>T mndet A Q" - by (cases "A = {}", auto simp: trace_refine_def T_mndet write0_def T_Mprefix) - -corollary mono_mndet_DT_process[simp]: "\x\A. P x \\<^sub>D\<^sub>T Q x \ mndet A P \\<^sub>D\<^sub>T mndet A Q" - by (simp add: trace_divergence_refine_def) - -lemmas -mono_mndet_FD_process[simp] = - mono_mndet_FD[simplified failure_divergence_refine_def[symmetric]] - -lemmas -mono_mndet_FD_set[simp] = - mndet_FD_subset[simplified failure_divergence_refine_def[symmetric]] - -corollary mono_mndet_F_set[simp]: "A \ {} \ A \ B \ mndet B P \\<^sub>F mndet A P" - and mono_mndet_D_set[simp]: "A \ {} \ A \ B \ mndet B P \\<^sub>D mndet A P" - and mono_mndet_T_set[simp]: "A \ {} \ A \ B \ mndet B P \\<^sub>T mndet A P" - and mono_mndet_DT_set[simp]: "A \ {} \ A \ B \ mndet B P \\<^sub>D\<^sub>T mndet A P" - by (simp_all add: FD_F FD_D le_F_T D_T_DT) - -lemmas -Mprefix_refines_Mndet_FD[simp] = - Mprefix_refines_Mndet[simplified failure_divergence_refine_def[symmetric]] - -corollary Mprefix_refines_Mndet_F[simp]: "mndet A P \\<^sub>F Mprefix A P" - and Mprefix_refines_Mndet_D[simp]: "mndet A P \\<^sub>D Mprefix A P" - and Mprefix_refines_Mndet_T[simp]: "mndet A P \\<^sub>T Mprefix A P" - and Mprefix_refines_Mndet_DT[simp]: "mndet A P \\<^sub>D\<^sub>T Mprefix A P" - by (simp_all add: FD_F FD_D le_F_T D_T_DT) - - -section \Reference processes and their unfolding rules\ - -thm DF_def DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def RUN_def CHAOS_def - -definition CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P :: "'a set \ 'a process" - where "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \ \ X. (SKIP \ STOP \ (\ x \ A \ X))" - - -thm DF_unfold DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold - -lemma RUN_unfold : "RUN A = (\ z \ A \ RUN A)" - by(simp add: RUN_def, rule trans, rule fix_eq, simp) - -lemma CHAOS_unfold : "CHAOS A = (STOP \ (\ z \ A \ CHAOS A))" - by(simp add: CHAOS_def, rule trans, rule fix_eq, simp) - -lemma CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold: "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \ SKIP \ STOP \ (\ x \ A \ CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A)" - unfolding CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def using fix_eq[of "\ X. (SKIP \ STOP \ (\ x \ A \ X))"] by simp - -section \Process events and reference processes events\ - -definition events_of where "events_of P \ (\t\T P. {a. ev a \ set t})" - -lemma events_DF: "events_of (DF A) = A" -proof(auto simp add:events_of_def) - fix x t - show "t \ T (DF A) \ ev x \ set t \ x \ A" - proof(induct t) - case Nil - then show ?case by simp - next - case (Cons a t) - from Cons(2) have "a # t \ T (\z\A \ DF A)" using DF_unfold by metis - then obtain aa where "a = ev aa \ aa \ A \ t \ T (DF A)" - by (cases "A={}", auto simp add:T_mndet write0_def T_Mprefix T_STOP) - with Cons show ?case by auto - qed -next - fix x - show "x \ A \ \xa\T (DF A). ev x \ set xa" - apply(subst DF_unfold, cases "A={}", auto simp add:T_mndet write0_def T_Mprefix) - by (metis Nil_elem_T list.sel(1) list.sel(3) list.set_intros(1)) -qed - -lemma events_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P: "events_of (DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) = A" -proof(auto simp add:events_of_def) - fix x t - show "t \ T (DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) \ ev x \ set t \ x \ A" - proof(induct t) - case Nil - then show ?case by simp - next - case (Cons a t) - from Cons(2) have "a # t \ T ((\z\A \ DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) \ SKIP)" using DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold by metis - with Cons obtain aa where "a = ev aa \ aa \ A \ t \ T (DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A)" - by (cases "A={}", auto simp add:T_mndet write0_def T_Mprefix T_STOP T_SKIP T_ndet) - with Cons show ?case by auto - qed -next - fix x - show "x \ A \ \xa\T (DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A). ev x \ set xa" - apply(subst DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold, cases "A={}") - apply(auto simp add:T_mndet write0_def T_Mprefix T_SKIP T_ndet) - by (metis Nil_elem_T list.sel(1) list.sel(3) list.set_intros(1)) -qed - -lemma events_RUN: "events_of (RUN A) = A" -proof(auto simp add:events_of_def) - fix x t - show "t \ T (RUN A) \ ev x \ set t \ x \ A" - proof(induct t) - case Nil - then show ?case by simp - next - case (Cons a t) - from Cons(2) have "a # t \ T (\z\A \ RUN A)" using RUN_unfold by metis - then obtain aa where "a = ev aa \ aa \ A \ t \ T (RUN A)" by (auto simp add:T_Mprefix) - with Cons show ?case by auto - qed -next - fix x - show "x \ A \ \xa\T (RUN A). ev x \ set xa" - apply(subst RUN_unfold, simp add: T_Mprefix) - by (metis Nil_elem_T list.sel(1) list.sel(3) list.set_intros(1)) -qed - -lemma events_CHAOS: "events_of (CHAOS A) = A" -proof(auto simp add:events_of_def) - fix x t - show "t \ T (CHAOS A) \ ev x \ set t \ x \ A" - proof(induct t) - case Nil - then show ?case by simp - next - case (Cons a t) - from Cons(2) have "a # t \ T (STOP \ (\ z \ A \ CHAOS A))" using CHAOS_unfold by metis - then obtain aa where "a = ev aa \ aa \ A \ t \ T (CHAOS A)" - by (auto simp add:T_ndet T_Mprefix T_STOP) - with Cons show ?case by auto - qed -next - fix x - show "x \ A \ \xa\T (CHAOS A). ev x \ set xa" - apply(subst CHAOS_unfold, simp add:T_ndet T_Mprefix T_STOP) - by (metis Nil_elem_T list.sel(1) list.sel(3) list.set_intros(1)) -qed - -lemma events_CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P: "events_of (CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) = A" -proof(auto simp add:events_of_def) - fix x t - show "t \ T (CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) \ ev x \ set t \ x \ A" - proof(induct t) - case Nil - then show ?case by simp - next - case (Cons a t) - from Cons(2) have "a # t \ T (SKIP \ STOP \ (\ z \ A \ CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A))" - using CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold by metis - with Cons obtain aa where "a = ev aa \ aa \ A \ t \ T (CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A)" - by (auto simp add:T_ndet T_Mprefix T_STOP T_SKIP) - with Cons show ?case by auto - qed -next - fix x - show "x \ A \ \xa\T (CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A). ev x \ set xa" - apply(subst CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold, simp add:T_ndet T_Mprefix T_STOP T_SKIP) - by (metis Nil_elem_T list.sel(1) list.sel(3) list.set_intros(1)) -qed - -lemma events_div: "D(P) \ {} \ events_of (P) = UNIV" -proof(auto simp add:events_of_def) - fix x xa - assume 1: "x \ D P" - show "\x\T P. ev xa \ set x" - proof(cases "tickFree x") - case True - hence "x@[ev xa] \ T P" - using 1 NT_ND front_tickFree_single is_processT7 by blast - then show ?thesis by force - next - case False - hence "(butlast x)@[ev xa] \ T P" - by (metis "1" D_T D_imp_front_tickFree append_single_T_imp_tickFree butlast_snoc - front_tickFree_single nonTickFree_n_frontTickFree process_charn) - then show ?thesis by force - qed -qed - - -thm DF_subset - -lemma DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_subset_FD: "A \ {} \ A \ B \ DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P B \\<^sub>F\<^sub>D DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A" - apply(subst DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def, rule fix_ind, rule le_FD_adm, simp_all add:monofunI, subst DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold) - by (rule mono_ndet_FD, simp_all) (meson mono_mndet_FD_process mono_mndet_FD_set trans_FD) - -lemma RUN_subset_DT: "A \ B \ RUN B \\<^sub>D\<^sub>T RUN A" - apply(subst RUN_def, rule fix_ind, rule le_DT_adm, simp_all add:monofunI, subst RUN_unfold) - by (meson mono_mprefix_DT_process mono_mprefix_DT_set trans_DT) - -lemma CHAOS_subset_FD: "A \ B \ CHAOS B \\<^sub>F\<^sub>D CHAOS A" - apply(subst CHAOS_def, rule fix_ind, rule le_FD_adm, simp_all add:monofunI, subst CHAOS_unfold) - by (auto simp add: failure_divergence_refine_def le_ref_def - D_Mprefix D_ndet F_STOP F_Mprefix F_ndet) - -lemma CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_subset_FD: "A \ B \ CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P B \\<^sub>F\<^sub>D CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A" - apply(subst CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def, rule fix_ind, rule le_FD_adm) - apply(simp_all add:monofunI, subst CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold) - by (auto simp add: failure_divergence_refine_def le_ref_def - D_Mprefix D_ndet F_STOP F_Mprefix F_ndet) - -section \Relations between refinements on reference processes\ - -lemma CHAOS_has_all_tickFree_failures: - "tickFree a \ {x. ev x \ set a} \ A \ (a,b) \ F (CHAOS A)" -proof(induct a) - case Nil - then show ?case - by (subst CHAOS_unfold, simp add:F_ndet F_STOP) -next - case (Cons a0 al) - hence "tickFree al" - by (metis append.left_neutral append_Cons front_tickFree_charn front_tickFree_mono) - with Cons show ?case - apply (subst CHAOS_unfold, simp add:F_ndet F_STOP F_Mprefix events_of_def) - using event_set by blast -qed - -lemma CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_has_all_failures: - assumes as:"(events_of P) \ A" - shows "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>F P" -proof - - have "front_tickFree a \ set a \ (\t\T P. set t) \ (a,b) \ F (CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A)" for a b - proof(induct a) - case Nil - then show ?case - by (subst CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold, simp add:F_ndet F_STOP) - next - case (Cons a0 al) - hence "front_tickFree al" - by (metis append.left_neutral append_Cons front_tickFree_charn front_tickFree_mono) - with Cons show ?case - apply (subst CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold, simp add:F_ndet F_STOP F_SKIP F_Mprefix events_of_def as) - apply(cases "a0=tick") - apply (metis append.simps(2) front_tickFree_charn - front_tickFree_mono list.distinct(1) tickFree_Cons) - using event_set image_iff as[simplified events_of_def] by fastforce - qed - thus ?thesis - by (simp add: F_T SUP_upper failure_refine_def process_charn subrelI) -qed - -corollary CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_has_all_failures_ev: "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P (events_of P) \\<^sub>F P" - and CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_has_all_failures_Un: "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV \\<^sub>F P" - by (simp_all add: CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_has_all_failures) - - -lemma DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_DF_refine_F: "DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>F DF A" - by (simp add:DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def, rule fix_ind, simp_all add:le_F_adm monofunI, subst DF_unfold, simp) - -lemma DF_RUN_refine_F: "DF A \\<^sub>F RUN A" - apply (simp add:DF_def, rule fix_ind, simp_all add:le_F_adm monofunI, subst RUN_unfold) - by (meson Mprefix_refines_Mndet_F mono_mndet_F_process trans_F) - -lemma CHAOS_DF_refine_F: "CHAOS A \\<^sub>F DF A" - apply (simp add:CHAOS_def DF_def, rule parallel_fix_ind, simp_all add: monofunI) - apply (rule le_F_adm, simp_all add: monofun_snd) - by (cases "A={}", auto simp add:adm_def failure_refine_def F_mndet - F_Mprefix write0_def F_ndet F_STOP) - -corollary CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_CHAOS_refine_F: "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>F CHAOS A" - and CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_refine_F: "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>F DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A" - by (simp_all add: CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_has_all_failures events_CHAOS events_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P - trans_F[OF CHAOS_DF_refine_F DF_RUN_refine_F]) - - -lemma div_free_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P: "D(DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) = {}" -proof(simp add:DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def fix_def) - define Y where "Y \ \i. iterate i\(\ x. (\xa\A \ x) \ SKIP)\\" - hence a:"chain Y" by simp - have "D (Y (Suc i)) = {d. d \ [] \ hd d \ (ev ` A) \ tl d \ D(Y i)}" for i - by (cases "A={}", auto simp add:Y_def D_STOP D_SKIP D_mndet write0_def D_Mprefix D_ndet) - hence b:"d \ D(Y i) \ length d \ i" for d i - by (induct i arbitrary:d, simp_all add: Nitpick.size_list_simp(2)) - { fix x - assume c:"\ i. x \ D (Y i)" - from b have "x \ D (Y (Suc (length x)))" using Suc_n_not_le_n by blast - with c have False by simp - } - with a show "D (\i. Y i) = {}" - using D_LUB[OF a] limproc_is_thelub[OF a] by auto -qed - -lemma div_free_DF: "D(DF A) = {}" -proof - - have "DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>D DF A" - by (simp add:DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def, rule fix_ind, simp_all add:le_D_adm monofunI, subst DF_unfold, simp) - then show ?thesis using divergence_refine_def div_free_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P by blast -qed - -lemma div_free_CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P: "D (CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) = {}" -proof - - have "DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>D CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A" - proof (simp add:DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def, rule fix_ind, simp_all add:le_D_adm monofunI, subst CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold) - fix x - assume 1:"x \\<^sub>D CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A" - have a:"((\xa\A \ x) \ SKIP) = (SKIP \ SKIP \ (\xa\A \ x))" - by (simp add: Ndet_commute ndet_id) - from 1 have b:"(SKIP \ SKIP \ (\xa\A \ x)) \\<^sub>D (SKIP \ STOP \ (\xa\A \ CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A))" - by (meson DT_D Mprefix_refines_Mndet_D STOP_leDT idem_D - mono_mprefix_D_process mono_ndet_D trans_D) - from a b show "((\xa\A \ x) |-| SKIP) \\<^sub>D (SKIP |-| STOP |-| Mprefix A (\x. CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A))" - by simp - qed - then show ?thesis using divergence_refine_def div_free_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P by blast -qed - -lemma div_free_CHAOS: "D(CHAOS A) = {}" -proof - - have "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>D CHAOS A" - apply (simp add:CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def, rule fix_ind) - by (simp_all add:le_D_adm monofunI, subst CHAOS_unfold, simp) - then show ?thesis using divergence_refine_def div_free_CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P by blast -qed - -lemma div_free_RUN: "D(RUN A) = {}" -proof - - have "CHAOS A \\<^sub>D RUN A" - by (simp add:CHAOS_def, rule fix_ind, simp_all add:le_D_adm monofunI, subst RUN_unfold, simp) - then show ?thesis using divergence_refine_def div_free_CHAOS by blast -qed - -corollary DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_DF_refine_FD: "DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>F\<^sub>D DF A" - and DF_RUN_refine_FD: "DF A \\<^sub>F\<^sub>D RUN A" - and CHAOS_DF_refine_FD: "CHAOS A \\<^sub>F\<^sub>D DF A" - and CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_CHAOS_refine_FD: "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>F\<^sub>D CHAOS A" - and CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_refine_FD: "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A \\<^sub>F\<^sub>D DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A" - using div_free_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P[of A] div_free_CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P[of A] div_free_DF[of A] div_free_RUN[of A] - div_free_CHAOS[of A] - F_D_FD[OF DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_DF_refine_F, of A] F_D_FD[OF DF_RUN_refine_F, of A] - F_D_FD[OF CHAOS_DF_refine_F, of A] F_D_FD[OF CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_CHAOS_refine_F, of A] - F_D_FD[OF CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_refine_F, of A] - by (auto simp add:divergence_refine_def) - - -lemma traces_CHAOS_sub: "T(CHAOS A) \ {s. set s \ ev ` A}" -proof(auto) - fix s sa - assume "s \ T (CHAOS A)" and "sa \ set s" - then show "sa \ ev ` A" - apply (induct s, simp) - by (subst (asm) (2) CHAOS_unfold, cases "A={}", auto simp add:T_ndet T_STOP T_Mprefix) -qed - -lemma traces_RUN_sub: "{s. set s \ ev ` A} \ T(RUN A)" -proof(auto) - fix s - assume "set s \ ev ` A" - then show "s \ T (RUN A)" - by (induct s, simp add: Nil_elem_T) (subst RUN_unfold, auto simp add:T_Mprefix) -qed - -corollary RUN_all_tickfree_traces1: "T(RUN A) = {s. set s \ ev ` A}" - and DF_all_tickfree_traces1: "T(DF A) = {s. set s \ ev ` A}" - and CHAOS_all_tickfree_traces1: "T(CHAOS A) = {s. set s \ ev ` A}" - using DF_RUN_refine_F[THEN le_F_T, simplified trace_refine_def] - CHAOS_DF_refine_F[THEN le_F_T,simplified trace_refine_def] - traces_CHAOS_sub traces_RUN_sub by blast+ - -corollary RUN_all_tickfree_traces2: "tickFree s \ s \ T(RUN UNIV)" - and DF_all_tickfree_traces2: "tickFree s \ s \ T(DF UNIV)" - and CHAOS_all_tickfree_trace2: "tickFree s \ s \ T(CHAOS UNIV)" - apply(simp_all add:tickFree_def RUN_all_tickfree_traces1 - DF_all_tickfree_traces1 CHAOS_all_tickfree_traces1) - by (metis event_set insertE subsetI)+ - -lemma traces_CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_sub: "T(CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) \ {s. front_tickFree s \ set s \ (ev ` A \ {tick})}" -proof(auto simp add:is_processT2_TR) - fix s sa - assume "s \ T (CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A)" and "sa \ set s" and "sa \ ev ` A" - then show "sa = tick" - apply (induct s, simp) - by (subst (asm) (2) CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold, cases "A={}", auto simp add:T_ndet T_STOP T_SKIP T_Mprefix) -qed - -lemma traces_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_sub: - "{s. front_tickFree s \ set s \ (ev ` A \ {tick})} \ T(DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A::'a process)" -proof(auto) - fix s - assume a:"front_tickFree s" and b:"set s \ insert tick (ev ` A)" - have c:"front_tickFree ((tick::'a event) # s) \ s = []" for s - by (metis butlast.simps(2) butlast_snoc front_tickFree_charn list.distinct(1) tickFree_Cons) - with a b show "s \ T (DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A)" - apply (induct s, simp add: Nil_elem_T, subst DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold, cases "A={}") - apply (subst DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_unfold, cases "A={}") - apply(auto simp add:T_Mprefix T_mndet write0_def T_SKIP T_ndet T_STOP) - apply (metis append_Cons append_Nil front_tickFree_charn front_tickFree_mono) - by (metis append_Cons append_Nil front_tickFree_mono) - qed - -corollary DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_all_front_tickfree_traces1: - "T(DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) = {s. front_tickFree s \ set s \ (ev ` A \ {tick})}" - and CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_all_front_tickfree_traces1: - "T(CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P A) = {s. front_tickFree s \ set s \ (ev ` A \ {tick})}" - using CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_refine_F[THEN le_F_T, simplified trace_refine_def] - traces_CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_sub traces_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_sub by blast+ - -corollary DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_all_front_tickfree_traces2: "front_tickFree s \ s \ T(DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV)" - and CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_all_front_tickfree_traces2: "front_tickFree s \ s \ T(CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV)" - apply(simp_all add:tickFree_def DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_all_front_tickfree_traces1 - CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_all_front_tickfree_traces1) - by (metis event_set subsetI)+ - -corollary DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_has_all_traces: "DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV \\<^sub>T P" - and CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_has_all_traces: "CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV \\<^sub>T P" - apply (simp add:trace_refine_def DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_all_front_tickfree_traces2 is_processT2_TR subsetI) - by (simp add:trace_refine_def CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_all_front_tickfree_traces2 is_processT2_TR subsetI) - -end diff --git a/thys/CSP_RefTK/CopyBuffer_props.thy b/thys/CSP_RefTK/CopyBuffer_props.thy --- a/thys/CSP_RefTK/CopyBuffer_props.thy +++ b/thys/CSP_RefTK/CopyBuffer_props.thy @@ -1,120 +1,89 @@ (*<*) \\ ******************************************************************** * Project : CSP-RefTK - A Refinement Toolkit for HOL-CSP * Version : 1.0 * * Author : Burkhart Wolff, Safouan Taha, Lina Ye. * * This file : The Copy-Buffer Example Revisited * * Copyright (c) 2020 Université Paris-Saclay, France * * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * * Redistributions in binary form must reproduce the above * copyright notice, this list of conditions and the following * disclaimer in the documentation and/or other materials provided * with the distribution. * * * Neither the name of the copyright holders nor the names of its * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. ******************************************************************************\ (*>*) chapter\Examples\ section\CopyBuffer Refinement over an infinite alphabet\ theory CopyBuffer_props - imports "HOL-CSP.CopyBuffer" "Properties" + imports "HOL-CSP.CopyBuffer" "HOL-CSP.Assertions" begin subsection\ The Copy-Buffer vs. reference processes \ lemma DF_COPY: "(DF (range left \ range right)) \\<^sub>F\<^sub>D COPY" - apply(simp add: DF_def,rule fix_ind2, simp_all) -proof - - show "adm (\a. a \\<^sub>F\<^sub>D COPY)" by (rule le_FD_adm, simp_all add: monofunI) -next - have 1: "(\xa\ range left \ range right \ \) \\<^sub>F\<^sub>D (\xa\ range left \ \)" by simp - have 2: "(\xa\ range left \ \) \\<^sub>F\<^sub>D (left\<^bold>?x \ \)" - unfolding read_def - by (meson BOT_leFD mono_Mndetprefix_FD Mprefix_refines_Mndetprefix_FD trans_FD) - show "(\x\range left \ range right \ \) \\<^sub>F\<^sub>D COPY" - by (metis (mono_tags, lifting) "1" "2" BOT_leFD COPY_rec mono_read_FD trans_FD) -next - fix P::"'a channel process" - assume *: "P \\<^sub>F\<^sub>D COPY" and ** : "(\x\range left \ range right \ P) \\<^sub>F\<^sub>D COPY" - have 1: "(\xa\ range left \ range right \ P) \\<^sub>F\<^sub>D (\xa\ range right \ P)" by force - have 2: "(\xa\ range right \ P) \\<^sub>F\<^sub>D (right\<^bold>!x \ P)" for x - by (metis mono_Mndetprefix_FD_set[of "{right x}" "range right"] Mprefix_refines_Mndetprefix_FD - empty_not_insert insert_subset rangeI sup_bot_left sup_ge1 trans_FD write_def) + by (simp add: DF_COPY) - - from 1 2 have ab: "(\xa\ range left \ range right \ P) \\<^sub>F\<^sub>D (right\<^bold>!x \ P)" for x - using trans_FD by blast - hence 3: "(left\<^bold>?x \ (\xa\ range left \ range right \ P)) \\<^sub>F\<^sub>D (left\<^bold>?x \(right\<^bold>!x \ P))" by simp - have 4: "\X. (\xa\ range left \ range right \ X) \\<^sub>F\<^sub>D (\xa\ range left \ X)" by simp - have 5: "\X. (\xa\ range left \ X) \\<^sub>F\<^sub>D (left\<^bold>?x \ X)" by (simp add: read_def K_record_comp) - from 3 4[of "(\xa\ range left \ range right \ P)"] - 5 [of "(\xa\ range left \ range right \ P)"] - have 6:"(\xa\ range left \ range right \ - (\xa\ range left \ range right \ P)) \\<^sub>F\<^sub>D (left\<^bold>?x \ (right\<^bold>!x \ P))" - using trans_FD by blast - from * ** have 7: "(left\<^bold>?x \ (right\<^bold>!x \ P)) \\<^sub>F\<^sub>D (left\<^bold>?x \ (right\<^bold>!x \ COPY))" by fastforce - show "(\x\range left \ range right \ \x\range left \ range right \ P) \\<^sub>F\<^sub>D COPY" - by (metis (mono_tags, lifting) "6" "7" COPY_rec trans_FD) -qed subsection\ ... and abstract consequences \ corollary df_COPY: "deadlock_free COPY" and lf_COPY: "lifelock_free COPY" apply (meson DF_COPY DF_Univ_freeness UNIV_not_empty image_is_empty sup_eq_bot_iff) by (meson CHAOS_DF_refine_FD DF_COPY DF_Univ_freeness UNIV_not_empty deadlock_free_def image_is_empty lifelock_free_def sup_eq_bot_iff trans_FD) corollary df_v2_COPY: "deadlock_free_v2 COPY" and lf_v2_COPY: "lifelock_free_v2 COPY" and nt_COPY: "non_terminating COPY" apply (simp add: df_COPY deadlock_free_is_deadlock_free_v2) apply (simp add: lf_COPY lifelock_free_is_lifelock_free_v2) using lf_COPY lifelock_free_is_non_terminating by blast lemma DF_SYSTEM: "DF UNIV \\<^sub>F\<^sub>D SYSTEM" using DF_subset[of "(range left \ range right)" UNIV, simplified] DF_COPY impl_refines_spec trans_FD by blast corollary df_SYSTEM: "deadlock_free SYSTEM" and lf_SYSTEM: "lifelock_free SYSTEM" apply (simp add: DF_SYSTEM deadlock_free_def) using CHAOS_DF_refine_FD DF_SYSTEM lifelock_free_def trans_FD by blast corollary df_v2_SYSTEM: "deadlock_free_v2 SYSTEM" and lf_v2_SYSTEM: "lifelock_free_v2 SYSTEM" and nt_SYSTEM: "non_terminating SYSTEM" apply (simp add: df_SYSTEM deadlock_free_is_deadlock_free_v2) apply (simp add: lf_SYSTEM lifelock_free_is_lifelock_free_v2) using lf_SYSTEM lifelock_free_is_non_terminating by blast end diff --git a/thys/CSP_RefTK/Fix_ind_ext.thy b/thys/CSP_RefTK/Fix_ind_ext.thy deleted file mode 100644 --- a/thys/CSP_RefTK/Fix_ind_ext.thy +++ /dev/null @@ -1,142 +0,0 @@ -(*<*) -\\ ******************************************************************** - * Project : CSP-RefTK - A Refinement Toolkit for HOL-CSP - * Version : 1.0 - * - * Author : Burkhart Wolff, Safouan Taha, Lina Ye. - * - * This file : More Fixpoint and k-Induction Schemata - * - * Copyright (c) 2020 Université Paris-Saclay, France - * - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following - * disclaimer in the documentation and/or other materials provided - * with the distribution. - * - * * Neither the name of the copyright holders nor the names of its - * contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - ******************************************************************************\ -(*>*) - -chapter \ Advanced Induction Schemata \ - -theory Fix_ind_ext - -imports HOLCF - -begin - -section\k-fixpoint-induction\ - -lemma nat_k_induct: - fixes k::nat - assumes "\in\<^sub>0. (\i0+i)) \ P (n\<^sub>0+k)" - shows "P (n::nat)" -proof(induct rule:nat_less_induct) - case (1 n) - then show ?case - apply(cases "n < k") - using assms(1) apply blast - using assms(2)[rule_format, of "n-k"] by auto -qed - -thm fix_ind fix_ind2 - -lemma fix_ind_k: - fixes k::nat - assumes adm: "adm P" - assumes base_k_steps: "\if\\)" - assumes step: "\x. (\if\x)) \ P (iterate k\f\x)" - shows "P (fix\f)" - unfolding fix_def2 apply (rule admD [OF adm chain_iterate]) - apply(rule nat_k_induct[of k], simp add: base_k_steps) - using step by (subst (1 2) add.commute, unfold iterate_iterate[symmetric]) blast - -lemma nat_k_skip_induct: - fixes k::nat - assumes "k \ 1" and "\in\<^sub>0. P (n\<^sub>0) \ P (n\<^sub>0+k)" - shows "P (n::nat)" -proof(induct rule:nat_less_induct) - case (1 n) - then show ?case - apply(cases "n < k") - using assms(2) apply blast - using assms(3)[rule_format, of "n-k"] assms(1) by auto -qed - -lemma fix_ind_k_skip: - fixes k::nat - assumes k_1: "k \ 1" - assumes adm: "adm P" - assumes base_k_steps: "\if\\)" - assumes step: "\x. P x \ P (iterate k\f\x)" - shows "P (fix\f)" - unfolding fix_def2 apply (rule admD [OF adm chain_iterate]) - apply(rule nat_k_skip_induct[of k]) - using k_1 base_k_steps apply auto - using step by (subst add.commute, unfold iterate_iterate[symmetric]) blast - -thm parallel_fix_ind - -section\Parallel fixpoint-induction\ - -lemma parallel_fix_ind_inc: - assumes adm: "adm (\x. P (fst x) (snd x))" - assumes base_fst: "\y. P \ y" and base_snd: "\x. P x \" - assumes step: "\x y. P x y \ P (G\x) y \ P x (H\y) \ P (G\x) (H\y)" - shows "P (fix\G) (fix\H)" -proof - - from adm have adm': "adm (case_prod P)" - unfolding split_def . - have "P (iterate i\G\\) (iterate j\H\\)" for i j - proof(induct "i+j" arbitrary:i j rule:nat_less_induct) - case 1 - { fix i' j' - assume i:"i = Suc i'" and j:"j = Suc j'" - have "P (iterate i'\G\\) (iterate j'\H\\)" - and "P (iterate i'\G\\) (iterate j\H\\)" - and "P (iterate i\G\\) (iterate j'\H\\)" - using "1.hyps" add_strict_mono i j apply blast - using "1.hyps" i apply auto[1] - using "1.hyps" j by auto - hence ?case by (simp add: i j step) - } - thus ?case - apply(cases i, simp add:base_fst) - apply(cases j, simp add:base_snd) - by assumption - qed - then have "\i. case_prod P (iterate i\G\\, iterate i\H\\)" - by simp - then have "case_prod P (\i. (iterate i\G\\, iterate i\H\\))" - by - (rule admD [OF adm'], simp, assumption) - then have "P (\i. iterate i\G\\) (\i. iterate i\H\\)" - by (simp add: lub_Pair) - then show "P (fix\G) (fix\H)" - by (simp add: fix_def2) -qed - -end \ No newline at end of file diff --git a/thys/CSP_RefTK/Introduction.thy b/thys/CSP_RefTK/Introduction.thy --- a/thys/CSP_RefTK/Introduction.thy +++ b/thys/CSP_RefTK/Introduction.thy @@ -1,123 +1,124 @@ (*<*) \\ ******************************************************************** * Project : CSP-RefTK - A Refinement Toolkit for HOL-CSP * Version : 1.0 * * Author : Burkhart Wolff, Safouan Taha, Lina Ye. * * This file : An Introduction * * Copyright (c) 2020 Université Paris-Saclay, France * * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * * Redistributions in binary form must reproduce the above * copyright notice, this list of conditions and the following * disclaimer in the documentation and/or other materials provided * with the distribution. * * * Neither the name of the copyright holders nor the names of its * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. ******************************************************************************\ (*>*) chapter\Context\ (*<*) theory Introduction imports HOLCF begin (*>*) section\Introduction\ text\ Communicating Sequential Processes CSP is a language to specify and verify patterns of interaction of concurrent systems. Together with CCS and LOTOS, it belongs to the family of \<^emph>\process algebras\. CSP's rich theory comprises denotational, operational and algebraic semantic facets and has influenced programming languages such as Limbo, Crystal, Clojure and most notably Golang @{cite "donovan2015go"}. CSP has been applied in industry as a tool for specifying and verifying the concurrent aspects of hardware systems, such as the T9000 transputer @{cite "Barret95"}. The theory of CSP, in particular the denotational Failure/Divergence Denotational Semantics, has been initially proposed in the book by Tony Hoare @{cite "Hoare:1985:CSP:3921"}, but evolved substantially since @{cite "BrookesHR84" and "brookes-roscoe85" and "roscoe:csp:1998"}. Verification of CSP properties has been centered around the notion of \<^emph>\process refinement orderings\, most notably \_\\<^sub>F\<^sub>D_\ and \_\_\. The latter turns the denotational domain of CSP into a Scott cpo @{cite "scott:cpo:1972"}, which yields semantics for the fixed point operator \\x. f(x)\ provided that \f\ is continuous with respect to \_\_\. Since it is possible to express deadlock-freeness and livelock-freeness as a refinement problem, the verification of properties has been reduced traditionally to a model-checking problem for a finite set of events \A\. We are interested in verification techniques for arbitrary event sets \A\ or arbitrarily parameterized processes. Such processes can be used to model dense-timed processes, processes with dynamic thread creation, and processes with unbounded thread-local variables and buffers. Events may even be higher-order objects such as functions or again processes, paving the way for the modeling of re-programmable compute servers or dynamic distributed computing architectures. However, this adds substantial complexity to the process theory: when it comes to study the interplay of different denotational models, refinement-orderings, and side-conditions for continuity, paper-and-pencil proofs easily reach their limits of precision. Several attempts have been undertaken to develop the formal theory of CSP in an interactive proof system, mostly in Isabelle/HOL @{cite "Camilleri91" and "tej.ea:corrected:1997" and "IsobeRoggenbach2010"}. This work is based on the most recent instance in this line, HOL-CSP 2.0, which has been published as AFP submission @{cite "HOL-CSP-AFP"} and whose development is hosted at \<^url>\https://gitlri.lri.fr/burkhart.wolff/hol-csp2.0\. The present AFP Module is an add-on on this work and develops some support for -\<^enum> advanced induction schemes (mutual fixed-point Induction, K-induction), -\<^enum> bridge-Lemmas between the classical refinement relations in the FD-semantics, - which allow for reduced refinement proof complexity in certain cases, and +\<^enum> example of induction schemes (mutual fixed-point Induction, K-induction), \<^enum> a theory of explicit state normalisation which allows for proofs over certain communicating networks of arbitrary size. \newpage \ - +(* \<^enum> bridge-Lemmas between the classical refinement relations in the FD-semantics, + which allow for reduced refinement proof complexity in certain cases, and *) section\The Global Architecture of CSP\_RefTk\ text\ \begin{figure}[ht] \centering \includegraphics[width=0.60\textwidth]{figures/session_graph.pdf} \caption{The overall architecture: HOLCF, HOL-CSP, and CSP\_RefTk} \label{fig:fig1} \end{figure} \ text\The global architecture of CSP\_RefTk is shown in \autoref{fig:fig1}. The entire package resides on: \<^enum> \<^session>\HOL-Eisbach\ from the Isabelle/HOL distribution, \<^enum> \<^session>\HOLCF\ from the Isabelle/HOL distribution, and \<^enum> \<^session>\HOL-CSP\ 2.0 from the Isabelle Archive of Formal Proofs. +\ +(* \<^noindent> The theories \<^verbatim>\Assertion_ext\ and \<^verbatim>\Fixind_ext\ are extensions of the -corresponding theories in \<^session>\HOL-CSP\.\ +corresponding theories in \<^session>\HOL-CSP\. *) (*<*) end (*>*) diff --git a/thys/CSP_RefTK/Process_norm.thy b/thys/CSP_RefTK/Process_norm.thy --- a/thys/CSP_RefTK/Process_norm.thy +++ b/thys/CSP_RefTK/Process_norm.thy @@ -1,246 +1,246 @@ (*<*) \\ ******************************************************************** * Project : CSP-RefTK - A Refinement Toolkit for HOL-CSP * Version : 1.0 * * Author : Burkhart Wolff, Safouan Taha, Lina Ye. * * This file : A Normalization Theory * * Copyright (c) 2020 Université Paris-Saclay, France * * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * * Redistributions in binary form must reproduce the above * copyright notice, this list of conditions and the following * disclaimer in the documentation and/or other materials provided * with the distribution. * * * Neither the name of the copyright holders nor the names of its * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. ******************************************************************************\ (*>*) chapter\ Normalisation of Deterministic CSP Processes \ theory Process_norm -imports "Properties" "HOL-CSP.Induction_ext" +imports "HOL-CSP.Assertions" "HOL-CSP.CSP_Induct" begin section\Deterministic normal-forms with explicit state\ abbreviation "P_dnorm \ \ \ (\ X. (\ s. \ e \ (\ s) \ X (\ s e)))" notation P_dnorm ("P\<^sub>n\<^sub>o\<^sub>r\<^sub>m\_,_\" 60) lemma dnorm_cont[simp]: fixes \::"'\::type \ 'event::type set" and \::"'\ \ 'event \ '\" shows "cont (\X. (\s. \ e \ (\ s) \ X (\ s e)))" (is "cont ?f") proof - have "cont (\X. ?f X s)" for s by (simp add:cont_fun) then show ?thesis by simp qed section\Interleaving product lemma\ lemma dnorm_inter: fixes \\<^sub>1 ::"'\\<^sub>1::type \ 'event::type set" and \\<^sub>2::"'\\<^sub>2::type \ 'event set" and \\<^sub>1 ::"'\\<^sub>1 \ 'event \ '\\<^sub>1" and \\<^sub>2::"'\\<^sub>2 \ 'event \ '\\<^sub>2" defines P: "P \ P\<^sub>n\<^sub>o\<^sub>r\<^sub>m\\\<^sub>1,\\<^sub>1\" (is "P \ fix\(\ X. ?P X)") defines Q: "Q \ P\<^sub>n\<^sub>o\<^sub>r\<^sub>m\\\<^sub>2,\\<^sub>2\" (is "Q \ fix\(\ X. ?Q X)") assumes indep: \\s\<^sub>1 s\<^sub>2. \\<^sub>1 s\<^sub>1 \ \\<^sub>2 s\<^sub>2 = {}\ defines Tr: "\ \ (\(s\<^sub>1,s\<^sub>2). \\<^sub>1 s\<^sub>1 \ \\<^sub>2 s\<^sub>2)" defines Up: "\ \ (\(s\<^sub>1,s\<^sub>2) e. if e \ \\<^sub>1 s\<^sub>1 then (\\<^sub>1 s\<^sub>1 e,s\<^sub>2) else if e \ \\<^sub>2 s\<^sub>2 then (s\<^sub>1, \\<^sub>2 s\<^sub>2 e) else (s\<^sub>1,s\<^sub>2))" defines S: "S \ P\<^sub>n\<^sub>o\<^sub>r\<^sub>m\\,\\" (is "S \ fix\(\ X. ?S X)") shows "(P s\<^sub>1 ||| Q s\<^sub>2) = S (s\<^sub>1,s\<^sub>2)" proof - have P_rec: "P = ?P P" using fix_eq[of "(\ X. ?P X)"] P by simp have Q_rec: "Q = ?Q Q" using fix_eq[of "(\ X. ?Q X)"] Q by simp have S_rec: "S = ?S S" using fix_eq[of "(\ X. ?S X)"] S by simp have dir1: "\ s\<^sub>1 s\<^sub>2. (P s\<^sub>1 ||| Q s\<^sub>2) \\<^sub>F\<^sub>D S (s\<^sub>1, s\<^sub>2)" proof(subst P, subst Q, induct rule:parallel_fix_ind_inc[of "\x y. \ s\<^sub>1 s\<^sub>2. (x s\<^sub>1 ||| y s\<^sub>2) \\<^sub>F\<^sub>D S (s\<^sub>1,s\<^sub>2)"]) case admissibility then show ?case by (intro adm_all le_FD_adm) (simp_all add: cont2cont_fun monofunI) next case (base_fst y) then show ?case by (metis app_strict BOT_leFD Sync_BOT Sync_commute) next case (base_snd x) then show ?case by (simp add: Sync_BOT) next case (step x) then show ?case (is "\ s\<^sub>1 s\<^sub>2. ?C s\<^sub>1 s\<^sub>2") proof(intro allI) fix s\<^sub>1 s\<^sub>2 show "?C s\<^sub>1 s\<^sub>2" apply simp apply (subst Mprefix_Sync_distr_indep[where S = "{}", simplified]) apply (subst S_rec, simp add: Tr Up Mprefix_Un_distrib) apply (intro mono_Det_FD mono_Mprefix_FD) using step(3)[simplified] indep apply simp using step(2)[simplified] indep by fastforce qed qed have dir2: "\ s\<^sub>1 s\<^sub>2. S (s\<^sub>1, s\<^sub>2) \\<^sub>F\<^sub>D (P s\<^sub>1 ||| Q s\<^sub>2)" proof(subst S, induct rule:fix_ind_k[of "\x. \ s\<^sub>1 s\<^sub>2. x (s\<^sub>1,s\<^sub>2) \\<^sub>F\<^sub>D (P s\<^sub>1 ||| Q s\<^sub>2)" 1]) case admissibility show ?case by (intro adm_all le_FD_adm) (simp_all add: cont_fun monofunI) next case base_k_steps then show ?case by simp next case step then show ?case (is "\ s\<^sub>1 s\<^sub>2. ?C s\<^sub>1 s\<^sub>2") proof(intro allI) fix s\<^sub>1 s\<^sub>2 have P_rec_sym:"Mprefix (\\<^sub>1 s\<^sub>1) (\e. P (\\<^sub>1 s\<^sub>1 e)) = P s\<^sub>1" using P_rec by metis have Q_rec_sym:"Mprefix (\\<^sub>2 s\<^sub>2) (\e. Q (\\<^sub>2 s\<^sub>2 e)) = Q s\<^sub>2" using Q_rec by metis show "?C s\<^sub>1 s\<^sub>2" apply (simp add: Tr Up Mprefix_Un_distrib) apply (subst P_rec, subst Q_rec, subst Mprefix_Sync_distr_indep[where S="{}", simplified]) apply (intro mono_Det_FD mono_Mprefix_FD) apply (subst Q_rec_sym, simp add:step[simplified]) apply (subst P_rec_sym) using step[simplified] indep by fastforce qed qed from dir1 dir2 show ?thesis using FD_antisym by blast qed section \Synchronous product lemma\ lemma dnorm_par: fixes \\<^sub>1 ::"'\\<^sub>1::type \ 'event::type set" and \\<^sub>2::"'\\<^sub>2::type \ 'event set" and \\<^sub>1 ::"'\\<^sub>1 \ 'event \ '\\<^sub>1" and \\<^sub>2::"'\\<^sub>2 \ 'event \ '\\<^sub>2" defines P: "P \ P\<^sub>n\<^sub>o\<^sub>r\<^sub>m\\\<^sub>1,\\<^sub>1\" (is "P \ fix\(\ X. ?P X)") defines Q: "Q \ P\<^sub>n\<^sub>o\<^sub>r\<^sub>m\\\<^sub>2,\\<^sub>2\" (is "Q \ fix\(\ X. ?Q X)") defines Tr: "\ \ (\(s\<^sub>1,s\<^sub>2). \\<^sub>1 s\<^sub>1 \ \\<^sub>2 s\<^sub>2)" defines Up: "\ \ (\(s\<^sub>1,s\<^sub>2) e. (\\<^sub>1 s\<^sub>1 e, \\<^sub>2 s\<^sub>2 e))" defines S: "S \ P\<^sub>n\<^sub>o\<^sub>r\<^sub>m\\,\\" (is "S \ fix\(\ X. ?S X)") shows "(P s\<^sub>1 || Q s\<^sub>2) = S (s\<^sub>1,s\<^sub>2)" proof - have P_rec: "P = ?P P" using fix_eq[of "(\ X. ?P X)"] P by simp have Q_rec: "Q = ?Q Q" using fix_eq[of "(\ X. ?Q X)"] Q by simp have S_rec: "S = ?S S" using fix_eq[of "(\ X. ?S X)"] S by simp have dir1: "\ s\<^sub>1 s\<^sub>2. (P s\<^sub>1 || Q s\<^sub>2) \\<^sub>F\<^sub>D S (s\<^sub>1, s\<^sub>2)" proof(subst P, subst Q, induct rule:parallel_fix_ind[of "\x y. \ s\<^sub>1 s\<^sub>2. (x s\<^sub>1 || y s\<^sub>2) \\<^sub>F\<^sub>D S (s\<^sub>1,s\<^sub>2)"]) case adm:1 then show ?case by (intro adm_all le_FD_adm) (simp_all add: cont2cont_fun monofunI) next case base:2 then show ?case by (simp add: Sync_BOT) next case step:(3 x y) then show ?case (is "\ s\<^sub>1 s\<^sub>2. ?C s\<^sub>1 s\<^sub>2") proof(intro allI) fix s\<^sub>1 s\<^sub>2 show "?C s\<^sub>1 s\<^sub>2" apply(simp) apply(subst Mprefix_Sync_distr_subset[where S="UNIV", simplified]) apply(subst S_rec, simp add: Tr Up Mprefix_Un_distrib) by (simp add: step) qed qed have dir2: "\ s\<^sub>1 s\<^sub>2. S (s\<^sub>1, s\<^sub>2) \\<^sub>F\<^sub>D (P s\<^sub>1 || Q s\<^sub>2)" proof(subst S, induct rule:fix_ind_k[of "\x. \ s\<^sub>1 s\<^sub>2. x (s\<^sub>1,s\<^sub>2) \\<^sub>F\<^sub>D (P s\<^sub>1 || Q s\<^sub>2)" 1]) case admissibility show ?case by (intro adm_all le_FD_adm) (simp_all add: cont_fun monofunI) next case base_k_steps then show ?case by simp next case step then show ?case (is "\ s\<^sub>1 s\<^sub>2. ?C s\<^sub>1 s\<^sub>2") proof(intro allI) fix s\<^sub>1 s\<^sub>2 have P_rec_sym:"Mprefix (\\<^sub>1 s\<^sub>1) (\e. P (\\<^sub>1 s\<^sub>1 e)) = P s\<^sub>1" using P_rec by metis have Q_rec_sym:"Mprefix (\\<^sub>2 s\<^sub>2) (\e. Q (\\<^sub>2 s\<^sub>2 e)) = Q s\<^sub>2" using Q_rec by metis show "?C s\<^sub>1 s\<^sub>2" apply(simp add: Tr Up) apply(subst P_rec, subst Q_rec, subst Mprefix_Sync_distr_subset[where S="UNIV", simplified]) apply(rule mono_Mprefix_FD) using step by auto qed qed from dir1 dir2 show ?thesis using FD_antisym by blast qed section\Consequences\ \\reachable states from one starting state\ inductive_set \ for \ ::"'\::type \ 'event::type set" and \ ::"'\ \ 'event \ '\" and \\<^sub>0 ::'\ where rbase: "\\<^sub>0 \ \ \ \ \\<^sub>0" | rstep: "s \ \ \ \ \\<^sub>0 \ e \ \ s \ \ s e \ \ \ \ \\<^sub>0" \\Deadlock freeness\ lemma deadlock_free_dnorm_ : fixes \ ::"'\::type \ 'event::type set" and \ ::"'\ \ 'event \ '\" and \\<^sub>0 ::'\ assumes non_reachable_sink: "\s \ \ \ \ \\<^sub>0. \ s \ {}" defines P: "P \ P\<^sub>n\<^sub>o\<^sub>r\<^sub>m\\,\\" (is "P \ fix\(\ X. ?P X)") shows "s \ \ \ \ \\<^sub>0 \ deadlock_free_v2 (P s)" proof(unfold deadlock_free_v2_FD DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P_def, induct arbitrary:s rule:fix_ind) show "adm (\a. \x. x \ \ \ \ \\<^sub>0 \ a \\<^sub>F\<^sub>D P x)" by (simp add: monofun_def) next fix s :: "'\" show "s \ \ \ \ \\<^sub>0 \ \ \\<^sub>F\<^sub>D P s" by simp next fix s :: "'\" and x :: "'event process" have P_rec: "P = ?P P" using fix_eq[of "(\ X. ?P X)"] P by simp assume 1 : "\s. s \ \ \ \ \\<^sub>0 \ x \\<^sub>F\<^sub>D P s" and 2 : "s \ \ \ \ \\<^sub>0 " from 1 2 show "(\ x. (\xa\UNIV \ x) \ SKIP)\x \\<^sub>F\<^sub>D P s" apply (subst P_rec, rule_tac trans_FD[rotated, OF Mprefix_refines_Mndetprefix_FD]) apply simp apply (rule mono_Ndet_FD_left) apply (rule trans_FD[OF mono_Mndetprefix_FD_set[of \\ s\ \UNIV\] mono_Mndetprefix_FD[rule_format, OF 1]]) using non_reachable_sink[rule_format, OF 2] apply assumption by blast (meson \.rstep) qed lemmas deadlock_free_dnorm = deadlock_free_dnorm_[rotated, OF rbase, rule_format] end diff --git a/thys/CSP_RefTK/Properties.thy b/thys/CSP_RefTK/Properties.thy deleted file mode 100644 --- a/thys/CSP_RefTK/Properties.thy +++ /dev/null @@ -1,133 +0,0 @@ -\\ ******************************************************************** - * Project : CSP-RefTK - A Refinement Toolkit for HOL-CSP - * Version : 1.0 - * - * Author : Burkhart Wolff, Safouan Taha, Lina Ye. - * - * This file : Theorems on DF and LF - * - * Copyright (c) 2020 Université Paris-Saclay, France - * - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following - * disclaimer in the documentation and/or other materials provided - * with the distribution. - * - * * Neither the name of the copyright holders nor the names of its - * contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - ******************************************************************************\ - -theory Properties - imports "HOL-CSP.Assertions" -begin - - - -section \Non-terminating Runs\ - -definition non_terminating :: "'a process \ bool" - where "non_terminating P \ RUN UNIV \\<^sub>T P" - -corollary non_terminating_refine_DF: "non_terminating P = DF UNIV \\<^sub>T P" - and non_terminating_refine_CHAOS: "non_terminating P = CHAOS UNIV \\<^sub>T P" - by (simp_all add: DF_all_tickfree_traces1 RUN_all_tickfree_traces1 CHAOS_all_tickfree_traces1 - non_terminating_def trace_refine_def) - -lemma non_terminating_is_right: "non_terminating (P::'a process) \ (\s\\ P. tickFree s)" - apply (rule iffI) - by (auto simp add:non_terminating_def trace_refine_def tickFree_def RUN_all_tickfree_traces1)[1] - (auto simp add:non_terminating_def trace_refine_def RUN_all_tickfree_traces2) - -lemma nonterminating_implies_div_free: "non_terminating P \ \ P = {}" - unfolding non_terminating_is_right - by (metis NT_ND equals0I front_tickFree_charn process_charn tickFree_Cons tickFree_append) - -lemma non_terminating_implies_F: "non_terminating P \ CHAOS UNIV \\<^sub>F P" - apply(auto simp add: non_terminating_is_right failure_refine_def) - using CHAOS_has_all_tickFree_failures F_T by blast - -corollary non_terminating_F: "non_terminating P = CHAOS UNIV \\<^sub>F P" - by (auto simp add:non_terminating_implies_F non_terminating_refine_CHAOS leF_imp_leT) - -corollary non_terminating_FD: "non_terminating P = CHAOS UNIV \\<^sub>F\<^sub>D P" - unfolding non_terminating_F - using div_free_CHAOS nonterminating_implies_div_free leFD_imp_leF - leF_leD_imp_leFD divergence_refine_def non_terminating_F - by fastforce - - -section \Lifelock Freeness\ - -thm lifelock_free_def - -corollary lifelock_free_is_non_terminating: "lifelock_free P = non_terminating P" - unfolding lifelock_free_def non_terminating_FD by rule - -lemma div_free_divergence_refine: - "\ P = {} \ CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV \\<^sub>D P" - "\ P = {} \ CHAOS UNIV \\<^sub>D P" - "\ P = {} \ RUN UNIV \\<^sub>D P" - "\ P = {} \ DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV \\<^sub>D P" - "\ P = {} \ DF UNIV \\<^sub>D P" - by (simp_all add: div_free_CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P div_free_CHAOS div_free_RUN div_free_DF - div_free_DF\<^sub>S\<^sub>K\<^sub>I\<^sub>P divergence_refine_def) - -definition lifelock_free_v2 :: "'a process \ bool" - where "lifelock_free_v2 P \ CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P UNIV \\<^sub>F\<^sub>D P" - -lemma div_free_is_lifelock_free_v2: "lifelock_free_v2 P \ \ P = {}" - using CHAOS\<^sub>S\<^sub>K\<^sub>I\<^sub>P_has_all_failures_Un leFD_imp_leD leF_leD_imp_leFD - div_free_divergence_refine(1) lifelock_free_v2_def - by blast - -lemma lifelock_free_is_lifelock_free_v2: "lifelock_free P \ lifelock_free_v2 P" - by (simp add: leFD_imp_leD div_free_divergence_refine(2) div_free_is_lifelock_free_v2 lifelock_free_def) - -corollary deadlock_free_v2_is_lifelock_free_v2: "deadlock_free_v2 P \ lifelock_free_v2 P" - by (simp add: deadlock_free_v2_implies_div_free div_free_is_lifelock_free_v2) - - -section \New laws\ - -lemma non_terminating_Seq: - "non_terminating P \ (P \<^bold>; Q) = P" - apply(auto simp add: non_terminating_is_right Process_eq_spec D_Seq F_Seq F_T is_processT7) - using process_charn apply blast - using process_charn apply blast - using F_T is_processT5_S2a apply fastforce - using D_T front_tickFree_Nil by blast - -lemma non_terminating_Sync: - "non_terminating P \ lifelock_free_v2 Q \ non_terminating (P \A\ Q)" - apply(auto simp add: non_terminating_is_right div_free_is_lifelock_free_v2 T_Sync) - apply (metis equals0D ftf_Sync1 ftf_Sync21 insertI1 tickFree_def) - apply (meson NT_ND is_processT7_S tickFree_append) - by (metis D_T empty_iff ftf_Sync1 ftf_Sync21 insertI1 tickFree_def) - -lemmas non_terminating_Par = non_terminating_Sync[where A = \UNIV\] - and non_terminating_Inter = non_terminating_Sync[where A = \{}\] - - -end diff --git a/thys/CSP_RefTK/ROOT b/thys/CSP_RefTK/ROOT --- a/thys/CSP_RefTK/ROOT +++ b/thys/CSP_RefTK/ROOT @@ -1,66 +1,65 @@ chapter AFP (***************************************************************************** * * Project : HOL-CSP - A Shallow Embedding of CSP in Isabelle/HOL * Version : 2.0 * * Author : Burkhart Wolff, Safouan Taha & Lina Ye * (Based on HOL-CSP 1.0 by Haykal Tej and Burkhart Wolff) * * This file : The Process Refinement Toolkit CSP_RefTK * * Copyright (c) 2020 Université Paris-Saclay, France * * * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: * * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * * Redistributions in binary form must reproduce the above * copyright notice, this list of conditions and the following * disclaimer in the documentation and/or other materials provided * with the distribution. * * * Neither the name of the copyright holders nor the names of its * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. ******************************************************************************) (* $Id:$ *) -session "CSP_RefTK" = "HOL-CSP" + +session "CSP_RefTK" (AFP) = "HOL-CSP" + description \An Environment for Advanced Refinement Proofs based on Normalization. Together with a proof of the generalized dining philosophers problem.\ - options [timeout = 1200, quick_and_dirty] + options [document = pdf, document_output = "output",timeout = 1200] sessions "HOLCF-Library" theories Introduction - Properties Process_norm CopyBuffer_props DiningPhilosophers Conclusion document_files "root.tex" "adb-long.bib" "root.bib" "figures/session_graph.pdf"