16 Addsimps [Let_def]; |
16 Addsimps [Let_def]; |
17 |
17 |
18 goal AutoChopper.thy "!st us p y ys. acc xs st (ys@[y]) us p A ~= ([],zs)"; |
18 goal AutoChopper.thy "!st us p y ys. acc xs st (ys@[y]) us p A ~= ([],zs)"; |
19 by (list.induct_tac "xs" 1); |
19 by (list.induct_tac "xs" 1); |
20 by (Simp_tac 1); |
20 by (Simp_tac 1); |
21 by (asm_simp_tac (simpset() addsplits [expand_if]) 1); |
21 by (Asm_simp_tac 1); |
22 val accept_not_Nil = result() repeat_RS spec; |
22 val accept_not_Nil = result() repeat_RS spec; |
23 Addsimps [accept_not_Nil]; |
23 Addsimps [accept_not_Nil]; |
24 |
24 |
25 goal AutoChopper.thy |
25 goal AutoChopper.thy |
26 "!st us. acc xs st [] us ([],ys) A = ([], zs) --> \ |
26 "!st us. acc xs st [] us ([],ys) A = ([], zs) --> \ |
27 \ zs = ys & (!ys. ys ~= [] & ys<=xs --> ~fin A (nexts A st ys))"; |
27 \ zs = ys & (!ys. ys ~= [] & ys<=xs --> ~fin A (nexts A st ys))"; |
28 by (list.induct_tac "xs" 1); |
28 by (list.induct_tac "xs" 1); |
29 by (simp_tac (simpset() addcongs [conj_cong]) 1); |
29 by (simp_tac (simpset() addcongs [conj_cong]) 1); |
30 by (simp_tac (simpset() addsplits [expand_if]) 1); |
30 by (Simp_tac 1); |
31 by (strip_tac 1); |
31 by (strip_tac 1); |
32 by (rtac conjI 1); |
32 by (rtac conjI 1); |
33 by (Fast_tac 1); |
33 by (Fast_tac 1); |
34 by (simp_tac (simpset() addsimps [prefix_Cons] addcongs [conj_cong]) 1); |
34 by (simp_tac (simpset() addsimps [prefix_Cons] addcongs [conj_cong]) 1); |
35 by (strip_tac 1); |
35 by (strip_tac 1); |
51 goal AutoChopper.thy |
51 goal AutoChopper.thy |
52 "! r erk l rst st ys yss zs::'a list. \ |
52 "! r erk l rst st ys yss zs::'a list. \ |
53 \ acc xs st erk r (l,rst) A = (ys#yss, zs) --> \ |
53 \ acc xs st erk r (l,rst) A = (ys#yss, zs) --> \ |
54 \ ys@concat(yss)@zs = (if acc_prefix A st xs then r@xs else erk@concat(l)@rst)"; |
54 \ ys@concat(yss)@zs = (if acc_prefix A st xs then r@xs else erk@concat(l)@rst)"; |
55 by (list.induct_tac "xs" 1); |
55 by (list.induct_tac "xs" 1); |
56 by (simp_tac (simpset() addcongs [conj_cong] addsplits [expand_if]) 1); |
56 by (simp_tac (simpset() addcongs [conj_cong]) 1); |
57 by (asm_simp_tac (simpset() addsplits [expand_if]) 1); |
57 by (Asm_simp_tac 1); |
58 by (res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
58 by (res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
59 by (rename_tac "vss lrst" 1); |
59 by (rename_tac "vss lrst" 1); |
60 by (asm_simp_tac (simpset() addsplits [expand_if]) 1); |
60 by (Asm_simp_tac 1); |
61 by (res_inst_tac[("xs","vss")] list_eq_cases 1); |
61 by (res_inst_tac[("xs","vss")] list_eq_cases 1); |
62 by (hyp_subst_tac 1); |
62 by (hyp_subst_tac 1); |
63 by (Simp_tac 1); |
63 by (Simp_tac 1); |
64 by (fast_tac (claset() addSDs [no_acc]) 1); |
64 by (fast_tac (claset() addSDs [no_acc]) 1); |
65 by (hyp_subst_tac 1); |
65 by (hyp_subst_tac 1); |
66 by (asm_simp_tac (simpset() addsplits [expand_if]) 1); |
66 by (Asm_simp_tac 1); |
67 val step2_a = (result() repeat_RS spec) RS mp; |
67 val step2_a = (result() repeat_RS spec) RS mp; |
68 |
68 |
69 |
69 |
70 goal AutoChopper.thy |
70 goal AutoChopper.thy |
71 "! st erk r l rest ys yss zs.\ |
71 "! st erk r l rest ys yss zs.\ |
72 \ acc xs st erk r (l,rest) A = (ys#yss, zs) --> \ |
72 \ acc xs st erk r (l,rest) A = (ys#yss, zs) --> \ |
73 \ (if acc_prefix A st xs \ |
73 \ (if acc_prefix A st xs \ |
74 \ then ys ~= [] \ |
74 \ then ys ~= [] \ |
75 \ else ys ~= [] | (erk=[] & (l,rest) = (ys#yss,zs)))"; |
75 \ else ys ~= [] | (erk=[] & (l,rest) = (ys#yss,zs)))"; |
76 by (simp_tac (simpset() addsplits [expand_if]) 1); |
76 by (Simp_tac 1); |
77 by (list.induct_tac "xs" 1); |
77 by (list.induct_tac "xs" 1); |
78 by (simp_tac (simpset() addcongs [conj_cong] addsplits [expand_if]) 1); |
78 by (simp_tac (simpset() addcongs [conj_cong]) 1); |
79 by (Fast_tac 1); |
79 by (Fast_tac 1); |
80 by (asm_simp_tac (simpset() addcongs [conj_cong] addsplits [expand_if]) 1); |
80 by (asm_simp_tac (simpset() addcongs [conj_cong]) 1); |
81 by (res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
81 by (res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
82 by (rename_tac "vss lrst" 1); |
82 by (rename_tac "vss lrst" 1); |
83 by (Asm_simp_tac 1); |
83 by (Asm_simp_tac 1); |
84 by (strip_tac 1); |
84 by (strip_tac 1); |
85 by (case_tac "acc_prefix A (next A st a) list" 1); |
85 by (case_tac "acc_prefix A (next A st a) list" 1); |
94 "! st erk r l rest ys yss zs. \ |
94 "! st erk r l rest ys yss zs. \ |
95 \ acc xs st erk r (l,rest) A = (ys#yss, zs) --> \ |
95 \ acc xs st erk r (l,rest) A = (ys#yss, zs) --> \ |
96 \ (if acc_prefix A st xs \ |
96 \ (if acc_prefix A st xs \ |
97 \ then ? g. ys=r@g & fin A (nexts A st g) \ |
97 \ then ? g. ys=r@g & fin A (nexts A st g) \ |
98 \ else (erk~=[] & erk=ys) | (erk=[] & (l,rest) = (ys#yss,zs)))"; |
98 \ else (erk~=[] & erk=ys) | (erk=[] & (l,rest) = (ys#yss,zs)))"; |
99 by (simp_tac (simpset() addsplits [expand_if]) 1); |
99 by (Simp_tac 1); |
100 by (list.induct_tac "xs" 1); |
100 by (list.induct_tac "xs" 1); |
101 by (simp_tac (simpset() addcongs [conj_cong] addsplits [expand_if]) 1); |
101 by (simp_tac (simpset() addcongs [conj_cong]) 1); |
102 by (Fast_tac 1); |
102 by (Fast_tac 1); |
103 by (asm_simp_tac (simpset() addcongs [conj_cong] addsplits [expand_if]) 1); |
103 by (asm_simp_tac (simpset() addcongs [conj_cong]) 1); |
104 by (strip_tac 1); |
104 by (strip_tac 1); |
105 by (rtac conjI 1); |
105 by (rtac conjI 1); |
106 by (res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
106 by (res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
107 by (rename_tac "vss lrst" 1); |
107 by (rename_tac "vss lrst" 1); |
108 by (Asm_simp_tac 1); |
108 by (Asm_simp_tac 1); |
133 "! st erk r l rest ys yss zs. \ |
133 "! st erk r l rest ys yss zs. \ |
134 \ acc xs st erk r (l,rest) A = (ys#yss, zs) --> \ |
134 \ acc xs st erk r (l,rest) A = (ys#yss, zs) --> \ |
135 \ (if acc_prefix A st xs \ |
135 \ (if acc_prefix A st xs \ |
136 \ then acc(concat(yss)@zs)(start A) [] [] ([],concat(yss)@zs) A = (yss,zs) \ |
136 \ then acc(concat(yss)@zs)(start A) [] [] ([],concat(yss)@zs) A = (yss,zs) \ |
137 \ else (erk~=[] & (l,rest)=(yss,zs)) | (erk=[] & (l, rest)=(ys#yss,zs)))"; |
137 \ else (erk~=[] & (l,rest)=(yss,zs)) | (erk=[] & (l, rest)=(ys#yss,zs)))"; |
138 by (simp_tac (simpset() addsplits [expand_if]) 1); |
138 by (Simp_tac 1); |
139 by (list.induct_tac "xs" 1); |
139 by (list.induct_tac "xs" 1); |
140 by (simp_tac (simpset() addcongs [conj_cong] addsplits [expand_if]) 1); |
140 by (simp_tac (simpset() addcongs [conj_cong]) 1); |
141 by (Fast_tac 1); |
141 by (Fast_tac 1); |
142 by (asm_simp_tac (simpset() addcongs [conj_cong] addsplits [expand_if]) 1); |
142 by (asm_simp_tac (simpset() addcongs [conj_cong]) 1); |
143 by (res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
143 by (res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
144 by (rename_tac "vss lrst" 1); |
144 by (rename_tac "vss lrst" 1); |
145 by (Asm_simp_tac 1); |
145 by (Asm_simp_tac 1); |
146 by (strip_tac 1); |
146 by (strip_tac 1); |
147 by (case_tac "acc_prefix A (next A st a) list" 1); |
147 by (case_tac "acc_prefix A (next A st a) list" 1); |
162 by (etac exE 1); |
162 by (etac exE 1); |
163 by (hyp_subst_tac 1); |
163 by (hyp_subst_tac 1); |
164 by (Simp_tac 1); |
164 by (Simp_tac 1); |
165 by (rtac trans 1); |
165 by (rtac trans 1); |
166 by (etac step2_a 1); |
166 by (etac step2_a 1); |
167 by (simp_tac (simpset() addsplits [expand_if]) 1); |
167 by (Simp_tac 1); |
168 val step2_d = (result() repeat_RS spec) RS mp; |
168 val step2_d = (result() repeat_RS spec) RS mp; |
169 |
169 |
170 Delsimps [split_paired_All]; |
170 Delsimps [split_paired_All]; |
171 goal AutoChopper.thy |
171 goal AutoChopper.thy |
172 "! st erk r p ys yss zs. \ |
172 "! st erk r p ys yss zs. \ |
173 \ acc xs st erk r p A = (ys#yss, zs) --> \ |
173 \ acc xs st erk r p A = (ys#yss, zs) --> \ |
174 \ (if acc_prefix A st xs \ |
174 \ (if acc_prefix A st xs \ |
175 \ then ? g. ys=r@g & (!as. as<=xs & g<=as & g~=as --> ~fin A (nexts A st as))\ |
175 \ then ? g. ys=r@g & (!as. as<=xs & g<=as & g~=as --> ~fin A (nexts A st as))\ |
176 \ else (erk~=[] & ys=erk) | (erk=[] & (ys#yss,zs)=p))"; |
176 \ else (erk~=[] & ys=erk) | (erk=[] & (ys#yss,zs)=p))"; |
177 by (simp_tac (simpset() addsplits [expand_if]) 1); |
177 by (Simp_tac 1); |
178 by (list.induct_tac "xs" 1); |
178 by (list.induct_tac "xs" 1); |
179 by (simp_tac (simpset() addcongs [conj_cong] addsplits [expand_if]) 1); |
179 by (simp_tac (simpset() addcongs [conj_cong]) 1); |
180 by (Fast_tac 1); |
180 by (Fast_tac 1); |
181 by (asm_simp_tac (simpset() addcongs [conj_cong] addsplits [expand_if]) 1); |
181 by (asm_simp_tac (simpset() addcongs [conj_cong]) 1); |
182 by (strip_tac 1); |
182 by (strip_tac 1); |
183 by (case_tac "acc_prefix A (next A st a) list" 1); |
183 by (case_tac "acc_prefix A (next A st a) list" 1); |
184 by (rtac conjI 1); |
184 by (rtac conjI 1); |
185 by (strip_tac 1); |
185 by (strip_tac 1); |
186 by (res_inst_tac [("f","%k. a#k")] ex_special 1); |
186 by (res_inst_tac [("f","%k. a#k")] ex_special 1); |
223 Chopper.is_longest_prefix_chopper_def] |
223 Chopper.is_longest_prefix_chopper_def] |
224 "is_auto_chopper(auto_chopper)"; |
224 "is_auto_chopper(auto_chopper)"; |
225 by (REPEAT(ares_tac [no_acc,allI,impI,conjI] 1)); |
225 by (REPEAT(ares_tac [no_acc,allI,impI,conjI] 1)); |
226 by (rtac mp 1); |
226 by (rtac mp 1); |
227 by (etac step2_b 2); |
227 by (etac step2_b 2); |
228 by (simp_tac (simpset() addsplits [expand_if]) 1); |
228 by (Simp_tac 1); |
229 by (rtac conjI 1); |
229 by (rtac conjI 1); |
230 by (rtac mp 1); |
230 by (rtac mp 1); |
231 by (etac step2_c 2); |
231 by (etac step2_c 2); |
232 by (simp_tac (simpset() addsplits [expand_if]) 1); |
232 by (Simp_tac 1); |
233 by (rtac conjI 1); |
233 by (rtac conjI 1); |
234 by (asm_simp_tac (simpset() addsimps [step2_a] addsplits [expand_if]) 1); |
234 by (asm_simp_tac (simpset() addsimps [step2_a]) 1); |
235 by (rtac conjI 1); |
235 by (rtac conjI 1); |
236 by (rtac mp 1); |
236 by (rtac mp 1); |
237 by (etac step2_d 2); |
237 by (etac step2_d 2); |
238 by (simp_tac (simpset() addsplits [expand_if]) 1); |
238 by (Simp_tac 1); |
239 by (rtac mp 1); |
239 by (rtac mp 1); |
240 by (etac step2_e 2); |
240 by (etac step2_e 2); |
241 by (simp_tac (simpset() addsplits [expand_if]) 1); |
241 by (Simp_tac 1); |
242 qed"auto_chopper_is_auto_chopper"; |
242 qed"auto_chopper_is_auto_chopper"; |