src/HOL/Lex/AutoChopper.ML
changeset 1894 c2c8279d40f0
parent 1673 d22110ddd0af
child 1950 97f1c6bf3ace
equal deleted inserted replaced
1893:fa58f4a06f21 1894:c2c8279d40f0
    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";