Quelle  Process.thy

(*<*)
―‹ ********************************************************************
 * Project : HOL-CSP - A Shallow Embedding of CSP in Isabelle/HOL
 * Version : 2.0
 *
 * Author : Benoît Ballenghien, Safouan Taha, Burkhart Wolff, Lina Ye.
 * (Based on HOL-CSP 1.0 by Haykal Tej and Burkhart Wolff)
 *
 * This file : The notion of processes
 *
 * Copyright (c) 2009 Université Paris-Sud, France
 * Copyright (c) 2025 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‹The Notion of Processes›

text‹As mentioned earlier, we base the theory of CSP on HOLCF, a Isabelle/HOL library
  a theory of continuous functions, fixpoint induction and recursion.›

(*<*)
theory Process
  imports HOLCF "HOL-Library.Prefix_Order" "HOL-Eisbach.Eisbach"
begin
  (*>*)

text‹HOLCF sets the default type class to @{class cpo}, while our
  theory establishes links between standard types and @{class pcpo}
 . Consequently, we reset the default type class to the default in HOL.›

default_sort type

section‹Pre-Requisite: Basic Traces and tick-Freeness›

text‹The denotational semantics of CSP assumes a distinguishable
  event, called \verb+tick+ and written $\checkmark$, that is required
  occur only in the end of traces in order to signalize successful termination of
  process. (In the original text of Hoare, this treatment was more
  and lead to foundational problems: the process invariant
  not be established for the sequential composition operator
  CSP; see cite‹"tej.ea:corrected:1997"› for details.)›

text ‹From the Isabelle-2025 version on, the classical constant tick (‹🍋›) of the CSP theory
 has been replaced by a parameterized version carrying a kind of return value.›

