Theory OpSemFDBis
chapter ‹ Failure Divergence Operational Semantics, bis›
theory OpSemFDBis
imports OpSemGenericBis "HOL-Library.LaTeXsugar"
begin
text ‹As announced in the motivations, the first definition we want to try is with \<^term>‹(⊑⇩F⇩D)›.›
abbreviation τ_trans :: ‹'α process ⇒ 'α process ⇒ bool› (infixl ‹⇩F⇩D↝⇩τ› 50)
where ‹P ⇩F⇩D↝⇩τ Q ≡ P ⊑⇩F⇩D Q›
text ‹We now instantiate the locale of \<^theory>‹HOL-CSP_OpSem.OpSemGenericBis›.›
interpretation OpSemGeneric ‹(⇩F⇩D↝⇩τ)›
using trans_FD by unfold_locales
(auto simp add: anti_mono_ready_set_FD mono_AfterExt_FD)
notation event_trans (‹_/ ⇩F⇩D↝_/ _› [50, 3, 51] 50)
notation trace_trans (‹_/ ⇩F⇩D↝⇧*_/ _› [50, 3, 51] 50)
lemma ‹P ⇩F⇩D↝ e P' ⟹ P' ⇩F⇩D↝⇩τ P'' ⟹ P ⇩F⇩D↝ e P''›
‹P ⇩F⇩D↝⇩τ P' ⟹ P' ⇩F⇩D↝ e P'' ⟹ P ⇩F⇩D↝ e P''›
by (fact event_trans_τ_trans τ_trans_event_trans)+
section ‹Operational Semantics Laws›
text ‹\<^const>‹SKIP› law›
lemma ‹SKIP ⇩F⇩D↝✓ STOP›
by (fact SKIP_trans_tick)
text ‹\<^term>‹e → P› laws›
lemma ‹e ∈ A ⟹ □a ∈ A → P a ⇩F⇩D↝(ev e) (P e)›
by (fact ev_trans_Mprefix)
lemma ‹e ∈ A ⟹ ⊓a ∈ A → P a ⇩F⇩D↝(ev e) (P e)›
by (fact ev_trans_Mndetprefix)
lemma ‹e → P ⇩F⇩D↝ (ev e) P›
by (fact ev_trans_prefix)
text ‹\<^term>‹P ⊓ Q› laws›
lemma ‹P ⊓ Q ⇩F⇩D↝⇩τ P›
and ‹P ⊓ Q ⇩F⇩D↝⇩τ Q›
by (fact τ_trans_NdetL τ_trans_NdetR)+
lemma ‹a ∈ A ⟹ (⊓a ∈ A. P a) ⇩F⇩D↝⇩τ P a›
by (fact τ_trans_GlobalNdet)
lemma ‹finite A ⟹ a ∈ A ⟹ (⨅a ∈ A. P a) ⇩F⇩D↝⇩τ P a›
by (fact τ_trans_MultiNdet)
text ‹\<^term>‹μ X. f X› law›
lemma ‹cont f ⟹ P = (μ X. f X) ⟹ P ⇩F⇩D↝⇩τ f P›
by (fact fix_point_τ_trans)
text ‹\<^term>‹P □ Q› laws›
lemma τ_trans_DetL: ‹P ⇩F⇩D↝⇩τ P' ⟹ P □ Q ⇩F⇩D↝⇩τ P' □ Q ›
and τ_trans_DetR: ‹Q ⇩F⇩D↝⇩τ Q' ⟹ P □ Q ⇩F⇩D↝⇩τ P □ Q'›
by simp_all
lemma τ_trans_MultiDet:
‹finite A ⟹ ∀a ∈ A. P a ⇩F⇩D↝⇩τ P' a ⟹
(❙□a ∈ A. P a) ⇩F⇩D↝⇩τ (❙□a ∈ A. P' a)›
by (fact mono_MultiDet_FD)
lemma ‹P ⇩F⇩D↝e P' ⟹ P □ Q ⇩F⇩D↝e P'›
and ‹Q ⇩F⇩D↝e Q' ⟹ P □ Q ⇩F⇩D↝e Q'›
by (fact event_trans_DetL event_trans_DetR)+
lemma ‹finite A ⟹ a ∈ A ⟹ P a ⇩F⇩D↝e Q ⟹ (❙□a ∈ A. P a) ⇩F⇩D↝e Q›
by (fact event_trans_MultiDet)
text ‹\<^term>‹P ❙; Q› laws›
lemma τ_trans_SeqL: ‹P ⇩F⇩D↝⇩τ P' ⟹ P ❙; Q ⇩F⇩D↝⇩τ P' ❙; Q›
by simp
lemma ev_trans_SeqL: ‹P ⇩F⇩D↝(ev e) P' ⟹ P ❙; Q ⇩F⇩D↝(ev e) P' ❙; Q›
by (auto simp add: ready_set_Seq AfterExt_Seq)
lemma τ_trans_SeqR: ‹∃P'. P ⇩F⇩D↝✓ P' ⟹ P ❙; Q ⇩F⇩D↝⇩τ Q›
by (metis mono_Seq_FD SKIP_Seq τ_trans_eq ready_tick_imp_τ_trans_SKIP)
lemma ‹✓ ∈ ready_set P ⟹ Q ⇩F⇩D↝(ev e) Q' ⟹ P ❙; Q ⇩F⇩D↝(ev e) Q'›
by (fact ev_trans_SeqR)
text ‹\<^term>‹P \ B› laws›
lemma τ_trans_Hiding: ‹P ⇩F⇩D↝⇩τ P' ⟹ P \ B ⇩F⇩D↝⇩τ P' \ B›
by (fact mono_Hiding_FD)
lemma ev_trans_Hiding_notin:
‹P ⇩F⇩D↝(ev e) P' ⟹ e ∉ B ⟹ P \ B ⇩F⇩D↝(ev e) P' \ B›
by (metis AfterExt_def After_Hiding_FD_Hiding_After_if_ready_notin mono_Hiding_FD
event_trans_τ_trans event.simps(4) ready_notin_imp_ready_Hiding)
lemma ‹P ⇩F⇩D↝✓ P' ⟹ P \ B ⇩F⇩D↝✓ STOP›
by (fact tick_trans_Hiding)
lemma ev_trans_Hiding_inside:
‹P ⇩F⇩D↝(ev e) P' ⟹ e ∈ B ⟹ P \ B ⇩F⇩D↝⇩τ P' \ B›
by (metis AfterExt_def Hiding_FD_Hiding_After_if_ready_inside
mono_Hiding_FD event.simps(4) trans_FD)
text ‹\<^term>‹Renaming P f› laws›
lemma τ_trans_Renaming: ‹P ⇩F⇩D↝⇩τ P' ⟹ Renaming P f ⇩F⇩D↝⇩τ Renaming P' f›
by (fact mono_Renaming_FD)
lemma tick_trans_Renaming: ‹P ⇩F⇩D↝✓ P' ⟹ Renaming P f ⇩F⇩D↝✓ STOP›
by (simp add: AfterExt_def ready_set_Renaming tick_eq_EvExt)
lemma ev_trans_Renaming:
‹f a = b ⟹ P ⇩F⇩D↝(ev a) P' ⟹ Renaming P f ⇩F⇩D↝(ev b) (Renaming P' f)›
apply (simp add: AfterExt_Renaming Renaming_BOT ready_set_BOT ready_set_Renaming)
apply (intro conjI impI)
apply (meson ev_elem_anteced1 imageI vimageI2)
apply (rule τ_trans_transitivity[of _ ‹Renaming (P afterExt ev a) f›])
apply (solves ‹rule τ_trans_GlobalNdet, simp›)
by (simp add: τ_trans_Renaming)
lemma ‹P ⇩F⇩D↝⇩τ P' ⟹ P ⟦a := b⟧ ⇩F⇩D↝⇩τ P' ⟦a := b⟧›
by (fact τ_trans_Renaming)
lemma ‹P ⇩F⇩D↝✓ P' ⟹ P ⟦a := b⟧ ⇩F⇩D↝✓ STOP›
by (fact tick_trans_Renaming)
lemma ev_trans_RenamingF:
‹P ⇩F⇩D↝(ev a) P' ⟹ P ⟦a := b⟧ ⇩F⇩D↝(ev b) P' ⟦a := b⟧›
by (metis ev_trans_Renaming fun_upd_same)
text ‹\<^term>‹P ⟦S⟧ Q› laws›
lemma τ_trans_SyncL: ‹P ⇩F⇩D↝⇩τ P' ⟹ P ⟦S⟧ Q ⇩F⇩D↝⇩τ P' ⟦S⟧ Q›
and τ_trans_SyncR: ‹Q ⇩F⇩D↝⇩τ Q' ⟹ P ⟦S⟧ Q ⇩F⇩D↝⇩τ P ⟦S⟧ Q'›
by simp_all
lemma ev_trans_SyncL:
‹e ∉ S ⟹ P ⇩F⇩D↝(ev e) P' ⟹ P ⟦S⟧ Q ⇩F⇩D↝(ev e) P' ⟦S⟧ Q ›
and ev_trans_SyncR:
‹e ∉ S ⟹ Q ⇩F⇩D↝(ev e) Q' ⟹ P ⟦S⟧ Q ⇩F⇩D↝(ev e) P ⟦S⟧ Q'›
by (simp_all add: AfterExt_Sync ready_set_Sync image_iff)
lemma ev_trans_SyncLR:
‹⟦e ∈ S; P ⇩F⇩D↝(ev e) P'; Q ⇩F⇩D↝(ev e) Q'⟧ ⟹
P ⟦S⟧ Q ⇩F⇩D↝(ev e) P' ⟦S⟧ Q'›
by (simp add: AfterExt_Sync ready_set_Sync)
text ‹From here we slightly defer from Roscoe's laws for \<^const>‹Sync›:
we obtain the following rules for \<^const>‹SKIP› instead of \<^const>‹STOP›.›
lemma tick_trans_SyncL: ‹P ⇩F⇩D↝✓ P' ⟹ P ⟦S⟧ Q ⇩F⇩D↝⇩τ SKIP ⟦S⟧ Q›
and tick_trans_SyncR: ‹Q ⇩F⇩D↝✓ Q' ⟹ P ⟦S⟧ Q ⇩F⇩D↝⇩τ P ⟦S⟧ SKIP›
by (simp_all add: ready_tick_imp_τ_trans_SKIP)
lemma tick_trans_SKIP_Sync_SKIP: ‹SKIP ⟦S⟧ SKIP ⇩F⇩D↝✓ STOP›
by (simp add: SKIP_trans_tick Sync_SKIP_SKIP)
lemma τ_trans_SKIP_Sync_SKIP: ‹SKIP ⟦S⟧ SKIP ⇩F⇩D↝⇩τ SKIP›
by (simp add: Sync_SKIP_SKIP)
text ‹\<^term>‹P ⊳ Q› laws›
lemma Sliding_τ_trans_left: ‹P ⇩F⇩D↝⇩τ P' ⟹ P ⊳ Q ⇩F⇩D↝⇩τ P' ⊳ Q›
unfolding Sliding_def by simp
lemma ‹P ⇩F⇩D↝e P' ⟹ P ⊳ Q ⇩F⇩D↝e P'›
by (fact Sliding_event_transL)
lemma ‹P ⊳ Q ⇩F⇩D↝⇩τ Q›
by (fact Sliding_τ_transR)
text ‹\<^term>‹P △ Q› laws›
lemma Interrupt_τ_trans_left: ‹P ⇩F⇩D↝⇩τ P' ⟹ P △ Q ⇩F⇩D↝⇩τ P' △ Q›
by (simp add: mono_Interrupt_FD)
lemma Interrupt_τ_trans_right: ‹Q ⇩F⇩D↝⇩τ Q' ⟹ P △ Q ⇩F⇩D↝⇩τ P △ Q'›
by (simp add: mono_Interrupt_FD)
lemma Interrupt_ev_trans_left:
‹P ⇩F⇩D↝(ev e) P' ⟹ P △ Q ⇩F⇩D↝(ev e) P' △ Q›
by (simp add: AfterExt_def After_Interrupt Interrupt_τ_trans_left ready_set_Interrupt)
lemma Interrupt_ev_trans_right: ‹Q ⇩F⇩D↝(ev e) Q' ⟹ P △ Q ⇩F⇩D↝(ev e) Q'›
by (simp add: AfterExt_def After_Interrupt ready_set_Interrupt)
text ‹\<^term>‹P Θ a ∈ A. Q a› laws›
lemma Throw_τ_trans_left:
‹P ⇩F⇩D↝⇩τ P' ⟹ P Θ a ∈ A. Q a ⇩F⇩D↝⇩τ P' Θ a ∈ A. Q a›
by (simp add: mono_Throw_FD)
lemma Throw_τ_trans_right:
‹∀a ∈ A. Q a ⇩F⇩D↝⇩τ Q' a ⟹ P Θ a ∈ A. Q a ⇩F⇩D↝⇩τ P Θ a ∈ A. Q' a›
by (simp add: mono_Throw_FD)
lemma Throw_event_trans_left:
‹P ⇩F⇩D↝e P' ⟹ e ∉ ev ` A ⟹ P Θ a ∈ A. Q a ⇩F⇩D↝e (P' Θ a ∈ A. Q a)›
apply (simp add: AfterExt_Throw ready_set_Throw image_iff split: event.split)
apply (intro conjI impI)
by (metis AfterExt_def Throw_τ_trans_left event.simps(4))
(solves ‹simp add: Throw_STOP tick_trans_iff›)
lemma Throw_ev_trans_right:
‹P ⇩F⇩D↝(ev e) P' ⟹ e ∈ A ⟹ P Θ a ∈ A. Q a ⇩F⇩D↝(ev e) (Q e)›
by (simp add: AfterExt_Throw ready_set_Throw split: event.split)
lemma ‹tickFree s ⟹ ⊥ ⇩F⇩D↝⇧*s P›
by (fact BOT_trace_trans_tickFree_anything)
section ‹Reality Checks›
lemma ‹STOP ⇩F⇩D↝⇧*s P ⟷ s = [] ∧ P = STOP›
by (fact STOP_trace_trans_iff)
lemma SKIP_trace_trans_iff :
‹SKIP ⇩F⇩D↝⇧*s P ⟷ s = [] ∧ P = SKIP ∨ s = [✓] ∧ P = STOP›
by (simp add: τ_trans_imp_leF_imp_SKIP_trace_trans_iff leFD_imp_leF)
lemma F_iff_exists_trans :
‹(s, X) ∈ ℱ P ⟷ (∃P'. (P ⇩F⇩D↝⇧*s P') ∧ X ∈ ℛ P')›
using F_imp_exists_trace_trans leFD_imp_leF trace_trans_imp_F_if_τ_trans_imp_leF by blast
lemma T_iff_exists_trans : ‹s ∈ 𝒯 P ⟷ (∃P'. P ⇩F⇩D↝⇧*s P')›
by (meson T_imp_exists_trace_trans leFD_imp_leF leF_imp_leT trace_trans_imp_T_if_τ_trans_imp_leT)
lemma tickFree_imp_D_iff_trace_trans_BOT:
‹tickFree s ⟹ s ∈ 𝒟 P ⟷ P ⇩F⇩D↝⇧*s ⊥›
using D_imp_trace_trans_BOT leFD_imp_leD trace_trans_BOT_imp_D_if_τ_trans_imp_leD by blast
lemma D_iff_trace_trans_BOT:
‹s ∈ 𝒟 P ⟷ (if tickFree s then P ⇩F⇩D↝⇧*s ⊥ else P ⇩F⇩D↝⇧*(butlast s) ⊥)›
by (metis tickFree_if_trans_trans_not_STOP STOP_neq_BOT
append_butlast_last_id front_tickFree_butlast
front_tickFree_single is_processT tickFree_butlast
tickFree_imp_D_iff_trace_trans_BOT)
section ‹Other Results›
lemma trace_trans_ready_set_subset_ready_set_AfterTrace:
‹P ⇩F⇩D↝⇧*s Q ⟹ ready_set Q ⊆ ready_set (P afterTrace s)›
by (metis T_iff_exists_trans T_imp_trace_trans_iff_AfterTrace_τ_trans τ_trans_anti_mono_ready_set)
lemma trace_trans_imp_ready_set:
‹P ⇩F⇩D↝⇧*(s @ e # t) Q ⟹ e ∈ ready_set (P afterTrace s)›
using T_iff_exists_trans ready_set_AfterTrace by blast
lemma AfterTrace_τ_trans_if_τ_trans_imp_leT :
‹(P ⇩F⇩D↝⇧*s Q) ⟷ s ∈ 𝒯 P ∧ P afterTrace s ⇩F⇩D↝⇩τ Q›
using T_iff_exists_trans T_imp_trace_trans_iff_AfterTrace_τ_trans by blast
lemma ‹deadlock_free P ⟷ DF UNIV ⇩F⇩D↝⇩τ P›
by (simp add: deadlock_free_def)
lemma ‹deadlock_free⇩S⇩K⇩I⇩P P ⟷ DF⇩S⇩K⇩I⇩P UNIV ⇩F⇩D↝⇩τ P›
by (fact deadlock_free⇩S⇩K⇩I⇩P_FD)
section ‹Summary: Operational Rules›
text ‹In this section, we will just write down the operational
laws that we have proven in a fancy way.›
paragraph ‹Absorbance rules›
text ‹\begin{center}
@{thm[mode=Rule] event_trans_τ_trans} \qquad
@{thm[mode=Rule] τ_trans_event_trans}
\end{center}›
paragraph ‹\<^const>‹SKIP› rule›
text ‹\begin{center}
@{thm[mode=Axiom] SKIP_trans_tick}
\end{center}›
paragraph ‹\<^term>‹e → P› rules›
text ‹\begin{center}
@{thm[mode=Rule, eta_contract=false] ev_trans_Mprefix} \qquad
@{thm[mode=Rule, eta_contract=false] ev_trans_Mndetprefix}
@{thm[mode=Axiom] ev_trans_prefix}
\end{center}›
paragraph ‹\<^const>‹Ndet› rules›
text ‹\begin{center}
@{thm[mode=Axiom] τ_trans_NdetL} \qquad
@{thm[mode=Axiom] τ_trans_NdetR}
@{thm[mode=Rule, eta_contract=false] τ_trans_GlobalNdet}
\end{center}›
paragraph ‹\<^term>‹μ X. f X› rule›
text ‹\begin{center}
@{thm[mode=Rule] fix_point_τ_trans}
\end{center}›
paragraph ‹\<^const>‹Det› rules›
text ‹\begin{center}
@{thm[mode=Rule] τ_trans_DetL} \qquad
@{thm[mode=Rule] τ_trans_DetR}
@{thm[mode=Rule] event_trans_DetL} \qquad
@{thm[mode=Rule] event_trans_DetR}
\end{center}›
paragraph ‹\<^const>‹Seq› rules›
text ‹\begin{center}
@{thm[mode=Rule] τ_trans_SeqL} \qquad
@{thm[mode=Rule] ev_trans_SeqL}
@{thm[mode=Rule] τ_trans_SeqR}
\end{center}›
paragraph ‹\<^const>‹Hiding› rules›
text ‹\begin{center}
@{thm[mode=Rule] τ_trans_Hiding} \qquad
@{thm[mode=Rule] tick_trans_Hiding}
@{thm[mode=Rule] ev_trans_Hiding_notin} \qquad
@{thm[mode=Rule] ev_trans_Hiding_inside}
\end{center}›
paragraph ‹\<^const>‹Renaming› rules›
text ‹\begin{center}
@{thm[mode=Rule] τ_trans_Renaming} \qquad
@{thm[mode=Rule] tick_trans_Renaming}
@{thm[mode=Rule] ev_trans_Renaming}
\end{center}›
paragraph ‹\<^const>‹Sync› rules›
text ‹\begin{center}
@{thm[mode=Rule] τ_trans_SyncL} \qquad
@{thm[mode=Rule] τ_trans_SyncR}
@{thm[mode=Rule] ev_trans_SyncL} \qquad
@{thm[mode=Rule] ev_trans_SyncR}
@{thm[mode=Rule] ev_trans_SyncLR}
@{thm[mode=Rule] tick_trans_SyncL} \qquad
@{thm[mode=Rule] tick_trans_SyncR}
@{thm[mode=Axiom] τ_trans_SKIP_Sync_SKIP}
\end{center}›
paragraph ‹\<^const>‹Sliding› rules›
text ‹\begin{center}
@{thm[mode=Rule] Sliding_τ_trans_left} \qquad
@{thm[mode=Rule] Sliding_event_transL}
@{thm[mode=Axiom] Sliding_τ_transR}
\end{center}›
paragraph ‹\<^const>‹Interrupt› rules›
text ‹\begin{center}
@{thm[mode=Rule] Interrupt_τ_trans_left} \qquad
@{thm[mode=Rule] Interrupt_τ_trans_right}
@{thm[mode=Rule] Interrupt_ev_trans_left} \qquad
@{thm[mode=Rule] Interrupt_ev_trans_right}
\end{center}›
paragraph ‹\<^const>‹Throw› rules›
text ‹\begin{center}
@{thm[mode=Rule, eta_contract=false] Throw_τ_trans_left} \qquad
@{thm[mode=Rule, eta_contract=false] Throw_τ_trans_right}
@{thm[mode=Rule, eta_contract=false] Throw_event_trans_left} \qquad
@{thm[mode=Rule, eta_contract=false] Throw_ev_trans_right}
\end{center}›
end