26 by (list.induct_tac "xs" 1); |
26 by (list.induct_tac "xs" 1); |
27 by (simp_tac (!simpset addcongs [conj_cong]) 1); |
27 by (simp_tac (!simpset addcongs [conj_cong]) 1); |
28 by (simp_tac (!simpset setloop (split_tac[expand_if])) 1); |
28 by (simp_tac (!simpset setloop (split_tac[expand_if])) 1); |
29 by (strip_tac 1); |
29 by (strip_tac 1); |
30 by (rtac conjI 1); |
30 by (rtac conjI 1); |
31 by (fast_tac HOL_cs 1); |
31 by (Fast_tac 1); |
32 by(simp_tac (!simpset addsimps [prefix_Cons] addcongs [conj_cong]) 1); |
32 by(simp_tac (!simpset addsimps [prefix_Cons] addcongs [conj_cong]) 1); |
33 by (strip_tac 1); |
33 by (strip_tac 1); |
34 by(REPEAT(eresolve_tac [conjE,exE] 1)); |
34 by(REPEAT(eresolve_tac [conjE,exE] 1)); |
35 by(hyp_subst_tac 1); |
35 by(hyp_subst_tac 1); |
36 by (Simp_tac 1); |
36 by (Simp_tac 1); |
37 by (case_tac "zsa = []" 1); |
37 by (case_tac "zsa = []" 1); |
38 by (Asm_simp_tac 1); |
38 by (Asm_simp_tac 1); |
39 by (fast_tac HOL_cs 1); |
39 by (Fast_tac 1); |
40 bind_thm("no_acc", result() RS spec RS spec RS mp); |
40 bind_thm("no_acc", result() RS spec RS spec RS mp); |
41 |
41 |
42 |
42 |
43 val [prem] = goal HOL.thy "? x.P(f(x)) ==> ? y.P(y)"; |
43 val [prem] = goal HOL.thy "? x.P(f(x)) ==> ? y.P(y)"; |
44 by (cut_facts_tac [prem] 1); |
44 by (cut_facts_tac [prem] 1); |
45 by (fast_tac HOL_cs 1); |
45 by (Fast_tac 1); |
46 val ex_special = result(); |
46 val ex_special = result(); |
47 |
47 |
48 |
48 |
49 goal AutoChopper.thy |
49 goal AutoChopper.thy |
50 "! r erk l rst st ys yss zs::'a list. \ |
50 "! r erk l rst st ys yss zs::'a list. \ |
57 by(rename_tac "vss lrst" 1); |
57 by(rename_tac "vss lrst" 1); |
58 by (asm_simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
58 by (asm_simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
59 by (res_inst_tac[("xs","vss")] list_eq_cases 1); |
59 by (res_inst_tac[("xs","vss")] list_eq_cases 1); |
60 by(hyp_subst_tac 1); |
60 by(hyp_subst_tac 1); |
61 by(Simp_tac 1); |
61 by(Simp_tac 1); |
62 by (fast_tac (HOL_cs addSDs [no_acc]) 1); |
62 by (fast_tac (!claset addSDs [no_acc]) 1); |
63 by(hyp_subst_tac 1); |
63 by(hyp_subst_tac 1); |
64 by (asm_simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
64 by (asm_simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
65 val step2_a = (result() repeat_RS spec) RS mp; |
65 val step2_a = (result() repeat_RS spec) RS mp; |
66 |
66 |
67 |
67 |
72 \ then ys ~= [] \ |
72 \ then ys ~= [] \ |
73 \ else ys ~= [] | (erk=[] & (l,rest) = (ys#yss,zs)))"; |
73 \ else ys ~= [] | (erk=[] & (l,rest) = (ys#yss,zs)))"; |
74 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
74 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
75 by (list.induct_tac "xs" 1); |
75 by (list.induct_tac "xs" 1); |
76 by (simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
76 by (simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
77 by (fast_tac HOL_cs 1); |
77 by (Fast_tac 1); |
78 by (asm_simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
78 by (asm_simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
79 by(res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
79 by(res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
80 by(rename_tac "vss lrst" 1); |
80 by(rename_tac "vss lrst" 1); |
81 by(Asm_simp_tac 1); |
81 by(Asm_simp_tac 1); |
82 by (strip_tac 1); |
82 by (strip_tac 1); |
83 by (case_tac "acc_prefix A (next A st a) list" 1); |
83 by (case_tac "acc_prefix A (next A st a) list" 1); |
84 by(Asm_simp_tac 1); |
84 by(Asm_simp_tac 1); |
85 by (subgoal_tac "r @ [a] ~= []" 1); |
85 by (subgoal_tac "r @ [a] ~= []" 1); |
86 by (fast_tac HOL_cs 1); |
86 by (Fast_tac 1); |
87 by (Simp_tac 1); |
87 by (Simp_tac 1); |
88 val step2_b = (result() repeat_RS spec) RS mp; |
88 val step2_b = (result() repeat_RS spec) RS mp; |
89 |
89 |
90 |
90 |
91 goal AutoChopper.thy |
91 goal AutoChopper.thy |
95 \ then ? g. ys=r@g & fin A (nexts A st g) \ |
95 \ then ? g. ys=r@g & fin A (nexts A st g) \ |
96 \ else (erk~=[] & erk=ys) | (erk=[] & (l,rest) = (ys#yss,zs)))"; |
96 \ else (erk~=[] & erk=ys) | (erk=[] & (l,rest) = (ys#yss,zs)))"; |
97 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
97 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
98 by (list.induct_tac "xs" 1); |
98 by (list.induct_tac "xs" 1); |
99 by (simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
99 by (simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
100 by (fast_tac HOL_cs 1); |
100 by (Fast_tac 1); |
101 by (asm_simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
101 by (asm_simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
102 by (strip_tac 1); |
102 by (strip_tac 1); |
103 by (rtac conjI 1); |
103 by (rtac conjI 1); |
104 by(res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
104 by(res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
105 by(rename_tac "vss lrst" 1); |
105 by(rename_tac "vss lrst" 1); |
108 by (strip_tac 1); |
108 by (strip_tac 1); |
109 by (res_inst_tac [("f","%k.a#k")] ex_special 1); |
109 by (res_inst_tac [("f","%k.a#k")] ex_special 1); |
110 by (Simp_tac 1); |
110 by (Simp_tac 1); |
111 by (res_inst_tac [("t","%k.ys=r@a#k"),("s","%k.ys=(r@[a])@k")] subst 1); |
111 by (res_inst_tac [("t","%k.ys=r@a#k"),("s","%k.ys=(r@[a])@k")] subst 1); |
112 by (Simp_tac 1); |
112 by (Simp_tac 1); |
113 by (fast_tac HOL_cs 1); |
113 by (Fast_tac 1); |
114 by (strip_tac 1); |
114 by (strip_tac 1); |
115 by (res_inst_tac [("x","[a]")] exI 1); |
115 by (res_inst_tac [("x","[a]")] exI 1); |
116 by (Asm_simp_tac 1); |
116 by (Asm_simp_tac 1); |
117 by (subgoal_tac "r @ [a] ~= []" 1); |
117 by (subgoal_tac "r @ [a] ~= []" 1); |
118 br sym 1; |
118 br sym 1; |
119 by (fast_tac HOL_cs 1); |
119 by (Fast_tac 1); |
120 by (Simp_tac 1); |
120 by (Simp_tac 1); |
121 by (strip_tac 1); |
121 by (strip_tac 1); |
122 by (res_inst_tac [("f","%k.a#k")] ex_special 1); |
122 by (res_inst_tac [("f","%k.a#k")] ex_special 1); |
123 by (Simp_tac 1); |
123 by (Simp_tac 1); |
124 by (res_inst_tac [("t","%k.ys=r@a#k"),("s","%k.ys=(r@[a])@k")] subst 1); |
124 by (res_inst_tac [("t","%k.ys=r@a#k"),("s","%k.ys=(r@[a])@k")] subst 1); |
125 by (Simp_tac 1); |
125 by (Simp_tac 1); |
126 by (fast_tac HOL_cs 1); |
126 by (Fast_tac 1); |
127 val step2_c = (result() repeat_RS spec) RS mp; |
127 val step2_c = (result() repeat_RS spec) RS mp; |
128 |
128 |
129 |
129 |
130 goal AutoChopper.thy |
130 goal AutoChopper.thy |
131 "! st erk r l rest ys yss zs. \ |
131 "! st erk r l rest ys yss zs. \ |
134 \ then acc(flat(yss)@zs)(start A) [] [] ([],flat(yss)@zs) A = (yss,zs) \ |
134 \ then acc(flat(yss)@zs)(start A) [] [] ([],flat(yss)@zs) A = (yss,zs) \ |
135 \ else (erk~=[] & (l,rest)=(yss,zs)) | (erk=[] & (l, rest)=(ys#yss,zs)))"; |
135 \ else (erk~=[] & (l,rest)=(yss,zs)) | (erk=[] & (l, rest)=(ys#yss,zs)))"; |
136 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
136 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
137 by (list.induct_tac "xs" 1); |
137 by (list.induct_tac "xs" 1); |
138 by (simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
138 by (simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
139 by (fast_tac HOL_cs 1); |
139 by (Fast_tac 1); |
140 by (asm_simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
140 by (asm_simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
141 by(res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
141 by(res_inst_tac [("p","acc list (start A) [] [] ([],list) A")] PairE 1); |
142 by(rename_tac "vss lrst" 1); |
142 by(rename_tac "vss lrst" 1); |
143 by(Asm_simp_tac 1); |
143 by(Asm_simp_tac 1); |
144 by (strip_tac 1); |
144 by (strip_tac 1); |
145 by (case_tac "acc_prefix A (next A st a) list" 1); |
145 by (case_tac "acc_prefix A (next A st a) list" 1); |
146 by (Asm_simp_tac 1); |
146 by (Asm_simp_tac 1); |
147 by (subgoal_tac "acc list (start A) [] [] ([],list) A = (yss,zs)" 1); |
147 by (subgoal_tac "acc list (start A) [] [] ([],list) A = (yss,zs)" 1); |
148 by (Asm_simp_tac 2); |
148 by (Asm_simp_tac 2); |
149 by (subgoal_tac "r@[a] ~= []" 2); |
149 by (subgoal_tac "r@[a] ~= []" 2); |
150 by (fast_tac HOL_cs 2); |
150 by (Fast_tac 2); |
151 by (Simp_tac 2); |
151 by (Simp_tac 2); |
152 by (subgoal_tac "flat(yss) @ zs = list" 1); |
152 by (subgoal_tac "flat(yss) @ zs = list" 1); |
153 by(hyp_subst_tac 1); |
153 by(hyp_subst_tac 1); |
154 by(atac 1); |
154 by(atac 1); |
155 by (case_tac "yss = []" 1); |
155 by (case_tac "yss = []" 1); |
156 by (Asm_simp_tac 1); |
156 by (Asm_simp_tac 1); |
157 by (hyp_subst_tac 1); |
157 by (hyp_subst_tac 1); |
158 by (fast_tac (HOL_cs addSDs [no_acc]) 1); |
158 by (fast_tac (!claset addSDs [no_acc]) 1); |
159 by (etac ((neq_Nil_conv RS iffD1) RS exE) 1); |
159 by (etac ((neq_Nil_conv RS iffD1) RS exE) 1); |
160 by (etac exE 1); |
160 by (etac exE 1); |
161 by (hyp_subst_tac 1); |
161 by (hyp_subst_tac 1); |
162 by (Simp_tac 1); |
162 by (Simp_tac 1); |
163 by (rtac trans 1); |
163 by (rtac trans 1); |
173 \ then ? g.ys=r@g & (!as. as<=xs & g<=as & g~=as --> ~fin A (nexts A st as))\ |
173 \ then ? g.ys=r@g & (!as. as<=xs & g<=as & g~=as --> ~fin A (nexts A st as))\ |
174 \ else (erk~=[] & ys=erk) | (erk=[] & (ys#yss,zs)=p))"; |
174 \ else (erk~=[] & ys=erk) | (erk=[] & (ys#yss,zs)=p))"; |
175 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
175 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
176 by (list.induct_tac "xs" 1); |
176 by (list.induct_tac "xs" 1); |
177 by (simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
177 by (simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
178 by (fast_tac HOL_cs 1); |
178 by (Fast_tac 1); |
179 by (asm_simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
179 by (asm_simp_tac (!simpset addcongs [conj_cong] setloop (split_tac [expand_if])) 1); |
180 by (strip_tac 1); |
180 by (strip_tac 1); |
181 by (case_tac "acc_prefix A (next A st a) list" 1); |
181 by (case_tac "acc_prefix A (next A st a) list" 1); |
182 br conjI 1; |
182 br conjI 1; |
183 by (strip_tac 1); |
183 by (strip_tac 1); |
205 by (Asm_simp_tac 1); |
205 by (Asm_simp_tac 1); |
206 by (strip_tac 1); |
206 by (strip_tac 1); |
207 by (res_inst_tac [("x","[a]")] exI 1); |
207 by (res_inst_tac [("x","[a]")] exI 1); |
208 by (rtac conjI 1); |
208 by (rtac conjI 1); |
209 by (subgoal_tac "r @ [a] ~= []" 1); |
209 by (subgoal_tac "r @ [a] ~= []" 1); |
210 by (fast_tac HOL_cs 1); |
210 by (Fast_tac 1); |
211 by (Simp_tac 1); |
211 by (Simp_tac 1); |
212 by (rtac list_cases 1); |
212 by (rtac list_cases 1); |
213 by (Simp_tac 1); |
213 by (Simp_tac 1); |
214 by (asm_full_simp_tac (!simpset addsimps [acc_prefix_def] addcongs[conj_cong]) 1); |
214 by (asm_full_simp_tac (!simpset addsimps [acc_prefix_def] addcongs[conj_cong]) 1); |
215 by (etac thin_rl 1); (* speed up *) |
215 by (etac thin_rl 1); (* speed up *) |
216 by (fast_tac HOL_cs 1); |
216 by (Fast_tac 1); |
217 val step2_e = (result() repeat_RS spec) RS mp; |
217 val step2_e = (result() repeat_RS spec) RS mp; |
218 Addsimps[split_paired_All]; |
218 Addsimps[split_paired_All]; |
219 |
219 |
220 goalw AutoChopper.thy [accepts_def, is_auto_chopper_def, auto_chopper_def, |
220 goalw AutoChopper.thy [accepts_def, is_auto_chopper_def, auto_chopper_def, |
221 Chopper.is_longest_prefix_chopper_def] |
221 Chopper.is_longest_prefix_chopper_def] |
226 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
226 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
227 by (rtac conjI 1); |
227 by (rtac conjI 1); |
228 br mp 1; |
228 br mp 1; |
229 be step2_c 2; |
229 be step2_c 2; |
230 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
230 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
231 by (fast_tac HOL_cs 1); |
231 by (Fast_tac 1); |
232 by (rtac conjI 1); |
232 by (rtac conjI 1); |
233 by (asm_simp_tac (!simpset addsimps [step2_a] setloop (split_tac [expand_if])) 1); |
233 by (asm_simp_tac (!simpset addsimps [step2_a] setloop (split_tac [expand_if])) 1); |
234 by (rtac conjI 1); |
234 by (rtac conjI 1); |
235 br mp 1; |
235 br mp 1; |
236 be step2_d 2; |
236 be step2_d 2; |
237 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
237 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
238 by (rtac mp 1); |
238 by (rtac mp 1); |
239 be step2_e 2; |
239 be step2_e 2; |
240 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
240 by (simp_tac (!simpset setloop (split_tac [expand_if])) 1); |
241 by (fast_tac HOL_cs 1); |
241 by (Fast_tac 1); |
242 qed"auto_chopper_is_auto_chopper"; |
242 qed"auto_chopper_is_auto_chopper"; |