author | huffman |
Wed, 17 Feb 2010 10:00:22 -0800 | |
changeset 35174 | e15040ae75d7 |
parent 27208 | 5fe899199f85 |
child 35215 | a03462cbf86f |
permissions | -rw-r--r-- |
3071 | 1 |
(* Title: HOLCF/IOA/meta_theory/CompoTraces.thy |
12218 | 2 |
Author: Olaf Müller |
3071 | 3 |
*) |
4 |
||
17233 | 5 |
header {* Compositionality on Trace level *} |
6 |
||
7 |
theory CompoTraces |
|
8 |
imports CompoScheds ShortExecutions |
|
9 |
begin |
|
3071 | 10 |
|
11 |
||
12 |
consts |
|
13 |
||
3521 | 14 |
mksch ::"('a,'s)ioa => ('a,'t)ioa => 'a Seq -> 'a Seq -> 'a Seq -> 'a Seq" |
15 |
par_traces ::"['a trace_module,'a trace_module] => 'a trace_module" |
|
3071 | 16 |
|
17 |
defs |
|
18 |
||
17233 | 19 |
mksch_def: |
10835 | 20 |
"mksch A B == (fix$(LAM h tr schA schB. case tr of |
3071 | 21 |
nil => nil |
22 |
| x##xs => |
|
23 |
(case x of |
|
12028 | 24 |
UU => UU |
3071 | 25 |
| Def y => |
26 |
(if y:act A then |
|
27 |
(if y:act B then |
|
10835 | 28 |
((Takewhile (%a. a:int A)$schA) |
29 |
@@ (Takewhile (%a. a:int B)$schB) |
|
30 |
@@ (y>>(h$xs |
|
31 |
$(TL$(Dropwhile (%a. a:int A)$schA)) |
|
32 |
$(TL$(Dropwhile (%a. a:int B)$schB)) |
|
3071 | 33 |
))) |
34 |
else |
|
10835 | 35 |
((Takewhile (%a. a:int A)$schA) |
36 |
@@ (y>>(h$xs |
|
37 |
$(TL$(Dropwhile (%a. a:int A)$schA)) |
|
38 |
$schB))) |
|
3071 | 39 |
) |
40 |
else |
|
41 |
(if y:act B then |
|
10835 | 42 |
((Takewhile (%a. a:int B)$schB) |
43 |
@@ (y>>(h$xs |
|
44 |
$schA |
|
45 |
$(TL$(Dropwhile (%a. a:int B)$schB)) |
|
3071 | 46 |
))) |
47 |
else |
|
48 |
UU |
|
49 |
) |
|
50 |
) |
|
51 |
)))" |
|
52 |
||
53 |
||
17233 | 54 |
par_traces_def: |
3521 | 55 |
"par_traces TracesA TracesB == |
56 |
let trA = fst TracesA; sigA = snd TracesA; |
|
57 |
trB = fst TracesB; sigB = snd TracesB |
|
58 |
in |
|
10835 | 59 |
( {tr. Filter (%a. a:actions sigA)$tr : trA} |
60 |
Int {tr. Filter (%a. a:actions sigB)$tr : trB} |
|
3521 | 61 |
Int {tr. Forall (%x. x:(externals sigA Un externals sigB)) tr}, |
62 |
asig_comp sigA sigB)" |
|
63 |
||
17233 | 64 |
axioms |
3071 | 65 |
|
17233 | 66 |
finiteR_mksch: |
10835 | 67 |
"Finite (mksch A B$tr$x$y) --> Finite tr" |
3071 | 68 |
|
19741 | 69 |
|
26339 | 70 |
declaration {* fn _ => Simplifier.map_ss (fn ss => ss setmksym (K NONE)) *} |
19741 | 71 |
|
72 |
||
73 |
subsection "mksch rewrite rules" |
|
74 |
||
75 |
lemma mksch_unfold: |
|
76 |
"mksch A B = (LAM tr schA schB. case tr of |
|
77 |
nil => nil |
|
78 |
| x##xs => |
|
79 |
(case x of |
|
80 |
UU => UU |
|
81 |
| Def y => |
|
82 |
(if y:act A then |
|
83 |
(if y:act B then |
|
84 |
((Takewhile (%a. a:int A)$schA) |
|
85 |
@@(Takewhile (%a. a:int B)$schB) |
|
86 |
@@(y>>(mksch A B$xs |
|
87 |
$(TL$(Dropwhile (%a. a:int A)$schA)) |
|
88 |
$(TL$(Dropwhile (%a. a:int B)$schB)) |
|
89 |
))) |
|
90 |
else |
|
91 |
((Takewhile (%a. a:int A)$schA) |
|
92 |
@@ (y>>(mksch A B$xs |
|
93 |
$(TL$(Dropwhile (%a. a:int A)$schA)) |
|
94 |
$schB))) |
|
95 |
) |
|
96 |
else |
|
97 |
(if y:act B then |
|
98 |
((Takewhile (%a. a:int B)$schB) |
|
99 |
@@ (y>>(mksch A B$xs |
|
100 |
$schA |
|
101 |
$(TL$(Dropwhile (%a. a:int B)$schB)) |
|
102 |
))) |
|
103 |
else |
|
104 |
UU |
|
105 |
) |
|
106 |
) |
|
107 |
))" |
|
108 |
apply (rule trans) |
|
109 |
apply (rule fix_eq2) |
|
110 |
apply (rule mksch_def) |
|
111 |
apply (rule beta_cfun) |
|
112 |
apply simp |
|
113 |
done |
|
114 |
||
115 |
lemma mksch_UU: "mksch A B$UU$schA$schB = UU" |
|
116 |
apply (subst mksch_unfold) |
|
117 |
apply simp |
|
118 |
done |
|
119 |
||
120 |
lemma mksch_nil: "mksch A B$nil$schA$schB = nil" |
|
121 |
apply (subst mksch_unfold) |
|
122 |
apply simp |
|
123 |
done |
|
124 |
||
125 |
lemma mksch_cons1: "[|x:act A;x~:act B|] |
|
126 |
==> mksch A B$(x>>tr)$schA$schB = |
|
127 |
(Takewhile (%a. a:int A)$schA) |
|
128 |
@@ (x>>(mksch A B$tr$(TL$(Dropwhile (%a. a:int A)$schA)) |
|
129 |
$schB))" |
|
130 |
apply (rule trans) |
|
131 |
apply (subst mksch_unfold) |
|
132 |
apply (simp add: Consq_def If_and_if) |
|
133 |
apply (simp add: Consq_def) |
|
134 |
done |
|
135 |
||
136 |
lemma mksch_cons2: "[|x~:act A;x:act B|] |
|
137 |
==> mksch A B$(x>>tr)$schA$schB = |
|
138 |
(Takewhile (%a. a:int B)$schB) |
|
139 |
@@ (x>>(mksch A B$tr$schA$(TL$(Dropwhile (%a. a:int B)$schB)) |
|
140 |
))" |
|
141 |
apply (rule trans) |
|
142 |
apply (subst mksch_unfold) |
|
143 |
apply (simp add: Consq_def If_and_if) |
|
144 |
apply (simp add: Consq_def) |
|
145 |
done |
|
146 |
||
147 |
lemma mksch_cons3: "[|x:act A;x:act B|] |
|
148 |
==> mksch A B$(x>>tr)$schA$schB = |
|
149 |
(Takewhile (%a. a:int A)$schA) |
|
150 |
@@ ((Takewhile (%a. a:int B)$schB) |
|
151 |
@@ (x>>(mksch A B$tr$(TL$(Dropwhile (%a. a:int A)$schA)) |
|
152 |
$(TL$(Dropwhile (%a. a:int B)$schB)))) |
|
153 |
)" |
|
154 |
apply (rule trans) |
|
155 |
apply (subst mksch_unfold) |
|
156 |
apply (simp add: Consq_def If_and_if) |
|
157 |
apply (simp add: Consq_def) |
|
158 |
done |
|
159 |
||
160 |
lemmas compotr_simps = mksch_UU mksch_nil mksch_cons1 mksch_cons2 mksch_cons3 |
|
161 |
||
162 |
declare compotr_simps [simp] |
|
163 |
||
164 |
||
165 |
subsection {* COMPOSITIONALITY on TRACE Level *} |
|
166 |
||
167 |
subsubsection "Lemmata for ==>" |
|
168 |
||
169 |
(* Consequence out of ext1_ext2_is_not_act1(2), which in turn are consequences out of |
|
170 |
the compatibility of IOA, in particular out of the condition that internals are |
|
171 |
really hidden. *) |
|
172 |
||
173 |
lemma compatibility_consequence1: "(eB & ~eA --> ~A) --> |
|
174 |
(A & (eA | eB)) = (eA & A)" |
|
175 |
apply fast |
|
176 |
done |
|
177 |
||
178 |
||
179 |
(* very similar to above, only the commutativity of | is used to make a slight change *) |
|
180 |
||
181 |
lemma compatibility_consequence2: "(eB & ~eA --> ~A) --> |
|
182 |
(A & (eB | eA)) = (eA & A)" |
|
183 |
apply fast |
|
184 |
done |
|
185 |
||
186 |
||
187 |
subsubsection "Lemmata for <==" |
|
188 |
||
189 |
(* Lemma for substitution of looping assumption in another specific assumption *) |
|
190 |
lemma subst_lemma1: "[| f << (g x) ; x=(h x) |] ==> f << g (h x)" |
|
191 |
by (erule subst) |
|
192 |
||
193 |
(* Lemma for substitution of looping assumption in another specific assumption *) |
|
194 |
lemma subst_lemma2: "[| (f x) = y >> g; x=(h x) |] ==> (f (h x)) = y >> g" |
|
195 |
by (erule subst) |
|
196 |
||
197 |
lemma ForallAorB_mksch [rule_format]: |
|
198 |
"!!A B. compatible A B ==> |
|
199 |
! schA schB. Forall (%x. x:act (A||B)) tr |
|
200 |
--> Forall (%x. x:act (A||B)) (mksch A B$tr$schA$schB)" |
|
27208
5fe899199f85
proper context for tactics derived from res_inst_tac;
wenzelm
parents:
26359
diff
changeset
|
201 |
apply (tactic {* Seq_induct_tac @{context} "tr" |
5fe899199f85
proper context for tactics derived from res_inst_tac;
wenzelm
parents:
26359
diff
changeset
|
202 |
[@{thm Forall_def}, @{thm sforall_def}, @{thm mksch_def}] 1 *}) |
26359 | 203 |
apply auto |
19741 | 204 |
apply (simp add: actions_of_par) |
205 |
apply (case_tac "a:act A") |
|
206 |
apply (case_tac "a:act B") |
|
207 |
(* a:A, a:B *) |
|
208 |
apply simp |
|
209 |
apply (rule Forall_Conc_impl [THEN mp]) |
|
210 |
apply (simp add: ForallPTakewhileQ intA_is_not_actB int_is_act) |
|
211 |
apply (rule Forall_Conc_impl [THEN mp]) |
|
212 |
apply (simp add: ForallPTakewhileQ intA_is_not_actB int_is_act) |
|
213 |
(* a:A,a~:B *) |
|
214 |
apply simp |
|
215 |
apply (rule Forall_Conc_impl [THEN mp]) |
|
216 |
apply (simp add: ForallPTakewhileQ intA_is_not_actB int_is_act) |
|
217 |
apply (case_tac "a:act B") |
|
218 |
(* a~:A, a:B *) |
|
219 |
apply simp |
|
220 |
apply (rule Forall_Conc_impl [THEN mp]) |
|
221 |
apply (simp add: ForallPTakewhileQ intA_is_not_actB int_is_act) |
|
222 |
(* a~:A,a~:B *) |
|
223 |
apply auto |
|
224 |
done |
|
225 |
||
226 |
lemma ForallBnAmksch [rule_format (no_asm)]: "!!A B. compatible B A ==> |
|
227 |
! schA schB. (Forall (%x. x:act B & x~:act A) tr |
|
228 |
--> Forall (%x. x:act B & x~:act A) (mksch A B$tr$schA$schB))" |
|
27208
5fe899199f85
proper context for tactics derived from res_inst_tac;
wenzelm
parents:
26359
diff
changeset
|
229 |
apply (tactic {* Seq_induct_tac @{context} "tr" |
5fe899199f85
proper context for tactics derived from res_inst_tac;
wenzelm
parents:
26359
diff
changeset
|
230 |
[@{thm Forall_def}, @{thm sforall_def}, @{thm mksch_def}] 1 *}) |
26359 | 231 |
apply auto |
19741 | 232 |
apply (rule Forall_Conc_impl [THEN mp]) |
233 |
apply (simp add: ForallPTakewhileQ intA_is_not_actB int_is_act) |
|
234 |
done |
|
235 |
||
236 |
lemma ForallAnBmksch [rule_format (no_asm)]: "!!A B. compatible A B ==> |
|
237 |
! schA schB. (Forall (%x. x:act A & x~:act B) tr |
|
238 |
--> Forall (%x. x:act A & x~:act B) (mksch A B$tr$schA$schB))" |
|
27208
5fe899199f85
proper context for tactics derived from res_inst_tac;
wenzelm
parents:
26359
diff
changeset
|
239 |
apply (tactic {* Seq_induct_tac @{context} "tr" |
5fe899199f85
proper context for tactics derived from res_inst_tac;
wenzelm
parents:
26359
diff
changeset
|
240 |
[@{thm Forall_def}, @{thm sforall_def}, @{thm mksch_def}] 1 *}) |
26359 | 241 |
apply auto |
19741 | 242 |
apply (rule Forall_Conc_impl [THEN mp]) |
243 |
apply (simp add: ForallPTakewhileQ intA_is_not_actB int_is_act) |
|
244 |
done |
|
245 |
||
246 |
(* safe-tac makes too many case distinctions with this lemma in the next proof *) |
|
247 |
declare FiniteConc [simp del] |
|
248 |
||
249 |
lemma FiniteL_mksch [rule_format (no_asm)]: "[| Finite tr; is_asig(asig_of A); is_asig(asig_of B) |] ==> |
|
250 |
! x y. Forall (%x. x:act A) x & Forall (%x. x:act B) y & |
|
251 |
Filter (%a. a:ext A)$x = Filter (%a. a:act A)$tr & |
|
252 |
Filter (%a. a:ext B)$y = Filter (%a. a:act B)$tr & |
|
253 |
Forall (%x. x:ext (A||B)) tr |
|
254 |
--> Finite (mksch A B$tr$x$y)" |
|
255 |
||
256 |
apply (erule Seq_Finite_ind) |
|
257 |
apply simp |
|
258 |
(* main case *) |
|
259 |
apply simp |
|
26359 | 260 |
apply auto |
19741 | 261 |
|
262 |
(* a: act A; a: act B *) |
|
263 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
264 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
265 |
back |
|
266 |
apply (erule conjE)+ |
|
267 |
(* Finite (tw iA x) and Finite (tw iB y) *) |
|
268 |
apply (simp add: not_ext_is_int_or_not_act FiniteConc) |
|
269 |
(* now for conclusion IH applicable, but assumptions have to be transformed *) |
|
270 |
apply (drule_tac x = "x" and g = "Filter (%a. a:act A) $s" in subst_lemma2) |
|
271 |
apply assumption |
|
272 |
apply (drule_tac x = "y" and g = "Filter (%a. a:act B) $s" in subst_lemma2) |
|
273 |
apply assumption |
|
274 |
(* IH *) |
|
275 |
apply (simp add: not_ext_is_int_or_not_act ForallTL ForallDropwhile) |
|
276 |
||
277 |
(* a: act B; a~: act A *) |
|
278 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
279 |
||
280 |
apply (erule conjE)+ |
|
281 |
(* Finite (tw iB y) *) |
|
282 |
apply (simp add: not_ext_is_int_or_not_act FiniteConc) |
|
283 |
(* now for conclusion IH applicable, but assumptions have to be transformed *) |
|
284 |
apply (drule_tac x = "y" and g = "Filter (%a. a:act B) $s" in subst_lemma2) |
|
285 |
apply assumption |
|
286 |
(* IH *) |
|
287 |
apply (simp add: not_ext_is_int_or_not_act ForallTL ForallDropwhile) |
|
288 |
||
289 |
(* a~: act B; a: act A *) |
|
290 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
291 |
||
292 |
apply (erule conjE)+ |
|
293 |
(* Finite (tw iA x) *) |
|
294 |
apply (simp add: not_ext_is_int_or_not_act FiniteConc) |
|
295 |
(* now for conclusion IH applicable, but assumptions have to be transformed *) |
|
296 |
apply (drule_tac x = "x" and g = "Filter (%a. a:act A) $s" in subst_lemma2) |
|
297 |
apply assumption |
|
298 |
(* IH *) |
|
299 |
apply (simp add: not_ext_is_int_or_not_act ForallTL ForallDropwhile) |
|
300 |
||
301 |
(* a~: act B; a~: act A *) |
|
302 |
apply (fastsimp intro!: ext_is_act simp: externals_of_par) |
|
303 |
done |
|
304 |
||
305 |
declare FiniteConc [simp] |
|
306 |
||
307 |
declare FilterConc [simp del] |
|
308 |
||
309 |
lemma reduceA_mksch1 [rule_format (no_asm)]: " [| Finite bs; is_asig(asig_of A); is_asig(asig_of B);compatible A B|] ==> |
|
310 |
! y. Forall (%x. x:act B) y & Forall (%x. x:act B & x~:act A) bs & |
|
311 |
Filter (%a. a:ext B)$y = Filter (%a. a:act B)$(bs @@ z) |
|
312 |
--> (? y1 y2. (mksch A B$(bs @@ z)$x$y) = (y1 @@ (mksch A B$z$x$y2)) & |
|
313 |
Forall (%x. x:act B & x~:act A) y1 & |
|
314 |
Finite y1 & y = (y1 @@ y2) & |
|
315 |
Filter (%a. a:ext B)$y1 = bs)" |
|
316 |
apply (frule_tac A1 = "A" in compat_commute [THEN iffD1]) |
|
317 |
apply (erule Seq_Finite_ind) |
|
318 |
apply (rule allI)+ |
|
319 |
apply (rule impI) |
|
320 |
apply (rule_tac x = "nil" in exI) |
|
321 |
apply (rule_tac x = "y" in exI) |
|
322 |
apply simp |
|
323 |
(* main case *) |
|
324 |
apply (rule allI)+ |
|
325 |
apply (rule impI) |
|
326 |
apply simp |
|
327 |
apply (erule conjE)+ |
|
328 |
apply simp |
|
329 |
(* divide_Seq on s *) |
|
330 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
331 |
apply (erule conjE)+ |
|
332 |
(* transform assumption f eB y = f B (s@z) *) |
|
333 |
apply (drule_tac x = "y" and g = "Filter (%a. a:act B) $ (s@@z) " in subst_lemma2) |
|
334 |
apply assumption |
|
335 |
apply (simp add: not_ext_is_int_or_not_act FilterConc) |
|
336 |
(* apply IH *) |
|
337 |
apply (erule_tac x = "TL$ (Dropwhile (%a. a:int B) $y) " in allE) |
|
338 |
apply (simp add: ForallTL ForallDropwhile FilterConc) |
|
339 |
apply (erule exE)+ |
|
340 |
apply (erule conjE)+ |
|
341 |
apply (simp add: FilterConc) |
|
342 |
(* for replacing IH in conclusion *) |
|
343 |
apply (rotate_tac -2) |
|
344 |
(* instantiate y1a and y2a *) |
|
345 |
apply (rule_tac x = "Takewhile (%a. a:int B) $y @@ a>>y1" in exI) |
|
346 |
apply (rule_tac x = "y2" in exI) |
|
347 |
(* elminate all obligations up to two depending on Conc_assoc *) |
|
348 |
apply (simp add: ForallPTakewhileQ intA_is_not_actB int_is_act int_is_not_ext FilterConc) |
|
349 |
apply (simp (no_asm) add: Conc_assoc FilterConc) |
|
350 |
done |
|
351 |
||
352 |
lemmas reduceA_mksch = conjI [THEN [6] conjI [THEN [5] reduceA_mksch1]] |
|
353 |
||
354 |
declare FilterConc [simp del] |
|
355 |
||
356 |
lemma reduceB_mksch1 [rule_format]: |
|
357 |
" [| Finite a_s; is_asig(asig_of A); is_asig(asig_of B);compatible A B|] ==> |
|
358 |
! x. Forall (%x. x:act A) x & Forall (%x. x:act A & x~:act B) a_s & |
|
359 |
Filter (%a. a:ext A)$x = Filter (%a. a:act A)$(a_s @@ z) |
|
360 |
--> (? x1 x2. (mksch A B$(a_s @@ z)$x$y) = (x1 @@ (mksch A B$z$x2$y)) & |
|
361 |
Forall (%x. x:act A & x~:act B) x1 & |
|
362 |
Finite x1 & x = (x1 @@ x2) & |
|
363 |
Filter (%a. a:ext A)$x1 = a_s)" |
|
364 |
apply (frule_tac A1 = "A" in compat_commute [THEN iffD1]) |
|
365 |
apply (erule Seq_Finite_ind) |
|
366 |
apply (rule allI)+ |
|
367 |
apply (rule impI) |
|
368 |
apply (rule_tac x = "nil" in exI) |
|
369 |
apply (rule_tac x = "x" in exI) |
|
370 |
apply simp |
|
371 |
(* main case *) |
|
372 |
apply (rule allI)+ |
|
373 |
apply (rule impI) |
|
374 |
apply simp |
|
375 |
apply (erule conjE)+ |
|
376 |
apply simp |
|
377 |
(* divide_Seq on s *) |
|
378 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
379 |
apply (erule conjE)+ |
|
380 |
(* transform assumption f eA x = f A (s@z) *) |
|
381 |
apply (drule_tac x = "x" and g = "Filter (%a. a:act A) $ (s@@z) " in subst_lemma2) |
|
382 |
apply assumption |
|
383 |
apply (simp add: not_ext_is_int_or_not_act FilterConc) |
|
384 |
(* apply IH *) |
|
385 |
apply (erule_tac x = "TL$ (Dropwhile (%a. a:int A) $x) " in allE) |
|
386 |
apply (simp add: ForallTL ForallDropwhile FilterConc) |
|
387 |
apply (erule exE)+ |
|
388 |
apply (erule conjE)+ |
|
389 |
apply (simp add: FilterConc) |
|
390 |
(* for replacing IH in conclusion *) |
|
391 |
apply (rotate_tac -2) |
|
392 |
(* instantiate y1a and y2a *) |
|
393 |
apply (rule_tac x = "Takewhile (%a. a:int A) $x @@ a>>x1" in exI) |
|
394 |
apply (rule_tac x = "x2" in exI) |
|
395 |
(* elminate all obligations up to two depending on Conc_assoc *) |
|
396 |
apply (simp add: ForallPTakewhileQ intA_is_not_actB int_is_act int_is_not_ext FilterConc) |
|
397 |
apply (simp (no_asm) add: Conc_assoc FilterConc) |
|
398 |
done |
|
399 |
||
400 |
lemmas reduceB_mksch = conjI [THEN [6] conjI [THEN [5] reduceB_mksch1]] |
|
401 |
||
402 |
declare FilterConc [simp] |
|
403 |
||
404 |
||
405 |
subsection "Filtering external actions out of mksch(tr,schA,schB) yields the oracle tr" |
|
406 |
||
407 |
lemma FilterA_mksch_is_tr: |
|
408 |
"!! A B. [| compatible A B; compatible B A; |
|
409 |
is_asig(asig_of A); is_asig(asig_of B) |] ==> |
|
410 |
! schA schB. Forall (%x. x:act A) schA & Forall (%x. x:act B) schB & |
|
411 |
Forall (%x. x:ext (A||B)) tr & |
|
412 |
Filter (%a. a:act A)$tr << Filter (%a. a:ext A)$schA & |
|
413 |
Filter (%a. a:act B)$tr << Filter (%a. a:ext B)$schB |
|
414 |
--> Filter (%a. a:ext (A||B))$(mksch A B$tr$schA$schB) = tr" |
|
415 |
||
27208
5fe899199f85
proper context for tactics derived from res_inst_tac;
wenzelm
parents:
26359
diff
changeset
|
416 |
apply (tactic {* Seq_induct_tac @{context} "tr" |
5fe899199f85
proper context for tactics derived from res_inst_tac;
wenzelm
parents:
26359
diff
changeset
|
417 |
[@{thm Forall_def}, @{thm sforall_def}, @{thm mksch_def}] 1 *}) |
19741 | 418 |
(* main case *) |
419 |
(* splitting into 4 cases according to a:A, a:B *) |
|
26359 | 420 |
apply auto |
19741 | 421 |
|
422 |
(* Case a:A, a:B *) |
|
423 |
apply (frule divide_Seq) |
|
424 |
apply (frule divide_Seq) |
|
425 |
back |
|
426 |
apply (erule conjE)+ |
|
427 |
(* filtering internals of A in schA and of B in schB is nil *) |
|
428 |
apply (simp add: not_ext_is_int_or_not_act externals_of_par intA_is_not_extB int_is_not_ext) |
|
429 |
(* conclusion of IH ok, but assumptions of IH have to be transformed *) |
|
430 |
apply (drule_tac x = "schA" in subst_lemma1) |
|
431 |
apply assumption |
|
432 |
apply (drule_tac x = "schB" in subst_lemma1) |
|
433 |
apply assumption |
|
434 |
(* IH *) |
|
435 |
apply (simp add: not_ext_is_int_or_not_act ForallTL ForallDropwhile) |
|
436 |
||
437 |
(* Case a:A, a~:B *) |
|
438 |
apply (frule divide_Seq) |
|
439 |
apply (erule conjE)+ |
|
440 |
(* filtering internals of A is nil *) |
|
441 |
apply (simp add: not_ext_is_int_or_not_act externals_of_par intA_is_not_extB int_is_not_ext) |
|
442 |
apply (drule_tac x = "schA" in subst_lemma1) |
|
443 |
apply assumption |
|
444 |
apply (simp add: not_ext_is_int_or_not_act ForallTL ForallDropwhile) |
|
445 |
||
446 |
(* Case a:B, a~:A *) |
|
447 |
apply (frule divide_Seq) |
|
448 |
apply (erule conjE)+ |
|
449 |
(* filtering internals of A is nil *) |
|
450 |
apply (simp add: not_ext_is_int_or_not_act externals_of_par intA_is_not_extB int_is_not_ext) |
|
451 |
apply (drule_tac x = "schB" in subst_lemma1) |
|
452 |
back |
|
453 |
apply assumption |
|
454 |
apply (simp add: not_ext_is_int_or_not_act ForallTL ForallDropwhile) |
|
455 |
||
456 |
(* Case a~:A, a~:B *) |
|
457 |
apply (fastsimp intro!: ext_is_act simp: externals_of_par) |
|
458 |
done |
|
459 |
||
460 |
||
461 |
subsection" Filter of mksch(tr,schA,schB) to A is schA -- take lemma proof" |
|
462 |
||
463 |
lemma FilterAmksch_is_schA: "!! A B. [| compatible A B; compatible B A; |
|
464 |
is_asig(asig_of A); is_asig(asig_of B) |] ==> |
|
465 |
Forall (%x. x:ext (A||B)) tr & |
|
466 |
Forall (%x. x:act A) schA & Forall (%x. x:act B) schB & |
|
467 |
Filter (%a. a:ext A)$schA = Filter (%a. a:act A)$tr & |
|
468 |
Filter (%a. a:ext B)$schB = Filter (%a. a:act B)$tr & |
|
469 |
LastActExtsch A schA & LastActExtsch B schB |
|
470 |
--> Filter (%a. a:act A)$(mksch A B$tr$schA$schB) = schA" |
|
471 |
apply (intro strip) |
|
472 |
apply (rule seq.take_lemmas) |
|
473 |
apply (rule mp) |
|
474 |
prefer 2 apply assumption |
|
475 |
back back back back |
|
476 |
apply (rule_tac x = "schA" in spec) |
|
477 |
apply (rule_tac x = "schB" in spec) |
|
478 |
apply (rule_tac x = "tr" in spec) |
|
479 |
apply (tactic "thin_tac' 5 1") |
|
480 |
apply (rule nat_less_induct) |
|
481 |
apply (rule allI)+ |
|
482 |
apply (rename_tac tr schB schA) |
|
483 |
apply (intro strip) |
|
484 |
apply (erule conjE)+ |
|
485 |
||
486 |
apply (case_tac "Forall (%x. x:act B & x~:act A) tr") |
|
487 |
||
488 |
apply (rule seq_take_lemma [THEN iffD2, THEN spec]) |
|
489 |
apply (tactic "thin_tac' 5 1") |
|
490 |
||
491 |
||
492 |
apply (case_tac "Finite tr") |
|
493 |
||
494 |
(* both sides of this equation are nil *) |
|
495 |
apply (subgoal_tac "schA=nil") |
|
496 |
apply (simp (no_asm_simp)) |
|
497 |
(* first side: mksch = nil *) |
|
498 |
apply (auto intro!: ForallQFilterPnil ForallBnAmksch FiniteL_mksch)[1] |
|
499 |
(* second side: schA = nil *) |
|
500 |
apply (erule_tac A = "A" in LastActExtimplnil) |
|
501 |
apply (simp (no_asm_simp)) |
|
502 |
apply (erule_tac Q = "%x. x:act B & x~:act A" in ForallQFilterPnil) |
|
503 |
apply assumption |
|
504 |
apply fast |
|
505 |
||
506 |
(* case ~ Finite s *) |
|
507 |
||
508 |
(* both sides of this equation are UU *) |
|
509 |
apply (subgoal_tac "schA=UU") |
|
510 |
apply (simp (no_asm_simp)) |
|
511 |
(* first side: mksch = UU *) |
|
512 |
apply (auto intro!: ForallQFilterPUU finiteR_mksch [THEN mp, COMP rev_contrapos] ForallBnAmksch)[1] |
|
513 |
(* schA = UU *) |
|
514 |
apply (erule_tac A = "A" in LastActExtimplUU) |
|
515 |
apply (simp (no_asm_simp)) |
|
516 |
apply (erule_tac Q = "%x. x:act B & x~:act A" in ForallQFilterPUU) |
|
517 |
apply assumption |
|
518 |
apply fast |
|
519 |
||
520 |
(* case" ~ Forall (%x.x:act B & x~:act A) s" *) |
|
521 |
||
522 |
apply (drule divide_Seq3) |
|
523 |
||
524 |
apply (erule exE)+ |
|
525 |
apply (erule conjE)+ |
|
526 |
apply hypsubst |
|
527 |
||
528 |
(* bring in lemma reduceA_mksch *) |
|
529 |
apply (frule_tac x = "schA" and y = "schB" and A = "A" and B = "B" in reduceA_mksch) |
|
530 |
apply assumption+ |
|
531 |
apply (erule exE)+ |
|
532 |
apply (erule conjE)+ |
|
533 |
||
534 |
(* use reduceA_mksch to rewrite conclusion *) |
|
535 |
apply hypsubst |
|
536 |
apply simp |
|
537 |
||
538 |
(* eliminate the B-only prefix *) |
|
539 |
||
540 |
apply (subgoal_tac " (Filter (%a. a :act A) $y1) = nil") |
|
541 |
apply (erule_tac [2] ForallQFilterPnil) |
|
542 |
prefer 2 apply assumption |
|
543 |
prefer 2 apply fast |
|
544 |
||
545 |
(* Now real recursive step follows (in y) *) |
|
546 |
||
547 |
apply simp |
|
548 |
apply (case_tac "x:act A") |
|
549 |
apply (case_tac "x~:act B") |
|
550 |
apply (rotate_tac -2) |
|
551 |
apply simp |
|
552 |
||
553 |
apply (subgoal_tac "Filter (%a. a:act A & a:ext B) $y1=nil") |
|
554 |
apply (rotate_tac -1) |
|
555 |
apply simp |
|
556 |
(* eliminate introduced subgoal 2 *) |
|
557 |
apply (erule_tac [2] ForallQFilterPnil) |
|
558 |
prefer 2 apply assumption |
|
559 |
prefer 2 apply fast |
|
560 |
||
561 |
(* bring in divide Seq for s *) |
|
562 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
563 |
apply (erule conjE)+ |
|
564 |
||
565 |
(* subst divide_Seq in conclusion, but only at the righest occurence *) |
|
566 |
apply (rule_tac t = "schA" in ssubst) |
|
567 |
back |
|
568 |
back |
|
569 |
back |
|
570 |
apply assumption |
|
571 |
||
572 |
(* reduce trace_takes from n to strictly smaller k *) |
|
573 |
apply (rule take_reduction) |
|
574 |
||
575 |
(* f A (tw iA) = tw ~eA *) |
|
576 |
apply (simp add: FilterPTakewhileQid int_is_act not_ext_is_int_or_not_act) |
|
577 |
apply (rule refl) |
|
578 |
apply (simp add: int_is_act not_ext_is_int_or_not_act) |
|
579 |
apply (rotate_tac -11) |
|
580 |
||
581 |
(* now conclusion fulfills induction hypothesis, but assumptions are not ready *) |
|
582 |
||
583 |
(* assumption Forall tr *) |
|
584 |
(* assumption schB *) |
|
585 |
apply (simp add: Forall_Conc ext_and_act) |
|
586 |
(* assumption schA *) |
|
587 |
apply (drule_tac x = "schA" and g = "Filter (%a. a:act A) $rs" in subst_lemma2) |
|
588 |
apply assumption |
|
589 |
apply (simp add: int_is_not_ext) |
|
590 |
(* assumptions concerning LastActExtsch, cannot be rewritten, as LastActExtsmalli are looping *) |
|
591 |
apply (drule_tac sch = "schA" and P = "%a. a:int A" in LastActExtsmall1) |
|
592 |
apply (frule_tac ?sch1.0 = "y1" in LastActExtsmall2) |
|
593 |
apply assumption |
|
594 |
||
595 |
(* assumption Forall schA *) |
|
596 |
apply (drule_tac s = "schA" and P = "Forall (%x. x:act A) " in subst) |
|
597 |
apply assumption |
|
598 |
apply (simp add: ForallPTakewhileQ int_is_act) |
|
599 |
||
600 |
(* case x:actions(asig_of A) & x: actions(asig_of B) *) |
|
601 |
||
602 |
||
603 |
apply (rotate_tac -2) |
|
604 |
apply simp |
|
605 |
||
606 |
apply (subgoal_tac "Filter (%a. a:act A & a:ext B) $y1=nil") |
|
607 |
apply (rotate_tac -1) |
|
608 |
apply simp |
|
609 |
(* eliminate introduced subgoal 2 *) |
|
610 |
apply (erule_tac [2] ForallQFilterPnil) |
|
611 |
prefer 2 apply (assumption) |
|
612 |
prefer 2 apply (fast) |
|
613 |
||
614 |
(* bring in divide Seq for s *) |
|
615 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
616 |
apply (erule conjE)+ |
|
617 |
||
618 |
(* subst divide_Seq in conclusion, but only at the righest occurence *) |
|
619 |
apply (rule_tac t = "schA" in ssubst) |
|
620 |
back |
|
621 |
back |
|
622 |
back |
|
623 |
apply assumption |
|
624 |
||
625 |
(* f A (tw iA) = tw ~eA *) |
|
626 |
apply (simp add: FilterPTakewhileQid int_is_act not_ext_is_int_or_not_act) |
|
627 |
||
628 |
(* rewrite assumption forall and schB *) |
|
629 |
apply (rotate_tac 13) |
|
630 |
apply (simp add: ext_and_act) |
|
631 |
||
632 |
(* divide_Seq for schB2 *) |
|
633 |
apply (frule_tac y = "y2" in sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
634 |
apply (erule conjE)+ |
|
635 |
(* assumption schA *) |
|
636 |
apply (drule_tac x = "schA" and g = "Filter (%a. a:act A) $rs" in subst_lemma2) |
|
637 |
apply assumption |
|
638 |
apply (simp add: int_is_not_ext) |
|
639 |
||
640 |
(* f A (tw iB schB2) = nil *) |
|
641 |
apply (simp add: int_is_not_ext not_ext_is_int_or_not_act intA_is_not_actB) |
|
642 |
||
643 |
||
644 |
(* reduce trace_takes from n to strictly smaller k *) |
|
645 |
apply (rule take_reduction) |
|
646 |
apply (rule refl) |
|
647 |
apply (rule refl) |
|
648 |
||
649 |
(* now conclusion fulfills induction hypothesis, but assumptions are not all ready *) |
|
650 |
||
651 |
(* assumption schB *) |
|
652 |
apply (drule_tac x = "y2" and g = "Filter (%a. a:act B) $rs" in subst_lemma2) |
|
653 |
apply assumption |
|
654 |
apply (simp add: intA_is_not_actB int_is_not_ext) |
|
655 |
||
656 |
(* conclusions concerning LastActExtsch, cannot be rewritten, as LastActExtsmalli are looping *) |
|
657 |
apply (drule_tac sch = "schA" and P = "%a. a:int A" in LastActExtsmall1) |
|
658 |
apply (frule_tac ?sch1.0 = "y1" in LastActExtsmall2) |
|
659 |
apply assumption |
|
660 |
apply (drule_tac sch = "y2" and P = "%a. a:int B" in LastActExtsmall1) |
|
661 |
||
662 |
(* assumption Forall schA, and Forall schA are performed by ForallTL,ForallDropwhile *) |
|
663 |
apply (simp add: ForallTL ForallDropwhile) |
|
664 |
||
665 |
(* case x~:A & x:B *) |
|
666 |
(* cannot occur, as just this case has been scheduled out before as the B-only prefix *) |
|
667 |
apply (case_tac "x:act B") |
|
668 |
apply fast |
|
669 |
||
670 |
(* case x~:A & x~:B *) |
|
671 |
(* cannot occur because of assumption: Forall (a:ext A | a:ext B) *) |
|
672 |
apply (rotate_tac -9) |
|
673 |
(* reduce forall assumption from tr to (x>>rs) *) |
|
674 |
apply (simp add: externals_of_par) |
|
675 |
apply (fast intro!: ext_is_act) |
|
676 |
||
677 |
done |
|
678 |
||
679 |
||
680 |
||
681 |
subsection" Filter of mksch(tr,schA,schB) to B is schB -- take lemma proof" |
|
682 |
||
683 |
lemma FilterBmksch_is_schB: "!! A B. [| compatible A B; compatible B A; |
|
684 |
is_asig(asig_of A); is_asig(asig_of B) |] ==> |
|
685 |
Forall (%x. x:ext (A||B)) tr & |
|
686 |
Forall (%x. x:act A) schA & Forall (%x. x:act B) schB & |
|
687 |
Filter (%a. a:ext A)$schA = Filter (%a. a:act A)$tr & |
|
688 |
Filter (%a. a:ext B)$schB = Filter (%a. a:act B)$tr & |
|
689 |
LastActExtsch A schA & LastActExtsch B schB |
|
690 |
--> Filter (%a. a:act B)$(mksch A B$tr$schA$schB) = schB" |
|
691 |
apply (intro strip) |
|
692 |
apply (rule seq.take_lemmas) |
|
693 |
apply (rule mp) |
|
694 |
prefer 2 apply assumption |
|
695 |
back back back back |
|
696 |
apply (rule_tac x = "schA" in spec) |
|
697 |
apply (rule_tac x = "schB" in spec) |
|
698 |
apply (rule_tac x = "tr" in spec) |
|
699 |
apply (tactic "thin_tac' 5 1") |
|
700 |
apply (rule nat_less_induct) |
|
701 |
apply (rule allI)+ |
|
702 |
apply (rename_tac tr schB schA) |
|
703 |
apply (intro strip) |
|
704 |
apply (erule conjE)+ |
|
705 |
||
706 |
apply (case_tac "Forall (%x. x:act A & x~:act B) tr") |
|
707 |
||
708 |
apply (rule seq_take_lemma [THEN iffD2, THEN spec]) |
|
709 |
apply (tactic "thin_tac' 5 1") |
|
710 |
||
711 |
apply (case_tac "Finite tr") |
|
712 |
||
713 |
(* both sides of this equation are nil *) |
|
714 |
apply (subgoal_tac "schB=nil") |
|
715 |
apply (simp (no_asm_simp)) |
|
716 |
(* first side: mksch = nil *) |
|
717 |
apply (auto intro!: ForallQFilterPnil ForallAnBmksch FiniteL_mksch)[1] |
|
718 |
(* second side: schA = nil *) |
|
719 |
apply (erule_tac A = "B" in LastActExtimplnil) |
|
720 |
apply (simp (no_asm_simp)) |
|
721 |
apply (erule_tac Q = "%x. x:act A & x~:act B" in ForallQFilterPnil) |
|
722 |
apply assumption |
|
723 |
apply fast |
|
724 |
||
725 |
(* case ~ Finite tr *) |
|
726 |
||
727 |
(* both sides of this equation are UU *) |
|
728 |
apply (subgoal_tac "schB=UU") |
|
729 |
apply (simp (no_asm_simp)) |
|
730 |
(* first side: mksch = UU *) |
|
731 |
apply (force intro!: ForallQFilterPUU finiteR_mksch [THEN mp, COMP rev_contrapos] ForallAnBmksch) |
|
732 |
(* schA = UU *) |
|
733 |
apply (erule_tac A = "B" in LastActExtimplUU) |
|
734 |
apply (simp (no_asm_simp)) |
|
735 |
apply (erule_tac Q = "%x. x:act A & x~:act B" in ForallQFilterPUU) |
|
736 |
apply assumption |
|
737 |
apply fast |
|
738 |
||
739 |
(* case" ~ Forall (%x.x:act B & x~:act A) s" *) |
|
740 |
||
741 |
apply (drule divide_Seq3) |
|
742 |
||
743 |
apply (erule exE)+ |
|
744 |
apply (erule conjE)+ |
|
745 |
apply hypsubst |
|
746 |
||
747 |
(* bring in lemma reduceB_mksch *) |
|
748 |
apply (frule_tac y = "schB" and x = "schA" and A = "A" and B = "B" in reduceB_mksch) |
|
749 |
apply assumption+ |
|
750 |
apply (erule exE)+ |
|
751 |
apply (erule conjE)+ |
|
752 |
||
753 |
(* use reduceB_mksch to rewrite conclusion *) |
|
754 |
apply hypsubst |
|
755 |
apply simp |
|
756 |
||
757 |
(* eliminate the A-only prefix *) |
|
758 |
||
759 |
apply (subgoal_tac "(Filter (%a. a :act B) $x1) = nil") |
|
760 |
apply (erule_tac [2] ForallQFilterPnil) |
|
761 |
prefer 2 apply (assumption) |
|
762 |
prefer 2 apply (fast) |
|
763 |
||
764 |
(* Now real recursive step follows (in x) *) |
|
765 |
||
766 |
apply simp |
|
767 |
apply (case_tac "x:act B") |
|
768 |
apply (case_tac "x~:act A") |
|
769 |
apply (rotate_tac -2) |
|
770 |
apply simp |
|
771 |
||
772 |
apply (subgoal_tac "Filter (%a. a:act B & a:ext A) $x1=nil") |
|
773 |
apply (rotate_tac -1) |
|
774 |
apply simp |
|
775 |
(* eliminate introduced subgoal 2 *) |
|
776 |
apply (erule_tac [2] ForallQFilterPnil) |
|
777 |
prefer 2 apply (assumption) |
|
778 |
prefer 2 apply (fast) |
|
779 |
||
780 |
(* bring in divide Seq for s *) |
|
781 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
782 |
apply (erule conjE)+ |
|
783 |
||
784 |
(* subst divide_Seq in conclusion, but only at the righest occurence *) |
|
785 |
apply (rule_tac t = "schB" in ssubst) |
|
786 |
back |
|
787 |
back |
|
788 |
back |
|
789 |
apply assumption |
|
790 |
||
791 |
(* reduce trace_takes from n to strictly smaller k *) |
|
792 |
apply (rule take_reduction) |
|
793 |
||
794 |
(* f B (tw iB) = tw ~eB *) |
|
795 |
apply (simp add: FilterPTakewhileQid int_is_act not_ext_is_int_or_not_act) |
|
796 |
apply (rule refl) |
|
797 |
apply (simp add: int_is_act not_ext_is_int_or_not_act) |
|
798 |
apply (rotate_tac -11) |
|
799 |
||
800 |
(* now conclusion fulfills induction hypothesis, but assumptions are not ready *) |
|
801 |
||
802 |
(* assumption schA *) |
|
803 |
apply (simp add: Forall_Conc ext_and_act) |
|
804 |
(* assumption schB *) |
|
805 |
apply (drule_tac x = "schB" and g = "Filter (%a. a:act B) $rs" in subst_lemma2) |
|
806 |
apply assumption |
|
807 |
apply (simp add: int_is_not_ext) |
|
808 |
(* assumptions concerning LastActExtsch, cannot be rewritten, as LastActExtsmalli are looping *) |
|
809 |
apply (drule_tac sch = "schB" and P = "%a. a:int B" in LastActExtsmall1) |
|
810 |
apply (frule_tac ?sch1.0 = "x1" in LastActExtsmall2) |
|
811 |
apply assumption |
|
812 |
||
813 |
(* assumption Forall schB *) |
|
814 |
apply (drule_tac s = "schB" and P = "Forall (%x. x:act B) " in subst) |
|
815 |
apply assumption |
|
816 |
apply (simp add: ForallPTakewhileQ int_is_act) |
|
817 |
||
818 |
(* case x:actions(asig_of A) & x: actions(asig_of B) *) |
|
819 |
||
820 |
apply (rotate_tac -2) |
|
821 |
apply simp |
|
822 |
||
823 |
apply (subgoal_tac "Filter (%a. a:act B & a:ext A) $x1=nil") |
|
824 |
apply (rotate_tac -1) |
|
825 |
apply simp |
|
826 |
(* eliminate introduced subgoal 2 *) |
|
827 |
apply (erule_tac [2] ForallQFilterPnil) |
|
828 |
prefer 2 apply (assumption) |
|
829 |
prefer 2 apply (fast) |
|
830 |
||
831 |
(* bring in divide Seq for s *) |
|
832 |
apply (frule sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
833 |
apply (erule conjE)+ |
|
834 |
||
835 |
(* subst divide_Seq in conclusion, but only at the righest occurence *) |
|
836 |
apply (rule_tac t = "schB" in ssubst) |
|
837 |
back |
|
838 |
back |
|
839 |
back |
|
840 |
apply assumption |
|
841 |
||
842 |
(* f B (tw iB) = tw ~eB *) |
|
843 |
apply (simp add: FilterPTakewhileQid int_is_act not_ext_is_int_or_not_act) |
|
844 |
||
845 |
(* rewrite assumption forall and schB *) |
|
846 |
apply (rotate_tac 13) |
|
847 |
apply (simp add: ext_and_act) |
|
848 |
||
849 |
(* divide_Seq for schB2 *) |
|
850 |
apply (frule_tac y = "x2" in sym [THEN antisym_less_inverse, THEN conjunct1, THEN divide_Seq]) |
|
851 |
apply (erule conjE)+ |
|
852 |
(* assumption schA *) |
|
853 |
apply (drule_tac x = "schB" and g = "Filter (%a. a:act B) $rs" in subst_lemma2) |
|
854 |
apply assumption |
|
855 |
apply (simp add: int_is_not_ext) |
|
856 |
||
857 |
(* f B (tw iA schA2) = nil *) |
|
858 |
apply (simp add: int_is_not_ext not_ext_is_int_or_not_act intA_is_not_actB) |
|
859 |
||
860 |
||
861 |
(* reduce trace_takes from n to strictly smaller k *) |
|
862 |
apply (rule take_reduction) |
|
863 |
apply (rule refl) |
|
864 |
apply (rule refl) |
|
865 |
||
866 |
(* now conclusion fulfills induction hypothesis, but assumptions are not all ready *) |
|
867 |
||
868 |
(* assumption schA *) |
|
869 |
apply (drule_tac x = "x2" and g = "Filter (%a. a:act A) $rs" in subst_lemma2) |
|
870 |
apply assumption |
|
871 |
apply (simp add: intA_is_not_actB int_is_not_ext) |
|
872 |
||
873 |
(* conclusions concerning LastActExtsch, cannot be rewritten, as LastActExtsmalli are looping *) |
|
874 |
apply (drule_tac sch = "schB" and P = "%a. a:int B" in LastActExtsmall1) |
|
875 |
apply (frule_tac ?sch1.0 = "x1" in LastActExtsmall2) |
|
876 |
apply assumption |
|
877 |
apply (drule_tac sch = "x2" and P = "%a. a:int A" in LastActExtsmall1) |
|
878 |
||
879 |
(* assumption Forall schA, and Forall schA are performed by ForallTL,ForallDropwhile *) |
|
880 |
apply (simp add: ForallTL ForallDropwhile) |
|
881 |
||
882 |
(* case x~:B & x:A *) |
|
883 |
(* cannot occur, as just this case has been scheduled out before as the B-only prefix *) |
|
884 |
apply (case_tac "x:act A") |
|
885 |
apply fast |
|
886 |
||
887 |
(* case x~:B & x~:A *) |
|
888 |
(* cannot occur because of assumption: Forall (a:ext A | a:ext B) *) |
|
889 |
apply (rotate_tac -9) |
|
890 |
(* reduce forall assumption from tr to (x>>rs) *) |
|
891 |
apply (simp add: externals_of_par) |
|
892 |
apply (fast intro!: ext_is_act) |
|
893 |
||
894 |
done |
|
895 |
||
896 |
||
897 |
subsection "COMPOSITIONALITY on TRACE Level -- Main Theorem" |
|
898 |
||
899 |
lemma compositionality_tr: |
|
900 |
"!! A B. [| is_trans_of A; is_trans_of B; compatible A B; compatible B A; |
|
901 |
is_asig(asig_of A); is_asig(asig_of B)|] |
|
902 |
==> (tr: traces(A||B)) = |
|
903 |
(Filter (%a. a:act A)$tr : traces A & |
|
904 |
Filter (%a. a:act B)$tr : traces B & |
|
905 |
Forall (%x. x:ext(A||B)) tr)" |
|
906 |
||
907 |
apply (simp (no_asm) add: traces_def has_trace_def) |
|
26359 | 908 |
apply auto |
19741 | 909 |
|
910 |
(* ==> *) |
|
911 |
(* There is a schedule of A *) |
|
912 |
apply (rule_tac x = "Filter (%a. a:act A) $sch" in bexI) |
|
913 |
prefer 2 |
|
914 |
apply (simp add: compositionality_sch) |
|
915 |
apply (simp add: compatibility_consequence1 externals_of_par ext1_ext2_is_not_act1) |
|
916 |
(* There is a schedule of B *) |
|
917 |
apply (rule_tac x = "Filter (%a. a:act B) $sch" in bexI) |
|
918 |
prefer 2 |
|
919 |
apply (simp add: compositionality_sch) |
|
920 |
apply (simp add: compatibility_consequence2 externals_of_par ext1_ext2_is_not_act2) |
|
921 |
(* Traces of A||B have only external actions from A or B *) |
|
922 |
apply (rule ForallPFilterP) |
|
923 |
||
924 |
(* <== *) |
|
925 |
||
926 |
(* replace schA and schB by Cut(schA) and Cut(schB) *) |
|
927 |
apply (drule exists_LastActExtsch) |
|
928 |
apply assumption |
|
929 |
apply (drule exists_LastActExtsch) |
|
930 |
apply assumption |
|
931 |
apply (erule exE)+ |
|
932 |
apply (erule conjE)+ |
|
933 |
(* Schedules of A(B) have only actions of A(B) *) |
|
934 |
apply (drule scheds_in_sig) |
|
935 |
apply assumption |
|
936 |
apply (drule scheds_in_sig) |
|
937 |
apply assumption |
|
938 |
||
939 |
apply (rename_tac h1 h2 schA schB) |
|
940 |
(* mksch is exactly the construction of trA||B out of schA, schB, and the oracle tr, |
|
941 |
we need here *) |
|
942 |
apply (rule_tac x = "mksch A B$tr$schA$schB" in bexI) |
|
943 |
||
944 |
(* External actions of mksch are just the oracle *) |
|
945 |
apply (simp add: FilterA_mksch_is_tr) |
|
946 |
||
947 |
(* mksch is a schedule -- use compositionality on sch-level *) |
|
948 |
apply (simp add: compositionality_sch) |
|
949 |
apply (simp add: FilterAmksch_is_schA FilterBmksch_is_schB) |
|
950 |
apply (erule ForallAorB_mksch) |
|
951 |
apply (erule ForallPForallQ) |
|
952 |
apply (erule ext_is_act) |
|
953 |
done |
|
954 |
||
955 |
||
956 |
||
957 |
subsection {* COMPOSITIONALITY on TRACE Level -- for Modules *} |
|
958 |
||
959 |
lemma compositionality_tr_modules: |
|
960 |
||
961 |
"!! A B. [| is_trans_of A; is_trans_of B; compatible A B; compatible B A; |
|
962 |
is_asig(asig_of A); is_asig(asig_of B)|] |
|
963 |
==> Traces (A||B) = par_traces (Traces A) (Traces B)" |
|
964 |
||
965 |
apply (unfold Traces_def par_traces_def) |
|
966 |
apply (simp add: asig_of_par) |
|
967 |
apply (rule set_ext) |
|
968 |
apply (simp add: compositionality_tr externals_of_par) |
|
969 |
done |
|
970 |
||
971 |
||
26339 | 972 |
declaration {* fn _ => Simplifier.map_ss (fn ss => ss setmksym (SOME o symmetric_fun)) *} |
3071 | 973 |
|
974 |
||
975 |
end |