src/HOL/Lex/AutoChopper.ML
changeset 4686 74a12e86b20b
parent 4089 96fba19bcbe2
child 4832 bc11b5b06f87
equal deleted inserted replaced
4685:9259feeeb2c8 4686:74a12e86b20b
    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";