25 qed "square_reflcl"; |
25 qed "square_reflcl"; |
26 |
26 |
27 goalw Commutation.thy [square_def] |
27 goalw Commutation.thy [square_def] |
28 "!!R. square R S S T ==> square (R^*) S S (T^*)"; |
28 "!!R. square R S S T ==> square (R^*) S S (T^*)"; |
29 by(strip_tac 1); |
29 by(strip_tac 1); |
30 be rtrancl_induct 1; |
30 by (etac rtrancl_induct 1); |
31 by(fast_tac trancl_cs 1); |
31 by(fast_tac trancl_cs 1); |
32 by(fast_tac (HOL_cs addSEs [rtrancl_into_rtrancl]) 1); |
32 by(fast_tac (HOL_cs addSEs [rtrancl_into_rtrancl]) 1); |
33 qed "square_rtrancl"; |
33 qed "square_rtrancl"; |
34 |
34 |
35 goalw Commutation.thy [commute_def] |
35 goalw Commutation.thy [commute_def] |
36 "!!R. square R S (S^*) (R^=) ==> commute (R^*) (S^*)"; |
36 "!!R. square R S (S^*) (R^=) ==> commute (R^*) (S^*)"; |
37 bd square_reflcl 1; |
37 by (dtac square_reflcl 1); |
38 br subsetI 1; |
38 by (rtac subsetI 1); |
39 be r_into_rtrancl 1; |
39 by (etac r_into_rtrancl 1); |
40 bd square_sym 1; |
40 by (dtac square_sym 1); |
41 bd square_rtrancl 1; |
41 by (dtac square_rtrancl 1); |
42 by(Asm_full_simp_tac 1); |
42 by(Asm_full_simp_tac 1); |
43 bd square_sym 1; |
43 by (dtac square_sym 1); |
44 bd square_rtrancl 1; |
44 by (dtac square_rtrancl 1); |
45 by(Asm_full_simp_tac 1); |
45 by(Asm_full_simp_tac 1); |
46 qed "square_rtrancl_reflcl_commute"; |
46 qed "square_rtrancl_reflcl_commute"; |
47 |
47 |
48 (*** commute ***) |
48 (*** commute ***) |
49 |
49 |
66 "!!R. [| diamond R; diamond S; commute R S |] ==> diamond (R Un S)"; |
66 "!!R. [| diamond R; diamond S; commute R S |] ==> diamond (R Un S)"; |
67 by(REPEAT(ares_tac [commute_Un,commute_sym] 1)); |
67 by(REPEAT(ares_tac [commute_Un,commute_sym] 1)); |
68 qed "diamond_Un"; |
68 qed "diamond_Un"; |
69 |
69 |
70 goalw Commutation.thy [diamond_def] "!!R. diamond R ==> confluent (R)"; |
70 goalw Commutation.thy [diamond_def] "!!R. diamond R ==> confluent (R)"; |
71 be commute_rtrancl 1; |
71 by (etac commute_rtrancl 1); |
72 qed "diamond_confluent"; |
72 qed "diamond_confluent"; |
73 |
73 |
74 goalw Commutation.thy [diamond_def] |
74 goalw Commutation.thy [diamond_def] |
75 "!!R. square R R (R^=) (R^=) ==> confluent R"; |
75 "!!R. square R R (R^=) (R^=) ==> confluent R"; |
76 by(fast_tac (trancl_cs addIs [square_rtrancl_reflcl_commute,r_into_rtrancl] |
76 by(fast_tac (trancl_cs addIs [square_rtrancl_reflcl_commute,r_into_rtrancl] |
92 |
92 |
93 (*** Church_Rosser ***) |
93 (*** Church_Rosser ***) |
94 |
94 |
95 goalw Commutation.thy [square_def,commute_def,diamond_def,Church_Rosser_def] |
95 goalw Commutation.thy [square_def,commute_def,diamond_def,Church_Rosser_def] |
96 "Church_Rosser(R) = confluent(R)"; |
96 "Church_Rosser(R) = confluent(R)"; |
97 br iffI 1; |
97 by (rtac iffI 1); |
98 by(fast_tac (HOL_cs addIs |
98 by(fast_tac (HOL_cs addIs |
99 [Un_upper2 RS rtrancl_mono RS subsetD RS rtrancl_trans, |
99 [Un_upper2 RS rtrancl_mono RS subsetD RS rtrancl_trans, |
100 rtrancl_converseI, converseI, Un_upper1 RS rtrancl_mono RS subsetD])1); |
100 rtrancl_converseI, converseI, Un_upper1 RS rtrancl_mono RS subsetD])1); |
101 by(safe_tac HOL_cs); |
101 by(safe_tac HOL_cs); |
102 be rtrancl_induct 1; |
102 by (etac rtrancl_induct 1); |
103 by(fast_tac trancl_cs 1); |
103 by(fast_tac trancl_cs 1); |
104 by(slow_tac (rel_cs addIs [r_into_rtrancl] |
104 by(slow_tac (rel_cs addIs [r_into_rtrancl] |
105 addEs [rtrancl_trans,r_into_rtrancl RS rtrancl_trans]) 1); |
105 addEs [rtrancl_trans,r_into_rtrancl RS rtrancl_trans]) 1); |
106 qed "Church_Rosser_confluent"; |
106 qed "Church_Rosser_confluent"; |