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)" |