src/HOL/HOLCF/IOA/meta_theory/Deadlock.thy
changeset 62002 f1599e98c4d0
parent 62001 1f2788fb0b8b
equal deleted inserted replaced
62001:1f2788fb0b8b 62002:f1599e98c4d0
     1 (*  Title:      HOL/HOLCF/IOA/meta_theory/Deadlock.thy
     1 (*  Title:      HOL/HOLCF/IOA/meta_theory/Deadlock.thy
     2     Author:     Olaf Müller
     2     Author:     Olaf Müller
     3 *)
     3 *)
     4 
     4 
     5 section {* Deadlock freedom of I/O Automata *}
     5 section \<open>Deadlock freedom of I/O Automata\<close>
     6 
     6 
     7 theory Deadlock
     7 theory Deadlock
     8 imports RefCorrectness CompoScheds
     8 imports RefCorrectness CompoScheds
     9 begin
     9 begin
    10 
    10 
    11 text {* input actions may always be added to a schedule *}
    11 text \<open>input actions may always be added to a schedule\<close>
    12 
    12 
    13 lemma scheds_input_enabled:
    13 lemma scheds_input_enabled:
    14   "[| Filter (%x. x:act A)$sch : schedules A; a:inp A; input_enabled A; Finite sch|]  
    14   "[| Filter (%x. x:act A)$sch : schedules A; a:inp A; input_enabled A; Finite sch|]  
    15           ==> Filter (%x. x:act A)$sch @@ a\<leadsto>nil : schedules A"
    15           ==> Filter (%x. x:act A)$sch @@ a\<leadsto>nil : schedules A"
    16 apply (simp add: schedules_def has_schedule_def)
    16 apply (simp add: schedules_def has_schedule_def)
    17 apply auto
    17 apply auto
    18 apply (frule inp_is_act)
    18 apply (frule inp_is_act)
    19 apply (simp add: executions_def)
    19 apply (simp add: executions_def)
    20 apply (tactic {* pair_tac @{context} "ex" 1 *})
    20 apply (tactic \<open>pair_tac @{context} "ex" 1\<close>)
    21 apply (rename_tac s ex)
    21 apply (rename_tac s ex)
    22 apply (subgoal_tac "Finite ex")
    22 apply (subgoal_tac "Finite ex")
    23 prefer 2
    23 prefer 2
    24 apply (simp add: filter_act_def)
    24 apply (simp add: filter_act_def)
    25 defer
    25 defer
    45 apply simp
    45 apply simp
    46 apply (rule sym)
    46 apply (rule sym)
    47 apply assumption
    47 apply assumption
    48 done
    48 done
    49 
    49 
    50 text {*
    50 text \<open>
    51                Deadlock freedom: component B cannot block an out or int action
    51                Deadlock freedom: component B cannot block an out or int action
    52                                  of component A in every schedule.
    52                                  of component A in every schedule.
    53     Needs compositionality on schedule level, input-enabledness, compatibility
    53     Needs compositionality on schedule level, input-enabledness, compatibility
    54                     and distributivity of is_exec_frag over @@
    54                     and distributivity of is_exec_frag over @@
    55 *}
    55 \<close>
    56 
    56 
    57 declare split_if [split del]
    57 declare split_if [split del]
    58 lemma IOA_deadlock_free: "[| a : local A; Finite sch; sch : schedules (A\<parallel>B);  
    58 lemma IOA_deadlock_free: "[| a : local A; Finite sch; sch : schedules (A\<parallel>B);  
    59              Filter (%x. x:act A)$(sch @@ a\<leadsto>nil) : schedules A; compatible A B; input_enabled B |]  
    59              Filter (%x. x:act A)$(sch @@ a\<leadsto>nil) : schedules A; compatible A B; input_enabled B |]  
    60            ==> (sch @@ a\<leadsto>nil) : schedules (A\<parallel>B)"
    60            ==> (sch @@ a\<leadsto>nil) : schedules (A\<parallel>B)"