author | paulson |
Tue, 04 Aug 1998 10:50:33 +0200 | |
changeset 5240 | bbcd79ef7cf2 |
parent 5232 | e5a7cdd07ea5 |
child 5253 | 82a5ca6290aa |
permissions | -rw-r--r-- |
4776 | 1 |
(* Title: HOL/UNITY/Reach.thy |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1998 University of Cambridge |
|
5 |
||
6 |
Reachability in Directed Graphs. From Chandy and Misra, section 6.4. |
|
4896
4727272f3db6
New syntax for function update; moved to main HOL directory
paulson
parents:
4776
diff
changeset
|
7 |
[ this example took only four days!] |
4776 | 8 |
*) |
9 |
||
10 |
(*TO SIMPDATA.ML?? FOR CLASET?? *) |
|
11 |
val major::prems = goal thy |
|
12 |
"[| if P then Q else R; \ |
|
13 |
\ [| P; Q |] ==> S; \ |
|
14 |
\ [| ~ P; R |] ==> S |] ==> S"; |
|
15 |
by (cut_facts_tac [major] 1); |
|
16 |
by (blast_tac (claset() addSDs [if_bool_eq_disj RS iffD1] addIs prems) 1); |
|
17 |
qed "ifE"; |
|
18 |
||
19 |
AddSEs [ifE]; |
|
20 |
||
21 |
||
5196 | 22 |
val cmd_defs = [racts_def, asgt_def, fun_upd_def]; |
4776 | 23 |
|
5069 | 24 |
Goalw [racts_def] "id : racts"; |
4776 | 25 |
by (Simp_tac 1); |
26 |
qed "id_in_racts"; |
|
27 |
AddIffs [id_in_racts]; |
|
28 |
||
29 |
(*All vertex sets are finite*) |
|
30 |
AddIffs [[subset_UNIV, finite_graph] MRS finite_subset]; |
|
31 |
||
5240
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
32 |
Addsimps [reach_invariant_def]; |
4776 | 33 |
|
5240
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
34 |
Goalw [rinit_def] "invariant (rinit,racts) reach_invariant"; |
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
35 |
by (rtac invariantI 1); |
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
36 |
by Auto_tac; (*for the initial state; proof of stability remains*) |
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
37 |
by (constrains_tac [racts_def, asgt_def] 1); |
4776 | 38 |
by (blast_tac (claset() addIs [r_into_rtrancl,rtrancl_trans]) 1); |
5240
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
39 |
qed "reach_invariant"; |
4776 | 40 |
|
41 |
||
42 |
(*** Fixedpoint ***) |
|
43 |
||
44 |
(*If it reaches a fixedpoint, it has found a solution*) |
|
5240
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
45 |
Goalw [fixedpoint_def, reach_invariant_def] |
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
46 |
"fixedpoint Int reach_invariant = { %v. (init, v) : edges^* }"; |
4776 | 47 |
by (rtac equalityI 1); |
48 |
by (blast_tac (claset() addIs [r_into_rtrancl,rtrancl_trans]) 2); |
|
49 |
by (auto_tac (claset() addSIs [ext], simpset())); |
|
50 |
by (etac rtrancl_induct 1); |
|
51 |
by Auto_tac; |
|
52 |
qed "fixedpoint_invariant_correct"; |
|
53 |
||
5069 | 54 |
Goalw (cmd_defs @ [FP_def, fixedpoint_def, stable_def, constrains_def]) |
4776 | 55 |
"FP racts <= fixedpoint"; |
56 |
by Auto_tac; |
|
57 |
by (dtac bspec 1); |
|
58 |
by (Blast_tac 1); |
|
59 |
by (asm_full_simp_tac (simpset() addsimps [Image_singleton, image_iff]) 1); |
|
60 |
by (dtac fun_cong 1); |
|
61 |
by Auto_tac; |
|
62 |
val lemma1 = result(); |
|
63 |
||
5069 | 64 |
Goalw (cmd_defs @ [FP_def, fixedpoint_def, stable_def, constrains_def]) |
4776 | 65 |
"fixedpoint <= FP racts"; |
66 |
by (auto_tac (claset() addIs [ext], simpset())); |
|
67 |
val lemma2 = result(); |
|
68 |
||
5069 | 69 |
Goal "FP racts = fixedpoint"; |
4776 | 70 |
by (rtac ([lemma1,lemma2] MRS equalityI) 1); |
71 |
qed "FP_fixedpoint"; |
|
72 |
||
73 |
||
74 |
(*If we haven't reached a fixedpoint then there is some edge for which u but |
|
75 |
not v holds. Progress will be proved via an ENSURES assertion that the |
|
76 |
metric will decrease for each suitable edge. A union over all edges proves |
|
77 |
a LEADSTO assertion that the metric decreases if we are not at a fixedpoint. |
|
78 |
*) |
|
79 |
||
5069 | 80 |
Goal "Compl fixedpoint = (UN (u,v): edges. {s. s u & ~ s v})"; |
4776 | 81 |
by (simp_tac (simpset() addsimps |
82 |
([Compl_FP, UN_UN_flatten, FP_fixedpoint RS sym, |
|
83 |
racts_def, asgt_def])) 1); |
|
84 |
by Safe_tac; |
|
5196 | 85 |
by (rtac fun_upd_idem 1); |
4776 | 86 |
by (Blast_tac 1); |
87 |
by (Full_simp_tac 1); |
|
88 |
by (REPEAT (dtac bspec 1 THEN Simp_tac 1)); |
|
89 |
by (dtac subsetD 1); |
|
90 |
by (Simp_tac 1); |
|
5196 | 91 |
by (asm_full_simp_tac (simpset() addsimps [fun_upd_idem_iff]) 1); |
4776 | 92 |
qed "Compl_fixedpoint"; |
93 |
||
5069 | 94 |
Goal "A - fixedpoint = (UN (u,v): edges. A Int {s. s u & ~ s v})"; |
4776 | 95 |
by (simp_tac (simpset() addsimps [Diff_eq, Compl_fixedpoint]) 1); |
96 |
by (Blast_tac 1); |
|
97 |
qed "Diff_fixedpoint"; |
|
98 |
||
99 |
||
100 |
(*** Progress ***) |
|
101 |
||
5111 | 102 |
Goalw [metric_def] "~ s x ==> Suc (metric (s(x:=True))) = metric s"; |
5071
548f398d770b
Consequences of the change from [ := ] to ( := ) in theory Update.
nipkow
parents:
5069
diff
changeset
|
103 |
by (subgoal_tac "{v. ~ (s(x:=True)) v} = {v. ~ s v} - {x}" 1); |
4776 | 104 |
by Auto_tac; |
105 |
by (asm_simp_tac (simpset() addsimps [card_Suc_Diff]) 1); |
|
106 |
qed "Suc_metric"; |
|
107 |
||
5111 | 108 |
Goal "~ s x ==> metric (s(x:=True)) < metric s"; |
4776 | 109 |
by (etac (Suc_metric RS subst) 1); |
110 |
by (Blast_tac 1); |
|
111 |
qed "metric_less"; |
|
112 |
AddSIs [metric_less]; |
|
113 |
||
5071
548f398d770b
Consequences of the change from [ := ] to ( := ) in theory Update.
nipkow
parents:
5069
diff
changeset
|
114 |
Goal "metric (s(y:=s x | s y)) <= metric s"; |
4776 | 115 |
by (case_tac "s x --> s y" 1); |
116 |
by (auto_tac (claset() addIs [less_imp_le], |
|
5196 | 117 |
simpset() addsimps [fun_upd_idem])); |
4776 | 118 |
qed "metric_le"; |
119 |
||
5111 | 120 |
Goal "(u,v): edges ==> \ |
4776 | 121 |
\ ensures racts ((metric-``{m}) Int {s. s u & ~ s v}) \ |
122 |
\ (metric-``(lessThan m))"; |
|
5240
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
123 |
by (ensures_tac [racts_def, asgt_def] "asgt u v" 1); |
4776 | 124 |
by (cut_facts_tac [metric_le] 1); |
125 |
by (fast_tac (claset() addSDs [le_imp_less_or_eq]) 1); |
|
126 |
qed "edges_ensures"; |
|
127 |
||
5069 | 128 |
Goal "leadsTo racts ((metric-``{m}) - fixedpoint) (metric-``(lessThan m))"; |
4776 | 129 |
by (simp_tac (simpset() addsimps [Diff_fixedpoint]) 1); |
130 |
by (rtac leadsTo_UN 1); |
|
131 |
by (split_all_tac 1); |
|
132 |
by (asm_simp_tac (simpset() addsimps [edges_ensures RS leadsTo_Basis]) 1); |
|
133 |
qed "leadsTo_Diff_fixedpoint"; |
|
134 |
||
5069 | 135 |
Goal "leadsTo racts (metric-``{m}) (metric-``(lessThan m) Un fixedpoint)"; |
4776 | 136 |
by (rtac (leadsTo_Diff_fixedpoint RS leadsTo_weaken_R RS leadsTo_Diff) 1); |
137 |
by (ALLGOALS (blast_tac (claset() addIs [subset_imp_leadsTo]))); |
|
138 |
qed "leadsTo_Un_fixedpoint"; |
|
139 |
||
140 |
||
141 |
(*Execution in any state leads to a fixedpoint (i.e. can terminate)*) |
|
5069 | 142 |
Goal "leadsTo racts UNIV fixedpoint"; |
4776 | 143 |
by (rtac lessThan_induct 1); |
144 |
by Auto_tac; |
|
145 |
by (rtac leadsTo_Un_fixedpoint 1); |
|
146 |
qed "leadsTo_fixedpoint"; |
|
147 |
||
5111 | 148 |
Goal "LeadsTo(rinit,racts) UNIV { %v. (init, v) : edges^* }"; |
4776 | 149 |
by (stac (fixedpoint_invariant_correct RS sym) 1); |
5240
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
150 |
by (rtac ([reach_invariant, |
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
151 |
leadsTo_fixedpoint RS leadsTo_imp_LeadsTo] |
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
152 |
MRS invariant_LeadsTo_weaken) 1); |
bbcd79ef7cf2
Constant "invariant" and new constrains_tac, ensures_tac
paulson
parents:
5232
diff
changeset
|
153 |
by Auto_tac; |
4776 | 154 |
qed "LeadsTo_correct"; |