datatype ('a, 'r) event_ptick =
    is_ev   : ev   (of_ev   : 'a)
  | is_tick : tick (of_tick : 'r) (‹🍋'(_')›)


text ‹This type 🍋‹('a, 'r) event_ptick› is of course isomorphic to the sum type ??‹'a + 'r›.›
text ‹``ptick'' stands for parameterized tick, and we introduce the type synonym for
 the classical process event type.›

type_synonym 'a event = ‹('a, unit) event_ptick›

abbreviation tick_unit :: ‹'a event› (‹🍋›) where ‹🍋 ≡ 🍋(())›

definition sum_of_event_ptick :: ‹('a, 'r) event_ptick ==> 'a + 'r›
  where ‹sum_of_event_ptick e ≡ case e of ev a ==> Inl a | 🍋(r) ==> Inr r›

definition event_{ptick_of_sum} :: ‹'a + 'r ==> ('a, 'r) event_ptick›
  where ‹event_{ptick_of_sum} s ≡ case s of Inl a ==> ev a | Inr r ==> 🍋(r)›

lemma type_definition_event_ptick : ‹type_definition sum_of_event_ptick event_{ptick_of_sum} UNIV›
proof unfold_locales
  show ‹sum_of_event_ptick s ∈ UNIV› for s :: ‹('a, 'r) event_ptick› by simp
next
  show ‹event_{ptick_of_sum} (sum_of_event_ptick e) = e› for e :: ‹('a, 'r) event_ptick›
    by (cases e) (simp_all add: event_{ptick_of_sum_def} sum_of_event_{ptick_def})
next
  show ‹sum_of_event_ptick (event_{ptick_of_sum} s) = s› for s :: ‹'a + 'r›
    by (cases s) (simp_all add: event_{ptick_of_sum_def} sum_of_event_{ptick_def})
qed

setup_lifting type_definition_event_ptick

lemma range_tick_Un_range_ev_is_UNIV [simp] : ‹range tick ∪ range ev = UNIV›
  by (metis UNIV_eq_I UnCI event_ptick.exhaust rangeI)

text ‹The generalization is done in a very straightforward way:
 the old version is recovered by considering 🍋‹('a, unit) event_ptick›.›

(* 
typedef ('a, 'r) event\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k = \<open>UNIV :: ('a + 'r) set\<close>
  morphisms event_of_sum sum_of_event by simp

setup_lifting type_definition_event

lift_definition ev :: \<open>'a \<Rightarrow> ('a, 'r) event\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k\<close> is \<open>\<lambda>a. Inl a\<close> .
lift_definition tick :: \<open>'r \<Rightarrow> ('a, 'r) event\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k\<close> (\<open>\<checkmark>'(_')\<close>) is \<open>\<lambda>r. Inr r\<close> .

free_constructors event for is_ev : ev of_ev | is_tick : tick of_tick
proof transfer
  show \<open>(\<And>x1. y = Inl x1 \<Longrightarrow> P) \<Longrightarrow> (\<And>x2. y = Inr x2 \<Longrightarrow> P) \<Longrightarrow> P\<close> for y :: \<open>'a + 'b\<close> and P
    by (metis isl_def sum.collapse(2))
next
  show \<open>ev x = ev y \<longleftrightarrow> x = y\<close> for x y :: 'a by (metis ev.rep_eq sum.inject(1))
next
  show \<open>\<checkmark>(x) = \<checkmark>(y) \<longleftrightarrow> x = y\<close> for x y :: 'r by (metis sum.inject(2) tick.rep_eq)
next
  show \<open>ev x \<noteq> \<checkmark>(y)\<close> for x :: 'a and y :: 'r
    by (metis Inl_Inr_False ev.rep_eq tick.rep_eq)
qed

this looks more natural, but does not work fine with the typedef of process
 *)

lemma not_is_ev   [simp] : ‹¬ is_ev e ⟷ is_tick e›
  and not_is_tick [simp] : ‹¬ is_tick e ⟷ is_ev e›
  by (use event_ptick.exhaust_disc in blast)+


type_synonym ('a, 'r) trace_ptick = ‹('a, 'r) event_ptick list›

text ‹We recover the classical version with 🍋‹unit›.›

type_synonym 'a trace = ‹('a, unit) trace_ptick›


text‹We chose as standard ordering on traces the prefix ordering.›


text‹Some facts on the prefix ordering.›

lemma nil_le     [simp]: ‹[] ≤ s›
  and nil_le2    [simp]: ‹s ≤ [] ⟷ s = []›
  and nil_less   [simp]: ‹¬ t < []›
  and nil_less2  [simp]: ‹[] < t @ [a]›
  and less_self  [simp]: ‹t < t @ [a]›
  and le_cons    [simp]: ‹a # s ≤ a # t ⟷ s ≤ t›
  and le_append  [simp]: ‹b @ s ≤ b @ t ⟷ s ≤ t›
  and less_cons  [simp]: ‹a # s < a # t ⟷ s < t›
  and less_append[simp]: ‹b @ s < b @ t ⟷ s < t›

and   le_length_mono: ‹s ≤ t ==> length s ≤ length t›
and less_length_mono: ‹s < t ==> length s < length t›
and   le_tail: ‹s ≠ [] ==> s ≤ t ==> tl s ≤ tl t›
and less_tail: ‹s ≠ [] ==> s < t ==> tl s < tl t›
              apply (simp_all add: less_eq_list_def less_list_def prefix_length_le)
    apply (metis prefix_length_less prefix_order.dual_order.not_eq_order_implies_strict)
   apply (metis prefix_def tl_append2)
  by (metis prefix_def prefix_order.eq_iff self_append_conv tl_append2)


lemma le_same_imp_eq_or_less: ‹(s :: 'a list) ≤ u ==> t ≤ u ==> t = s ∨ s < t ∨ t < s›
  by (metis less_eq_list_def linorder_le_cases nless_le prefix_length_prefix)


lemma append_eq_first_pref_spec: ‹s @ t = r @ [x] ==> t ≠ [] ==> s ≤ r›
  by (metis butlast_append butlast_snoc less_eq_list_def prefix_def)


lemma prefixes_fin: ‹finite {t. t ≤ s} ∧ card {t. t ≤ s} = Suc (length s)›
proof (induct s)
  show ‹finite {t. t ≤ []} ∧ card {t. t ≤ []} = Suc (length [])› by simp
next
  case (Cons x s)
  have * : ‹{t. t ≤ x # s} = {[]} ∪ (λt. x # t) ` {t. t ≤ s}›
    by (simp add: image_def less_eq_list_def set_eq_iff)
      (meson Sublist.prefix_Cons)
  show ‹finite {t. t ≤ x # s} ∧ card {t. t ≤ x # s} = Suc (length (x # s))›
  proof (intro conjI)
    show ‹finite {t. t ≤ x # s}› by (simp add: "*" Cons.hyps)
  next
    have ‹finite ((λt. x # t) ` {t. t ≤ s})› by (simp add: Cons.hyps)
    show ‹card {t. t ≤ x # s} = Suc (length (x # s))›
      by (subst card_Un_disjoint[of ‹{[]}› ‹(λt. x # t) ` {t. t ≤ s}›, folded "*"])
        (auto simp add: card_image Cons.hyps)   
  qed
qed


lemma sublists_fin: ‹finite {t. ∃t1 t2. s = t1 @ t @ t2}›
proof (induct s)
  show ‹finite {t. ∃t1 t2. [] = t1 @ t @ t2}› by simp
next
  case (Cons x s)
  have ‹{t. t ≤ x # s} = {t. ∃t2. x # s = t @ t2}›
    by (simp add: less_eq_list_def prefix_def)
  with prefixes_fin[of ‹x # s›] have ‹finite {t. ∃t2. x # s = t @ t2}› by simp
  have ‹{t. ∃t1 t2. x # s = t1 @ t @ t2} ⊆
 {t. ∃t1 t2. s = t1 @ t @ t2} ∪ {t. ∃t2. x # s = t @ t2}›
    by (simp add: subset_iff) (meson Cons_eq_append_conv)
  show ‹finite {t. ∃t1 t2. x # s = t1 @ t @ t2}›
    by (rule finite_subset[OF ‹?this›], rule finite_UnI)
      (simp_all add: Cons.hyps ‹finite {t. ∃t2. x # s = t @ t2}›)
qed


lemma suffixes_fin: ‹finite {t. ∃t1. s = t1 @ t}›
  by (rule finite_subset[of _ ‹{t. ∃t1 t2. s = t1 @ t @ t2}›];
      simp add: subset_iff sublists_fin) blast 


text‹For the process invariant, it is a key element to
  the notion of traces to traces that may only contain
  tick event at the very end. This is captured by the definition
  the predicate \verb+front_tickFree+ and its stronger version
 verb+tickFree+. Here is the theory of this concept.›

definition tickFree :: ‹('a, 'r) trace_ptick ==> bool› (‹tF›)
  where ‹tF s ≡ range tick ∩ set s = {}›

definition front_tickFree :: ‹('a, 'r) trace_ptick ==> bool› (‹ftF›)
  where ‹ftF s ≡ s = [] ∨ tickFree (tl (rev s))›

lemma tickFree_Nil        [simp] : ‹tF []›
  and tickFree_Cons_iff   [simp] : ‹tF (a # t) ⟷ is_ev a ∧ tF t›
  and tickFree_append_iff [simp] : ‹tF (s @ t) ⟷ tF s ∧ tF t›
  and tickFree_rev_iff    [simp] : ‹tF (rev t) ⟷ tF t›
  and non_tickFree_tick   [simp] : ‹¬ tF [🍋(r)]›
  by (cases a; auto simp add: tickFree_def)+

lemma tickFree_iff_is_map_ev : ‹tF t ⟷ (∃u. t = map ev u)›
  by (induct t) (simp_all add: Cons_eq_map_conv is_ev_def)

lemma front_tickFree_Nil   [simp] : ‹ftF []›
  and front_tickFree_single[simp] : ‹ftF [a]›
  by (simp_all add: front_tickFree_def)


lemma tickFree_tl : ‹tF s ==> tF (tl s)›
  by (cases s) simp_all

lemma non_tickFree_imp_not_Nil: ‹¬ tF s ==> s ≠ []›
  using tickFree_Nil by blast

lemma tickFree_butlast: ‹tF s ⟷ tF (butlast s) ∧ (s ≠ [] ⟶ is_ev (last s))›
  by (induct s) simp_all

lemma front_tickFree_iff_tickFree_butlast: ‹ftF s ⟷ tF (butlast s)›
  by (induct s) (auto simp add: front_tickFree_def)

lemma front_tickFree_Cons_iff: ‹ftF (a # s) ⟷ s = [] ∨ is_ev a ∧ ftF s›
  by (simp add: front_tickFree_iff_tickFree_butlast)

lemma front_tickFree_append_iff:
  ‹ftF (s @ t) ⟷ (if t = [] then ftF s else tF s ∧ ftF t)›
  by (simp add: butlast_append front_tickFree_iff_tickFree_butlast)

lemma tickFree_imp_front_tickFree [simp] : ‹tF s ==> ftF s›
  by (simp add: front_tickFree_def tickFree_tl)

lemma front_tickFree_charn: ‹ftF s ⟷ s = [] ∨ (∃a t. s = t @ [a] ∧ tF t)›
  by (cases s rule: rev_cases) (simp_all add: front_tickFree_def)


lemma nonTickFree_n_frontTickFree: ‹¬ tF s ==> ftF s ==> ∃t r. s = t @ [🍋(r)]›
  by (metis event_ptick.disc(1) event_ptick.exhaust front_tickFree_append_iff list.distinct(1)
      rev_exhaust tickFree_Cons_iff tickFree_Nil tickFree_append_iff)

lemma front_tickFree_dw_closed : ‹ftF (s @ t) ==> ftF s›
  by (metis front_tickFree_append_iff tickFree_imp_front_tickFree)

lemma front_tickFree_append: ‹tF s ==> ftF t ==> ftF (s @ t)›
  by (simp add: front_tickFree_append_iff)

lemma tickFree_imp_front_tickFree_snoc: ‹tF s ==> ftF (s @ [a])›
  by (simp add: front_tickFree_append)

lemma front_tickFree_nonempty_append_imp: ‹ftF (t @ r) ==> r ≠ [] ==> tF t ∧ ftF r›
  by (simp add: front_tickFree_append_iff)

lemma tickFree_map_ev [simp] : ‹tF (map ev t)›
  by (induct t) simp_all

lemma tickFree_map_tick_iff [simp] : ‹tF (map tick t) ⟷ t = []›
  by (induct t) simp_all

lemma front_tickFree_map_tick_iff [simp] : ‹ftF (map tick t) ⟷ t = [] ∨ (∃r. t = [r])›
  by (simp add: front_tickFree_iff_tickFree_butlast map_butlast[symmetric])
    (metis append_Nil append_butlast_last_id butlast.simps(1, 2))

― ‹term‹map ev (map f t)› if automatically simplified into term‹map (ev ∘ f) t› by the
 simplified, so we need to add the following versions.›

lemma tickFree_map_ev_comp [simp] : ‹tF (map (ev ∘ f) t)›
  by (metis list.map_comp tickFree_map_ev)

lemma tickFree_map_tick_comp_iff [simp] : ‹tF (map (tick ∘ f) t) ⟷ t = []›
  by (fold map_map, unfold tickFree_map_tick_iff) simp

lemma front_tickFree_map_tick_comp_iff [simp] : ‹ftF (map (tick ∘ f) t) ⟷ t = [] ∨ (∃r. t = [r])›
  by (fold map_map, unfold front_tickFree_map_tick_iff)
    (simp add: map_eq_Cons_conv)



section‹ Basic Types, Traces, Failures and Divergences ›

type_synonym ('a, 'r) refusal_ptick = ‹('a, 'r) event_ptick set›
type_synonym 'a refusal = ‹('a, unit) refusal_ptick›
type_synonym ('a, 'r) failure_ptick = ‹('a, 'r) trace_ptick × ('a, 'r) refusal_ptick›
type_synonym 'a failure = ‹('a, unit) failure_ptick›
type_synonym ('a, 'r) divergence_ptick = ‹('a, 'r) trace_ptick›
type_synonym 'a divergence = ‹('a, unit) divergence_ptick›
type_synonym ('a, 'r) process₀ = ‹('a, 'r) failure_ptick set × ('a, 'r) divergence_ptick set›

definition FAILURES :: ‹('a, 'r) process₀ ==> ('a, 'r) failure_ptick set›
  where ‹FAILURES P ≡ fst P›

definition TRACES :: ‹('a, 'r) process₀ ==> ('a, 'r) trace_ptick set›
  where ‹TRACES P ≡ {tr. ∃ref. (tr, ref) ∈ FAILURES P}›

definition DIVERGENCES :: ‹('a, 'r) process₀ ==> ('a, 'r) divergence_ptick set›
  where ‹DIVERGENCES P ≡ snd P›

definition REFUSALS :: ‹('a, 'r) process₀ ==> ('a, 'r) refusal_ptick set›
  where ‹REFUSALS P ≡ {ref. ([], ref) ∈ FAILURES P}›

section‹ The Process Type Invariant ›

definition is_process :: ‹('a, 'r) process₀ ==> bool› where
  ‹is_process P ≡
 ([], {}) ∈ FAILURES P ∧
 (∀s X. (s, X) ∈ FAILURES P ⟶ ftF s) ∧
 (∀s t. (s @ t, {}) ∈ FAILURES P ⟶ (s, {}) ∈ FAILURES P) ∧
 (∀s X Y. (s, Y) ∈ FAILURES P ∧ X ⊆ Y ⟶ (s, X) ∈ FAILURES P) ∧
 (∀s X Y. (s, X) ∈ FAILURES P ∧ (∀c. c ∈ Y ⟶ (s @ [c], {}) ∉ FAILURES P)
 ⟶ (s, X ∪ Y) ∈ FAILURES P) ∧
 (∀s r X. (s @ [🍋(r)], {}) ∈ FAILURES P ⟶ (s, X - {🍋(r)}) ∈ FAILURES P) ∧
 (∀s t. s ∈ DIVERGENCES P ∧ tF s ∧ ftF t ⟶ s @ t ∈ DIVERGENCES P) ∧
 (∀s X. s ∈ DIVERGENCES P ⟶ (s, X) ∈ FAILURES P) ∧
 (∀s r. s @ [🍋(r)] ∈ DIVERGENCES P ⟶ s ∈ DIVERGENCES P)›


lemma is_process_spec:
  ‹is_process P ⟷
 ([], {}) ∈ FAILURES P ∧
 (∀s X. (s, X) ∈ FAILURES P ⟶ ftF s) ∧
 (∀s t. (s @ t, {}) ∉ FAILURES P ∨ (s, {}) ∈ FAILURES P) ∧
 (∀s X Y. (s, Y) ∉ FAILURES P ∨ ¬ X ⊆ Y ∨ (s, X) ∈ FAILURES P) ∧
 (∀s X Y. (s, X) ∈ FAILURES P ∧ (∀c. c ∈ Y ⟶ (s @ [c], {}) ∉ FAILURES P)
 ⟶ (s, X ∪ Y) ∈ FAILURES P) ∧
 (∀s r X. (s @ [🍋(r)], {}) ∈ FAILURES P ⟶ (s, X - {🍋(r)}) ∈ FAILURES P) ∧
 (∀s t. s ∉ DIVERGENCES P ∨ ¬ tF s ∨ ¬ ftF t ∨ s @ t ∈ DIVERGENCES P) ∧
 (∀s X. s ∉ DIVERGENCES P ∨ (s, X) ∈ FAILURES P) ∧
 (∀s r. s @ [🍋(r)] ∉ DIVERGENCES P ∨ s ∈ DIVERGENCES P)›
  by (simp only: is_process_def HOL.nnf_simps(1)
      HOL.nnf_simps(3) [symmetric] HOL.imp_conjL[symmetric])

lemma Process_eqI :
  ‹FAILURES P = FAILURES Q ==> DIVERGENCES P = DIVERGENCES Q ==> P = Q›
  by (metis DIVERGENCES_def FAILURES_def prod_eq_iff)

lemma process_eq_spec:
  ‹P = Q ⟷ FAILURES P = FAILURES Q ∧ DIVERGENCES P = DIVERGENCES Q›
  by (meson Process_eqI)


lemma process_surj_pair: ‹(FAILURES P, DIVERGENCES P) = P›
  by(auto simp: FAILURES_def DIVERGENCES_def)

lemma Fa_eq_imp_Tr_eq: ‹FAILURES P = FAILURES Q ==> TRACES P = TRACES Q›
  by (auto simp: FAILURES_def DIVERGENCES_def TRACES_def) 



lemma is_process1 : ‹([], {}) ∈ FAILURES P›
  and is_process2 : ‹(s, X) ∈ FAILURES P ==> ftF s›
  and is_process3 : ‹(s @ t, {}) ∈ FAILURES P ==> (s, {}) ∈ FAILURES P›
  and is_process4 : ‹[is_process P; (s, Y) ∈ FAILURES P; X ⊆ Y] ==> (s, X) ∈ FAILURES P›
  and is_process5 : ‹[is_process P; (s, X) ∈ FAILURES P; ∀c. c ∈ Y ⟶ (s @ [c], {}) ∉ FAILURES P]
 ==> (s, X ∪ Y) ∈ FAILURES P›
  and is_process6 : ‹(s @ [🍋(r)], {}) ∈ FAILURES P ==> (s, X - {🍋(r)}) ∈ FAILURES P›
  and is_process7 : ‹[s ∈ DIVERGENCES P; tF s; ftF t] ==> s @ t ∈ DIVERGENCES P›
  and is_process8 : ‹s ∈ DIVERGENCES P ==> (s, X) ∈ FAILURES P›
  and is_process9 : ‹s @ [🍋(r)] ∈ DIVERGENCES P ==> s ∈ DIVERGENCES P›
  if ‹is_process P›
  using ‹is_process P› unfolding is_process_def by metis+


(* 
lemma is_process3_S_pref: \<open>\<lbrakk>is_process P; (t, {}) \<in> FAILURES P; s \<le> t\<rbrakk> \<Longrightarrow> (s, {}) \<in> FAILURES P\<close>
  by (metis prefixE is_process3)

lemma is_process4: \<open>is_process P \<Longrightarrow> \<forall>s X Y. (s, Y) \<notin> FAILURES P \<or> \<not> X \<subseteq> Y \<or> (s, X) \<in> FAILURES P\<close>
  by (simp only: is_process_spec) simp

lemma is_process4_S: \<open>\<lbrakk>is_process P; (s, Y) \<in> FAILURES P; X \<subseteq> Y\<rbrakk> \<Longrightarrow> (s, X) \<in> FAILURES P\<close>
  by (drule is_process4, auto)

lemma is_process4_S1: \<open>\<lbrakk>is_process P; x \<in> FAILURES P; X \<subseteq> snd x\<rbrakk> \<Longrightarrow> (fst x, X) \<in> FAILURES P\<close>
  by (drule is_process4_S, auto)

lemma is_process5:
  \<open>is_process P \<Longrightarrow> \<forall>s X Y. (s, X) \<in> FAILURES P \<and> (\<forall>c. c \<in> Y \<longrightarrow> (s @ [c], {}) \<notin> FAILURES P)
                            \<longrightarrow> (s, X \<union> Y) \<in> FAILURES P\<close>
  by (drule is_process_spec[THEN iffD1],metis)

lemma is_process5_S:
  \<open>\<lbrakk>is_process P; (sa, X) \<in> FAILURES P; \<forall>c. c \<in> Y \<longrightarrow> (sa @ [c], {}) \<notin> FAILURES P\<rbrakk>
   \<Longrightarrow> (sa, X \<union> Y) \<in> FAILURES P\<close>
  by (drule is_process5, metis)

lemma is_process5_S1:
  \<open>\<lbrakk>is_process P; (sa, X) \<in> FAILURES P; (sa, X \<union> Y) \<notin> FAILURES P\<rbrakk>
   \<Longrightarrow> \<exists>c. c \<in> Y \<and> (sa @ [c], {}) \<in> FAILURES P\<close>
  by (erule contrapos_np, drule is_process5_S, simp_all)

lemma is_process6: \<open>is_process P \<Longrightarrow> \<forall>s X. (s @ [\<checkmark>(r)], {}) \<in> FAILURES P \<longrightarrow> (s, X - {\<checkmark>(r)}) \<in> FAILURES P\<close>
  by (drule is_process_spec[THEN iffD1], metis)

lemma is_process6_S: \<open>is_process P \<Longrightarrow> (s @ [\<checkmark>(r)], {}) \<in> FAILURES P \<Longrightarrow> (s, X - {\<checkmark>(r)}) \<in> FAILURES P\<close>
  by (simp add: is_process6)

lemma is_process7:
  \<open>is_process P \<Longrightarrow> \<forall> s t. s \<notin> DIVERGENCES P \<or> \<not> tickFree s \<or> \<not> front_tickFree t \<or> s @ t \<in> DIVERGENCES P\<close>
  by (drule is_process_spec[THEN iffD1], metis)

lemma is_process7_S:
  \<open>is_process P \<Longrightarrow> s \<in> DIVERGENCES P \<Longrightarrow> tickFree s \<Longrightarrow>
   front_tickFree t \<Longrightarrow> s @ t \<in> DIVERGENCES P\<close>
  by (drule is_process7, metis)

lemma is_process8: \<open>is_process P \<Longrightarrow> \<forall>s X. s \<notin> DIVERGENCES P \<or> (s, X) \<in> FAILURES P\<close>
  by (drule is_process_spec[THEN iffD1], metis)

lemma is_process8_S: \<open>is_process P \<Longrightarrow> s \<in> DIVERGENCES P \<Longrightarrow> (s, X) \<in> FAILURES P\<close>
  by (drule is_process8, metis)

lemma is_process9: \<open>is_process P \<Longrightarrow> \<forall>s. s @ [tick] \<notin> DIVERGENCES P \<or> s \<in> DIVERGENCES P\<close>
  by (drule is_process_spec[THEN iffD1], metis)

lemma is_process9_S: \<open>is_process P \<Longrightarrow> s @ [tick] \<in> DIVERGENCES P \<Longrightarrow> s \<in> DIVERGENCES P\<close>
  by (drule is_process9, metis)

lemma Failures_implies_Traces: \<open> \<lbrakk>is_process P; (s, X) \<in> FAILURES P\<rbrakk> \<Longrightarrow> s \<in> TRACES P\<close>
  by( simp add: TRACES_def, metis)

lemma is_process5_sing: 
  \<open>is_process P \<Longrightarrow> (s, {x}) \<notin> FAILURES P \<Longrightarrow> (s, {}) \<in> FAILURES P \<Longrightarrow> (s @ [x], {}) \<in> FAILURES P\<close>
  by (drule_tac X = \<open>{}\<close> in is_process5_S1, auto)

lemma is_process5_singT: 
  \<open>is_process P \<Longrightarrow> (s, {x}) \<notin> FAILURES P \<Longrightarrow> (s, {}) \<in> FAILURES P \<Longrightarrow> s @ [x] \<in> TRACES P\<close>
  by (drule is_process5_sing) (auto simp add: TRACES_def)
 *)

lemma trace_with_Tick_imp_tickFree_front :
  ‹is_process P ==> t @ [🍋(r)] ∈ TRACES P ==> tF t›
  by (simp add: TRACES_def) (meson front_tickFree_append_iff is_process2 neq_Nil_conv)


section ‹ The Abstraction to the process-Type ›

typedef ('a, 'r) process_ptick = ‹{p :: ('a, 'r) process₀ . is_process p}›
  morphisms process₀_of_process process_of_process₀
proof - 
  have ‹({(s, X). s = []}, {}) ∈ {p. is_process p}›
    by (simp add: DIVERGENCES_def FAILURES_def is_process_def)
  thus ?thesis by auto
qed

text ‹Again, the old version without parameterized termination can be recovered
 by considering 🍋‹('a, unit) process_ptick›.›

type_synonym 'a process = ‹('a, unit) process_ptick›

setup_lifting type_definition_process_ptick

text ‹This is where we differ from previous versions: we lift definitions
 using Isabelle's machinery instead of doing it by hand.›

lift_definition Failures :: ‹('a, 'r) process_ptick ==> ('a, 'r) failure_ptick set› (‹F›) is FAILURES .

lift_definition Traces :: ‹('a, 'r) process_ptick ==> ('a, 'r) trace_ptick set› (‹T›) is TRACES .

lift_definition Divergences :: ‹('a, 'r) process_ptick ==> ('a, 'r) divergence_ptick set› (‹D›) is DIVERGENCES .

lift_definition Refusals :: ‹('a, 'r) process_ptick ==> ('a, 'r) refusal_ptick set› (‹R›) is REFUSALS .

lemma Refusals_def_bis : ‹R P = {X. ([], X) ∈ F P}›
  by (simp add: Failures.rep_eq REFUSALS_def Refusals.rep_eq)

lemma Refusals_iff : ‹X ∈ R P ⟷ ([], X) ∈ F P›
  by (simp add: Failures_def Refusals_def_bis)

lemma T_def_spec: ‹T P = {tr. ∃f. f ∈ F P ∧ tr = fst f}›
  by (simp add: Traces_def TRACES_def Failures_def)

lemma T_F_spec : ‹(t, {}) ∈ F P ⟷ t ∈ T P›
  by transfer (auto simp add: TRACES_def intro: is_process4)


lemma Process_spec: ‹process_of_process₀ (F P, D P) = P›
  by (simp add: Divergences.rep_eq Failures.rep_eq
      process₀_of_process_inverse process_surj_pair)


lemma Process_eq_spec: ‹P = Q ⟷ F P = F Q ∧ D P = D Q›
  by (metis Process_spec)


lemma Process_eq_spec_optimized: ‹P = Q ⟷ D P = D Q ∧ (D P = D Q ⟶ F P = F Q)›
  using Process_eq_spec by auto

lemma is_processT:
  ‹([], {}) ∈ F P ∧
 (∀s X. (s, X) ∈ F P ⟶ ftF s) ∧
 (∀s t. (s @ t, {}) ∈ F P ⟶ (s, {}) ∈ F P) ∧
 (∀s X Y. (s, Y) ∈ F P ∧ X ⊆ Y ⟶ (s, X) ∈ F P) ∧
 (∀s X Y. (s, X) ∈ F P ∧ (∀c. c ∈ Y ⟶ (s @ [c], {}) ∉ F P) ⟶ (s, X ∪ Y) ∈ F P) ∧
 (∀s r X. (s @ [🍋(r)], {}) ∈ F P ⟶ (s, X - {🍋(r)}) ∈ F P) ∧
 (∀s t. s ∈ D P ∧ tF s ∧ ftF t ⟶ s @ t ∈ D P) ∧
 (∀s r X. s ∈ D P ⟶ (s, X) ∈ F P) ∧ (∀s. s @ [🍋(r)] ∈ D P ⟶ s ∈ D P)›
  by transfer (unfold is_process_def, fast)

text ‹When the second type is set to 🍋‹unit›, we recover the classical definition
 as defined in the book by Roscoe.›

lemma is_processT_unit:
  ‹([], {}) ∈ F P ∧
 (∀s X. (s, X) ∈ F P ⟶ ftF s) ∧
 (∀s t. (s @ t, {}) ∈ F P ⟶ (s, {}) ∈ F P) ∧
 (∀s X Y. (s, Y) ∈ F P ∧ X ⊆ Y ⟶ (s, X) ∈ F P) ∧
 (∀s X Y. (s, X) ∈ F P ∧ (∀c. c ∈ Y ⟶ (s @ [c], {}) ∉ F P) ⟶ (s, X ∪ Y) ∈ F P) ∧
 (∀s X. (s @ [🍋], {}) ∈ F P ⟶ (s, X - {🍋}) ∈ F P) ∧
 (∀s t. s ∈ D P ∧ tF s ∧ ftF t ⟶ s @ t ∈ D P) ∧
 (∀s X. s ∈ D P ⟶ (s, X) ∈ F P) ∧ (∀s. s @ [🍋] ∈ D P ⟶ s ∈ D P)›
  by transfer (unfold is_process_def, fast)


lemma process_charn:
  ‹([], {}) ∈ F P ∧
 (∀s X. (s, X) ∈ F P ⟶ ftF s) ∧
 (∀s t. (s @ t, {}) ∉ F P ∨ (s, {}) ∈ F P) ∧
 (∀s X Y. (s, Y) ∉ F P ∨ ¬ X ⊆ Y ∨ (s, X) ∈ F P) ∧
 (∀s X Y. (s, X) ∈ F P ∧ (∀c. c ∈ Y ⟶ (s @ [c], {}) ∉ F P) ⟶ (s, X ∪ Y) ∈ F P) ∧
 (∀s r X. (s @ [🍋(r)], {}) ∈ F P ⟶ (s, X - {🍋(r)}) ∈ F P) ∧
 (∀s t. s ∉ D P ∨ ¬ tF s ∨ ¬ ftF t ∨ s @ t ∈ D P) ∧
 (∀s r X. s ∉ D P ∨ (s, X) ∈ F P) ∧ (∀s. s @ [🍋(r)] ∉ D P ∨ s ∈ D P)›
  by (meson is_processT)



text‹ split of \verb+is_processT+: ›

lemma is_processT1          : ‹([], {}) ∈ F P›
  and is_processT1_TR       : ‹[] ∈ T P›
  and is_processT2          : ‹(s, X) ∈ F P ==> ftF s›
  and is_processT2_TR       : ‹s ∈ T P ==> ftF s›
  and is_processT3          : ‹(s @ t, {}) ∈ F P ==> (s, {}) ∈ F P›
  and is_processT3_pref     : ‹(t, {}) ∈ F P ==> s ≤ t ==> (s, {}) ∈ F P›
  and is_processT3_TR       : ‹t ∈ T P ==> s ≤ t ==> s ∈ T P›
  and is_processT3_TR_pref  : ‹(t, {}) ∈ F P ==> s ≤‹************
 and is_processT4 : ‹ Ye.
 and is_processT5 : ‹ ∀ ∈ (s @ [c], {}) ∉
 ==> (s, X ∪ Y) ∈*
 and is_processT6 : ‹ F (s, X - {🍋 \close
  is_processT6 : ‹ X - {\<>r)}) ∈ P\close
  is_processT : \<opens tF s ==> s @ t ∈ D
 sX) <> 
  is_proces : ‹ s ∈
java.lang.StringIndexOutOfBoundsException: Index 64 out of bounds for length 20
  \<openmetisThe Notion of Processes›c 200 Univers Paris-Sud, France

  is_process : ‹.clo
 
 Diff_insert_absorbsocs6
 metis Diff_insert_absorb is_processT6_TR)

 > t \<> Pre-Requisite: Basic Traces and tick-Freeness›
 is_processT3_TRytore

  nonempty_divE :
 ‹ (∧ t ∈ thesis) ==>IANWAY OUT OF THE USE
 (mx_in front_tickFree_nonempty_apis_pro
 is_processT9 netext \ ‹As mentioned earlier, we base the theory of CS o HLC,a sael/O librr


  div_butlast_when_non_tickFree_iff
 ‹
 by (cases s r where ‹i_k e ≡Ila|\checkmarkr) ==> Inr r›
 (metis front_tickFree_Cons_if is_roe7srcesT stk_e)


 
 by (metis eq_fst_iff is_processT8)

  is_processT9: ‹
 by (insert process_charn[of P], metis)

 by (simp add:process_charn)

  is_processT2: ‹
 text 🚫t_k›

  is_processT2_TR : ‹
 by (simp add: Traces.rep_eq Traces_def TRACES_def Failures.rep_eq[symmetric])
 (use i_proceT2 n as)
 
 
  is_proT2: ‹ tick ∉
 using front_tickFree_def is_processT2 tickFree_def by blast
 *)

lemma is_processT3 : ‹ FP\close
 by (metis process_charn)

  F P ==> t ==> F P›pjava.lang.NullPointerException



lemma>s, Y) ∈ X< Y ==> (s,X \in Pjava.lang.StringIndexOutOfBoundsException: Index 128 out of bounds for length 128
  by (mesonprocess_charn

lemma is_processT4_S1 : ‹
 by (metis is_processT4 prod.coll

  is_processT5:
 ‹ (s @ { \otin F P ==> (s, X ∪ FPclo
 by (simp add: process_charn)

 is_processT5_S1:
 ‹ Y) ∉exic.c ∈ (s @ [c], {}) ∈
 by (erule contrapos_np, simp add: is_processT5)

  is_processT5_S2: ‹ F P \<Longrightarrow( F P›
 using is_processT5_S1 by blast

  is_processT5_S2a: ‹ F (s @ [c], {}) \<> 
 using is_processT5_S2 by blast

  is_processT5_S3: ‹ t \<Longrightarrow  length t›
 using is_processT5_S2a by auto

 
  is_processT5_S4: ‹
 by (erule contrapos_np, si apply (metis prefix_length_less prfix_ode.dua_ordr.no_q_rer_mples_stic)


  is_processT5_S5:
java.lang.StringIndexOutOfBoundsException: Index 144 out of bounds for length 144
 ∀ (s @ [c], {}) ∈
 by (simp add: is_processT5_S2a)

  is_processT5_S6: ‹
 metis append_self_conv2 is_processT1 is_processT5_S4)

  is_processT6: ‹((λt. x # t) ` {t. t ≤ s})› by (simp add: Cons.hyps)
 by (simp add: process_charn)

  is_processT7: ‹reeet <> 
 by (insert process_charn[of P], metis)

 ocessT8 \open∈) ∈
 sertrcess_cr[fP, mets)

  is_processT8_Pair: \<openfsts ≤ t ==> length s ≤
 by (metis eq_fst_iff is_processT8)

  is_processT9: ‹ D P› .∃ {t. ∃ x#s= @t}\close
 by (insert process_charn[of P], metis)

  le_same_: \<pen(
 by (meis les_elist_de inoderle_ase nssl pei_etprefx
 *)

n ductshowfinite {t. t ≤ []} ∧ by simp

lemma F_T: ‹
 by (simp add: T_def_spec split_def, metis)

  ltickFree sip]: \open []› is_ev a ∧
  processT4pec

lemmasD_T = is_processT8 [THEN

lemmas is_processT4_empty [elim!] = F_T [THEN T_F]


(* 
lemma no_Trace_implies_no_Failure:singe_Nil
by ec

lemmas  NT_NF = no_Trace_implies_no_Failure



lemma D_T_subset :  theicate+front_tickFreeitstrongerersion

lemma _:open>(s, X) \<notin> \<F> P \<Longrightarrow> s \>\D>P\<close>
java.lang.StringIndexOutOfBoundsException: Index 69 out of bounds for length 49

lemmas NT_ND =_set .tra_subsetDsetD

lemma F_T1: \<open>a \<in> \<F> P \<Longrightarrow> fst a \<in> \<T> P<close
  by (rule_tac X=\<open>snd a\<close> in F_T, simp)



>
  yrulecontrapos_nnonlyF

lemma  is_processT6_S1: \<open>\<checkmark>(r) \<notin> X \<Longrightarrow> (s @ [\<checkmark>(r)], {}) \<in> \<F> P \<Longrightarrow> (s, X) \<in> \<F> P\<close>
  by (metis Diff_insert_absorb processT6

lemmas is_processT3_ST = T_F [THEN is_processT3, THEN F_T]

lemmascessT3_ST_pref_ef THEN_cessT3_S_prefTHEN]

lemmass_processT3_SR_THENEN_HEN _ssT3
 *)




lemma is_processT5_S7: ‹>∃ A ∧ t @[x]∈
 by (metis T_F_sec s_rocesT5 pbtlf)

 ocessT5_S7's5_7:
 ‹ A) ∉>P ==>∈ X ∧
 by (erule contrapos_np, subst Un_Diff_cancel[symmetric])
 (rule is_processT5, auto simp: T_F_spec)

  trace_tick_continuation_or_all_tick_failuresE:
java.lang.NullPointerException
java.lang.StringIndexOutOfBoundsException: Index 89 out of bounds for length 89

 
  by (auto simp: T_F_spec[symmetric] is_processT1) *)

lemmas cessT1_TR

lemmaskFree
  and s_processT8
  and T_imp_front_tickFree THEN


lemma D_front_tickFree_subset<>subseteq
  by (<s

lemma F_D_part FAILURES P ∧ FAILURES ftF s) \>
  by (autoT8

lemmaforall>s r X. (s @ [<){
  using F_D_part by blast

lemma append_T_imp_tickFree:  java.lang.NullPointerException
  by (meson front_tickFree_append_iff is_processT2_TR)

lemma tick_T_F: \open \checkmark<n T (t @ [🍋
  by (mesons X Y. (s, Y) ∉ X ⊆>_ocesss <>FAILURESc. c ∈ (s @ [c], {}) ∉

(* corollary append_single_T_imp_tickFree : \<open>t @ [a] \<in> \<T> P \<Longrightarrow> tickFree t\<close>
  by (simp add: append_T_imp_tickFree) *)

(* lemma F_subset_imp_T_subset: \<open>\<F> P \<subseteq> \<F> Q \<Longrightarrow> \<T> P \<subseteq> \<T> Q\<close>
  by (auto simp: subsetD T_F_spec[symmetric]) *)

(* lemma is_processT6_S2: \<open>\<checkmark>(r) \<notin> X \<Longrightarrow> [\<checkmark>(r)] \<in> \<T> P \<Longrightarrow> ([], X) \<in> \<F> P\<close>
  by (metis Diff_insert_absorb append_Nil is_processT6_TR) *)

lemma is_processT9_tick: ‹
 by mts aendNi _rocT isres9tcFe_Nl

 mp_decomp<t  T P \<Longrightarrow  tF t\Longrightarrow ∃
 by (simp add: is_processT2_TR nonTickFree_n_frontTickFree)



 ‹
 ‹∃c. c ∈ Y ∧ (sa @ [c, } <> 
  \emph{approximation ordering} (also called \emph{pros rdrin})
 manticsoui (pits) oer rocsss,
  \emph{refinement ordering} captures our intuition that a more concrete
  is more deterministic and more defined than an abstract one.

  s<is_process\ Y ⟶ })∉
  i\lemsope>\R>_a›
  former provides ju<penrocess
 elements eca $rd ldots \close

  min_elememis_poces:\><ongrightarrow 
  {s ∈t <>X

  Nil_min_elem byby (
 by (simp add: min_elems_def)

  min_elems_le_self[simp] : 🚫is_process P ==> t @ [🍋 TRACES P 🚫
  is_ <>is_process

  elem_min_elems = Set.set_mp[OF min_elems_le_self]
 
  min_ele : \<openmin_elems
 by (simp add: min_elems_def less_eq_list_def set_eq_iff)
 (metis front_tickFree_charn nil_less nil_less2)

  min_elems5 : ‹
  -
 have * : ‹^s>p\^sub>t_i\^s>c_{p :: ('a, 'r) process₀ . is_process p}›
 proof (induct n arbitrary: x rule: nat_induct)
 show ‹>length x ≤ ∃x. s ∈ for x by (simp add: Nil_min_elems)
 next
  x
 assume ‹length x ≤ Suc n›
 assume hyp : ‹Longrightarrow>length x ≤ ∃x. s ∈ for x
java.lang.NullPointerException
 proof (cases ‹
 show ‹A. y < xs≤ min_elems A›
 by (elim bexE, frule hyp, drule less_length_mono, use ‹ in simp)
 (meson dual_order.strict_trans2 less_list_def)
 next
 show ‹T P = {tr. ∃f. f ∈ F P ∧
 using ‹_lems_e b auo
 qed
 qed
 thus ‹
 

  min_elems4: ‹>s. (s :: ('a, 'r) trace_tc min_elems A›
 by (auto dest: min_elems5)

  min_elems_charn: ‹ ∃ t' ∈
 esono pfixE E m_ele5

  miin_elemsno:\opens::'a list) ∈ min_elems A ==> t ∈ s l by (simp add: Fai.rep_eq REFUSALS_Refusals.r)
 by (metis (mono_tags, lifting) mem_Collect_eq min_elems_def order_neq_le_trans)

 ‹
  sets after a given trace $s$ and a given process
 P$: ›

 Refusals_after : ‹
 where ‹ \F P \<and c <>  P) ⟶unio> Y) ∈ F P) ∧

 >In the following, we link the process theory to the underlying
 /domain theory of HOLCF y ietiinte apprxmatio ordeng
  HOLCF's pcpo's. ›

 
java.lang.NullPointerException
 
  \qsubseteqwi
 \verb+_ << s>0of_process process_s)


  le_approx_def : ‹
 \forall>..s ∉ R_a Q s) ∧
 min_elems (Dlemma is_pis_processT1 : ‹

 ‹ The approximation ordering captures the fact that more concrete
  should be more defined by ordering the divergence sets
 . For defined positions in a process, the failure
  cici onwis;mrovr e inima et
 wrt.~prefix ordering on traces, i.e.~lists) must be contained in
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null

  ..

 


  le_approx1: ‹
 by (simp add: le_approx_def)


  le_approx2: ‹
 by (auto simp: Refusals_after_def le_approx_def)


  le_approx3: ‹P ⊑ Q ==> min_elems(D P) ⊆ T Q› ⟶∧
 by (simp add: le_approx_def)

  le_approx2T: ‹
 by (auto simp: le_approx2 T_F_spec[symmetric])

 le_approx_lemma_F : 🚫 Longr X ⊆ snd x ==> (fst x, X) ∈ F P›
 by (meson le_approx2 process_chnsurelI

  order_lemma = le_approx_lemma_F

 lemma_T:<>\
 by(auto dest!:le_approx_lemas

  proc_ord2a : ‹(s, {}) ∈ F (s @ [c], {}) ∉ (s, {c}) ∈
 by (auto simp: le_approx_def Refusals_after_def)


java.lang.NullPointerException
  intro_classes
 ow\>sqs> P›
 by (metis D_T elem_min_elems le_approx_def subsetI)
 <> 
 show ‹
 simpd: 🚫
 
 fix P Q R :: ‹s ∈ D (s, X) ∈
 assume ‹ \<or(and>
 show ‹s @ [tick] ∈ s ∈
 proof (unfold le_approx_def, intro conjI allI impI)
 show ‹ Some Consequences of the Process Characterization›
 next
 show ‹s ∈t. s <>\
 by (metis ‹
 next
 from ‹P ⊑\closeTHEN le_approx3]
 Q ⊑ X. s \notinD (s,X) ∈r)] ∉
  D_T_ubset:\openD P ⊆ T P›!D_
  (sim ad: in_lems_def ssubet_fff lst
 qed
 


 ‹
  theory, which comprises a library of facts such as \verb+chain+,
 verb+directed+(sets), upper bounds and least up is_prcs3THEF]

  is_processT5_S7: ‹)\<> 
  facts from the theory of complete partial orders:
 begin{itemize}
 tion_or_all_tick_failuresE
 item \verb+po_class.chain_mono+ : @{thm po_clas.caai_mn}
 
 item
 item \verb+po_class.ub_imageD+ : @{thm po_class.ub_imageD}
 item \verb+po_class.is_ub_upward+ : @{thm po_class.is_ub_upward}
 item \verb+po_class.is_lubD1+ : @{thm po_class.is_lubD1}
 item \verb+po_class.is_lubI+ : @{thm po_class.is_lubI}
 item \verb+po_class.is_lub_maximal+ : @{thm po_class.is_lub_maximal}
 
 item \verb+po_class.is_lub_range_shift+: \\ @{thm po_class.is_lub_range_shift}
 item \verb+po_lass.i.i_lub_angeD+ @{thmp_las.s_lub_rage
 item \verb+po_class.lub_eqI+: @{thm po_class.lub_eqI}
 item \verb+po_class.is_lub_unique+:@{thm po_class.is_lub_unique}
 end{itemize}
 🚫


  min_elems3: ‹
 by (simp addmn__eemdee ess_q_lit_def l les_llst_ef)
 (metis D_imp_front_tickFree append.right_neutral front_tickFree_append_iff
 front_tickFree_dw_closed is_processT7 lemma T_nonTickFre 🚫


 s ∉ D \>s @ [c] ∈ [c] \<in 
 

  min_elems2: 🚫n> \FP
 by (meson T_F in_mono le_approx3 le_approx_lemma_F min_elems3)

  min_elems6: ‹ D P ⊑ (s @ [c], {}) nFS\close
 ontro!:mn_lem2)

 : ‹s ∉ D P ==> (s, {}) ∈ F P ==> P ⊑ S ==> Q ⊑ (s, {})\<in F Q›
 by (meson is_processT8 le_approx2)

 \pen <notin  ==>⊑
 by (meson D_T le_approx2T)


  chain_lemma: ‹
 by (metis chain_mono_less not_le_imp_l poclas.hanmoo


  fixes S :: ‹<t\_ick›
 assumes ‹ is_pocessT8 : 🚫
 

  lim_proc :: ‹s ∈ A ==> ∃s. t ∈ms A› by auto
 is ‹
  (unfold is_process_defSfDIVGCES_def fs_cov snn_on,itroocn lIm)
 show ‹ {) \in F<>(
 
 show ‹open>[('a, 'r) process_pik,('ar rc\<^>\i_k] ==>p_ik set›R_a›
  (meson INT_iff UNIV_I image_eqI is_processT2)
 
 <(s
 (s, {}) ∈ ∩p_ik :(ye p elow
 
 show ‹(s, Y) ∈_+. ›
 by (metis (full_types) INT_iff is_processT4)
 
 show ‹ The approximation ordering captures the fact that more concrete
 <>s
 
 proof (rule ccontr)
 assume \openusing is_pr by fas
 then obtain i where ‹
 moreover have ‹
 ultimately obtainpen>P \<>P> min_elemD P) ⊆
 using is_processT5 by blast
 from ‹
 from assm ‹

java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
 by (*
 qed
 essT9 oe>s i 🪙
 show ‹
 (s, X - {🍋(r)}) ∈
 
 show ‹
 s @ t ∈ ∩
 
  \shows<> 
 by (simp add: is_processT8)
 
 show ‹ ∩
 
 


 er o opet prtia dr
 by (metis Failures.rep_eq lim_proc.rep_eq process_surj_pair prod.sel(1))

  D_LUB: ‹
 sverncesrep_eq im_rcrpeqqprces_urj

  T_LUB: ‹
 

 rojs = _LB _LB _U

  Refusals_LUB: ‹
 autouo imp mp add: Reffusalsl_ddef_bbs F_LUB)

  Refusals_after_LUB: ‹
 by (auto simp add: Refusals_after_def F_LUB)

 
 and D_LUB_2: : \open ∈(s, X) ∈ F P ==> ∀ (s @ [c], {})\notin F P ==>X <nion 
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
 and Refusals_LUB_2: ‹ <>  (s @ [c], {}) ∈
 and Refusals_after_LUB_2: ‹using is_processT5_S2 _S2 by bas
 by (simp_all add: F_LUB D_LUB T_LUB Refusals_LUB Refusals_after_LUB)

 


  ‹\F> i_rc›
  eaddd\close>


 ‹

 ‹
 \_ \le \_ $ written \verb+_ <= _+. It captures the intuition that more
  processes should be more deterministic and more defined.›

java.lang.NullPointerException
 

java.lang.NullPointerException
 where ‹ )🚫s ∈

  less_process ∩==> (s, X) ∈ for s X
 where ‹] eti)

 .

 



 oteatijstthersynta oor stndr pross efieent orer
 defined in the theory Process. ›


  le_ref1 : \<openP<   D P›
 and le_ref2 : ‹(s, X) ∈ lim_proc ⟷i. (s, X) ∈
 and le_ref2T : ‹ T
java.lang.NullPointerException
 by (simp_all add: less_eq_process_p RsasatrLUB_: open>X ∈a lim_proc s ⟷i. X ∈ Some Consequences of the Process Characterization›
 (use T_F_spec iblast)

  F_subsetimp__ssbset \openF P ⊆ F Q ==> T P ⊆
 using T_F_spec by blast

  D_extended_is_D :
java.lang.NullPointerException
 by (auto simp add: is_processT7)
 (metis D_imp_front_tickFree append.right_neutral butlast_snoc front_tickFree_append_iff
  prcesnonTikree__roTikreetcreNl


  Process_eq_optimizedI :
 lemma no_Trace_implies ‹
 Andt X. (t, X) ∈ \F>P\Longrightarrow t ∉ P \<Longrightarrow  D\Longrightarrow> (t, X n
 ∧t X. (t, X) ∈ no_Trac
 by (simp add: Process_eq_spec_optimized, safe, auto intro: is_processT8)



  process_ptc
java.lang.NullPointerException


  lim_proc_is_ub: ‹NT_ND = D_T_sub
 by (simp add: s_u_ef le_aprx_dfF_LUBD_LBT_LURfusas_ferdef)
 (into allI cojI, last, use chainnemm is_pocesT8 l_approx2 in as,
 use D_T chainchain_lemma le_approx2T le_approx in blast)


 
 notin> D P ==> t ∈ ¬ @ [c]›
 by (auto simp: le_list_def less_list_def)
 (metis butlast_append butlast_snoc front_tickFree_append_iff process_charn self_append_conv)
 *)


lemma chain_min_elem_div_is_min_for_sequel:
  <openchain min_elems (S i)) <Longrightarrow  j ==> D (S j) <ongrightarrowrightarrow
  by (metis contrapos_nnT_F
      min_elems5 min_elems_no po_class.chain_mono)


lemma limproc_is_lubmin_elems5
proof (unfold is_lub_def, intro conjI allI impI)
  showrange S <| lim_proc S›
next
  show ‹
  proof (unfold le_approx_def, intro conjI allI impI subsetI)
    show \<open>s
      by (meson D_LUB_2 \<
  nextbysimpd<>hain S\<close> D_LUB)lemma is_processT5_S7 \<open>t \<in> \<T> P \Longrightarrow>(, A \notinF>P \<Longrightarrow> \<exists>x. x \<in> A \<and> t @ []in \<T> P\<close>
    show \<open>s \< \<D> (lim_proc S) \<Longrightarrow> \<R>\<^sub>a (lim_proc S) s = \<R>\<^sub>a P s\<close> for s
      by (metis \<open>chain S\<close> \<open>range S <| P\<close> D_LUB_2 le_approx_def lim_proc_is_ub ub_rangeD
  
    fix s
    assume \<open>s \<in> min_elems (\<D> (lim_proc S))\<close>
    from elem_min_elems[OF this] have \<open>\<forall>i. s \<in> \<D> (S i)\<close>
      by lemma D_front_tickFree_subset :\<>\<D> P \<subseteq> Collect ftF\<closejava.lang.StringIndexOutOfBoundsException: Index 77 out of bounds for length 77
    \<exists>i. \<forall>j\<ge>i. s \<in> min_elems (\<D> (S j))\<close>
   ruleontr
      assume \<open>\<nexists>i. \<forall>j\<ge>i. s \<in> min_elems (\<D> (S j))\<lose
      hence \<open>\<forall>i. \<existsdtmp_front_tickFree
      with \<open>\<forall>i. slemma tick_T_F: \<open(r)] \<in> \<T> P \<Longrightarrow> (t @ [\<checkmark>(r)], X) \<in> \<F> P\<close>
      have \<open>\<forall>j. s \<notin> min_elems ( xx. \<not> P x \<Longrightarrow> cont (g x)\rbrakk \<Longrightarrow>
      from \<open>s \<in> min_elems (\<D> (lim_proc S))\<close> \<open>\<forall>i. s \<in> \<D>  <close> show False
        by (casessrulerev_casespdd _lems_def <openhaininS<ose>
          (use Nil_min_elems \<open>\<forall>j. s \<notin> min_elems (\<D> (  (uct<>card (S 0)\<close> arbitrary: S rule: nat_less_induct)
            metis (no_types, lifting) INT_iff \<open>\<forall>j. s \<notin> min_elems (\<D> (S j))\<close> less_self min_elems3)
    qed
    <s \<in> \<T> P\<close> by (meson le_approx3 order.refl subset_eq \<open>range S <| P\<close> ub_rangeD)
  qed
qed


lemma limproc_is_thelub: \<open>chain S \<Longrightarrow> (\<Squnion>i. S i)alsofromift_Suc_antimono_lemono_leere OF\<pen<nd>i. S (Suc i) \<subseteq> S i\<close>  by simp din_elems_def
  by (frule limproc_is_lub, frule po_class.lub_eqI, simp)


instance process\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k :: (type, type) cpo
  by intro_classes (use limproc_is_lub in blast)



instance process\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k :: (type, type) pcpo
proof
  define bot\<x \<in> A \<Longrightarrow> length x \<le> n \<Longrightarrow> \<exists>s\<le>x. s \<in> min_elems A\<close> for x :: \<open>'a list\<close> and A n
  define bot :: \<open>('a, 'r) process\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k\<close> where \<open>bot \<equiv> process_of_process\<^sub>0 bot\<^sub>0\<close>

  have \<open>is_process bot\<^sub>0\<close>
    unfolding is_process_def bot\<^sub>0_
    by (simp add: FAILURES_def DIVERGENCES_def)
      (meson front_tickFree_append_iff front_tickFree_dw_closed)
  have F_botnext
    by (metis CollectI FAILURES_def Failures.rep_eq \<open>is_process bot\<^sub>0\<close> 
        bot\<^sub>0_def bot_def fst_eqD process_of_process\<^sub>0_inverse)
  have D_bot : \<open>\<D> bot = {d. ftF d}\<close>
    by (tis llectI VERGENCES_defvergencesp_eq<>is_process bot<sub>\closejava.lang.StringIndexOutOfBoundsException: Index 95 out of bounds for length 95
        bot\<^sub>0_def bot_def process_of_process\<^sub>0_inverse prod.sel(2))

  show \<open>\<exists>lemma min_elems4:\open> \<noteq> {} \<Longrightarrow> \<exists>s. (s :: ('a, 'r) trace\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k) \<in> min_elems A\<close>
  proof (intro exI allI)
    show \<open>bot \<sqsubseteq> y\<close> for y
    proof (unfold le_approx_def, intro conjI allIdefinition Refusals_after<>('a, 'r) process\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k, ('a, 'r) trace\<^sub>p\<^sub>t\<^sub>i\<^subcsubk] \<Rightarrow> ('a, 'r) refusal\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k set\<close>open\<R>\<^sub>a\<close>)
rightarrow \<D> bot\<close> for s
        by (simp add: D_bot D_imp_front_tickFree)
    next
      from F_imp_front_tickFree show \<open>s \<notin> \<D> bot \<Longrightarrow> \<R>\<java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
        by (auto simp add: D_bot Refusals_after_def F_bot)
    next
      show \<open>s \<in> min_elems (\<D> bot) \<Longrightarrow> s \<in> \<T> y\<close> for s
        by (simp add: D_bot min_elems_Collect_ftF_is_Nil)
    qed
  qed
qed



 <close>

lemma le_FD_adm : \<open>cont (u :: ('b::cpo) \<Rightarrow> ('a, 'r) process\<^emma le_approx_lemma_F :\<n < \<F> Q \<subseteq> \F> P\<close>
  apply (unfold less_eq_process\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k_def adm_def)
  apply (simp add: cont2contlubE D_LUB F_LUB ch2ch_cont limproc_is_thelub monofun_def)
  by (meson INF_greatest dual_order.trans is_ub_thelub le_approx1 le_approx_lemma_F)

lemmas le_FD_adm_cont[simp] = le_FD_adm[OF _ cont2mono]

section\<open> The Conditional Statement is Continuous \<close>
text\<open>The conditional operator of CSP is obtained by a direct shallow embedding. Here we  show <open>P \qsubseteq Q \<Longrightarrow> Q \<sqsubseteq> P \<Longrightarrow> P = Q\<close> for P Q :: \<open>('a, 'r) process\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k\<close>

lemma if_then_else_cont[simp]:
  \<open>\<lbrakk>\<And>x. P x \<Longrightarrow> cont (f x); \<And>x. \<not> P x \<Longrightarrow> cont (g x)\<rbrakk> \Longrightarrow
   cont (\<lambda>y. if P x then f x y else g x y)\<close>
  for f :: \<open>'c \<Rightarrow> 'b :: cpo \<Rightarrow> ('a, 'r) process\<^sub>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k\<close>
  by (auto simp: cont_def)


section \<open>Tools for proving continuity\<close>

\<comment> \<open>The following result is very useful (especially for ProcOmata).\<closetext\<open> At this ointeit ber  m derlying

lemma cont_process_rec: \<open>P = (\<mu> X. f X) \<Longrightarrow> cont f \<Longrightarrow> P = f P\<close>
  by (simp add: def_cont_fix_eq)


lemma Inter_nonempty_finite_chained_sets: \<open>(\<Inter>iitem\+lassmaximalpo_classmal
  if \<open>\<And>i. j \<le> i \<Longrightarrow> S i \<noteq> {}\<close> \<open>finite (S j)\<close> \<open>\<And>i. S (Suc i) \<subseteq> S i\<close> for S :: \<open>nat \<Rightarrow> 'a set\<close>
proofee_dw_closedprocessT7efix_def
  have * : \<open>\<forall>i. S i \<noteq> {java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
    for S :: \<open>nat \<Rightarrow> 'a set\<close>
roofnductct >card (S 0)\<close> arbitrary: S rule: nat_less_induct)
    case 1
    show ?case
    sesopen\<forall>i. S i = S 0\<close>)
      case True
      thus ?thesis by (metis "1.prems"(1) INT_iff ex_in_conv)
    
      case False
      have f1: \<open>i \<le><ongrightarrow S j \<subseteq> S i\<close> for i j by (simp add: "1.prems"(3) lift_Suc_antimono_le)
      with False obtain j m where f2: \<open>m < java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
        by (metis "1.prems"(2) psubsetI psubset_card_mono zero_le)
      define T where \<open>T i \<equiv> S (i + j)\<close> for i
      have f4: \<open>m = card (T 0)\<close> unfolding T_def by (simp add: f3)
      from f1 have f5: \<open>(\<Inter>i. S i) = (\<Inter>i. T i)\<close> begin
      show ?thesis
        apply (subst f5)
        apply (rule "1.hyps"[rule_format, OF f2, of T, OF f4], unfold T_def)
        by (simp_all add: "1.prems"(1, 3) lift_Suc_antimono_le)
          1ems2add_0 nite_subset1
    qed
  qed
  define S' where \<open>S' i \<equiv> S (j + i)\<close> for i
  have \<open>\<forall>i. S' i \<noteq> {}\<close> by (simp add: S'_def \<open>\<And>i. j \<le> i \<Longrightarrow> S i \<noteq> {}\<close>)
  moreover have \<open>finite (S' 0)\<close> by (simp add: \<open>S'< \<lambda>i. S (j + i)\<close> \<open>finite (S j)\<close>)
  moreover have \<open>\<forall>i. S' (Suc i) \<subseteq> S' i\<close> by (simp add: S'_def \<open>\<And>i. S (Suc i) \<subseteq    \opens, X \<union> Y) \<notin> \<Inter> (\<F> ` range S)\<close>
  ultimately have \<open>(\<Inter>i. S' i) \<noteq> {}\<close> by (fact "*")
  also from lift_Suc_antimono_le[where f = S, OF \<open>\<And>i. S (Suc i) \<subseteq> S i\<    fromassmopenc \<in> Y\<close> obtain j where ** : \<open>(s @ [c], {}) \<notin> \<F> (S j)\<close> by blast
  have \<open>
    ( : NF_greateststINF_lowerowererF_monodefualityI
  nally owopen\<Inter>i. S i) \<noteq> {}\<close> .
qed


method prove_finite_subset_of_prefixes for t :: \<open>('a, 'r)ce<>p\<^sub>t\<^sub>i\<^sub>c\<^sub>k\<close> =
  \<comment>\<open>Useful for establishing lemma F_LUB<>\<F> lim_proc = \<Inter> (\<F> ` range S)\<close>
  solves  by (metis Failures.rep_eq lim_proc_ocess_surj_pair)
          (rule finite_subset[of _ \<open>{u. u \<le> t}\<close>],
           use prefixI in blast, simp add: prefixes_fin)\<close


(*<*)
end
  (*>*)