src/HOL/IOA/IOA.ML
changeset 17288 aa3833fb7bee
parent 12886 75ca1bf5ae12
equal deleted inserted replaced
17287:bd49e10bbd24 17288:aa3833fb7bee
     1 (*  Title:      HOL/IOA/IOA.ML
     1 (*  Title:      HOL/IOA/IOA.ML
     2     ID:         $Id$
     2     ID:         $Id$
     3     Author:     Tobias Nipkow & Konrad Slind
     3     Author:     Tobias Nipkow & Konrad Slind
     4     Copyright   1994  TU Muenchen
     4     Copyright   1994  TU Muenchen
     5 
       
     6 The I/O automata of Lynch and Tuttle.
       
     7 *)
     5 *)
     8 
     6 
     9 Addsimps [Let_def];
     7 Addsimps [Let_def];
    10 
     8 
    11 val ioa_projections = [asig_of_def, starts_of_def, trans_of_def];
     9 bind_thms ("ioa_projections", [asig_of_def, starts_of_def, trans_of_def]);
    12 
    10 
    13 val exec_rws = [executions_def,is_execution_fragment_def];
    11 bind_thms ("exec_rws", [executions_def,is_execution_fragment_def]);
    14 
    12 
    15 Goal
    13 Goal
    16 "asig_of(x,y,z) = x & starts_of(x,y,z) = y & trans_of(x,y,z) = z";
    14 "asig_of(x,y,z) = x & starts_of(x,y,z) = y & trans_of(x,y,z) = z";
    17   by (simp_tac (simpset() addsimps ioa_projections) 1);
    15   by (simp_tac (simpset() addsimps ioa_projections) 1);
    18   qed "ioa_triple_proj";
    16   qed "ioa_triple_proj";
    65   by (rtac allI 1);
    63   by (rtac allI 1);
    66   by (cut_inst_tac [("m","na"),("n","n")] less_linear 1);
    64   by (cut_inst_tac [("m","na"),("n","n")] less_linear 1);
    67   by Auto_tac;
    65   by Auto_tac;
    68 qed "reachable_n";
    66 qed "reachable_n";
    69 
    67 
    70 val [p1,p2] = goalw IOA.thy [invariant_def]
    68 val [p1,p2] = goalw (the_context ()) [invariant_def]
    71   "[| !!s. s:starts_of(A) ==> P(s);                                          \
    69   "[| !!s. s:starts_of(A) ==> P(s);                                          \
    72 \     !!s t a. [|reachable A s; P(s)|] ==> (s,a,t): trans_of(A) --> P(t) |] \
    70 \     !!s t a. [|reachable A s; P(s)|] ==> (s,a,t): trans_of(A) --> P(t) |] \
    73 \  ==> invariant A P";
    71 \  ==> invariant A P";
    74   by (rewrite_goals_tac(reachable_def::Let_def::exec_rws));
    72   by (rewrite_goals_tac(reachable_def::Let_def::exec_rws));
    75   by Safe_tac;
    73   by Safe_tac;
    83   by Safe_tac;
    81   by Safe_tac;
    84    by (etac (p2 RS mp) 1);
    82    by (etac (p2 RS mp) 1);
    85     by (ALLGOALS(fast_tac(claset() addDs [reachable_n])));
    83     by (ALLGOALS(fast_tac(claset() addDs [reachable_n])));
    86 qed "invariantI";
    84 qed "invariantI";
    87 
    85 
    88 val [p1,p2] = goal IOA.thy
    86 val [p1,p2] = goal (the_context ())
    89  "[| !!s. s : starts_of(A) ==> P(s); \
    87  "[| !!s. s : starts_of(A) ==> P(s); \
    90 \    !!s t a. reachable A s ==> P(s) --> (s,a,t):trans_of(A) --> P(t) \
    88 \    !!s t a. reachable A s ==> P(s) --> (s,a,t):trans_of(A) --> P(t) \
    91 \ |] ==> invariant A P";
    89 \ |] ==> invariant A P";
    92   by (fast_tac (claset() addSIs [invariantI] addSDs [p1,p2]) 1);
    90   by (fast_tac (claset() addSIs [invariantI] addSDs [p1,p2]) 1);
    93 qed "invariantI1";
    91 qed "invariantI1";
    94 
    92 
    95 val [p1,p2] = goalw IOA.thy [invariant_def]
    93 val [p1,p2] = goalw (the_context ()) [invariant_def]
    96 "[| invariant A P; reachable A s |] ==> P(s)";
    94 "[| invariant A P; reachable A s |] ==> P(s)";
    97    by (rtac (p2 RS (p1 RS spec RS mp)) 1);
    95    by (rtac (p2 RS (p1 RS spec RS mp)) 1);
    98 qed "invariantE";
    96 qed "invariantE";
    99 
    97 
   100 Goal 
    98 Goal
   101 "actions(asig_comp a b) = actions(a) Un actions(b)";
    99 "actions(asig_comp a b) = actions(a) Un actions(b)";
   102   by (simp_tac (simpset() addsimps
   100   by (simp_tac (simpset() addsimps
   103                ([actions_def,asig_comp_def]@asig_projections)) 1);
   101                ([actions_def,asig_comp_def]@asig_projections)) 1);
   104   by (Fast_tac 1);
   102   by (Fast_tac 1);
   105 qed "actions_asig_comp";
   103 qed "actions_asig_comp";
   108 "starts_of(A || B) = {p. fst(p):starts_of(A) & snd(p):starts_of(B)}";
   106 "starts_of(A || B) = {p. fst(p):starts_of(A) & snd(p):starts_of(B)}";
   109   by (simp_tac (simpset() addsimps (par_def::ioa_projections)) 1);
   107   by (simp_tac (simpset() addsimps (par_def::ioa_projections)) 1);
   110 qed "starts_of_par";
   108 qed "starts_of_par";
   111 
   109 
   112 (* Every state in an execution is reachable *)
   110 (* Every state in an execution is reachable *)
   113 Goalw [reachable_def] 
   111 Goalw [reachable_def]
   114 "ex:executions(A) ==> !n. reachable A (snd ex n)";
   112 "ex:executions(A) ==> !n. reachable A (snd ex n)";
   115   by (Fast_tac 1);
   113   by (Fast_tac 1);
   116 qed "states_of_exec_reachable";
   114 qed "states_of_exec_reachable";
   117 
   115 
   118 
   116 
   119 Goal 
   117 Goal
   120 "(s,a,t) : trans_of(A || B || C || D) =                                      \
   118 "(s,a,t) : trans_of(A || B || C || D) =                                      \
   121 \ ((a:actions(asig_of(A)) | a:actions(asig_of(B)) | a:actions(asig_of(C)) |  \
   119 \ ((a:actions(asig_of(A)) | a:actions(asig_of(B)) | a:actions(asig_of(C)) |  \
   122 \   a:actions(asig_of(D))) &                                                 \
   120 \   a:actions(asig_of(D))) &                                                 \
   123 \  (if a:actions(asig_of(A)) then (fst(s),a,fst(t)):trans_of(A)              \
   121 \  (if a:actions(asig_of(A)) then (fst(s),a,fst(t)):trans_of(A)              \
   124 \   else fst t=fst s) &                                                      \
   122 \   else fst t=fst s) &                                                      \
   148 
   146 
   149 
   147 
   150 Goal "externals(asig_of(A1||A2)) =    \
   148 Goal "externals(asig_of(A1||A2)) =    \
   151 \  (externals(asig_of(A1)) Un externals(asig_of(A2)))";
   149 \  (externals(asig_of(A1)) Un externals(asig_of(A2)))";
   152 by (asm_full_simp_tac (simpset() addsimps [externals_def,asig_of_par,asig_comp_def,asig_inputs_def,asig_outputs_def,Un_def,set_diff_def]) 1);
   150 by (asm_full_simp_tac (simpset() addsimps [externals_def,asig_of_par,asig_comp_def,asig_inputs_def,asig_outputs_def,Un_def,set_diff_def]) 1);
   153 by (rtac set_ext 1); 
   151 by (rtac set_ext 1);
   154 by (Fast_tac 1);
   152 by (Fast_tac 1);
   155 qed"externals_of_par"; 
   153 qed"externals_of_par";
   156 
   154 
   157 Goalw [externals_def,actions_def,compat_ioas_def,compat_asigs_def]
   155 Goalw [externals_def,actions_def,compat_ioas_def,compat_asigs_def]
   158  "[| compat_ioas A1 A2; a:externals(asig_of(A1))|] ==> a~:internals(asig_of(A2))";
   156  "[| compat_ioas A1 A2; a:externals(asig_of(A1))|] ==> a~:internals(asig_of(A2))";
   159 by (Asm_full_simp_tac 1);
   157 by (Asm_full_simp_tac 1);
   160 by (Best_tac 1);
   158 by (Best_tac 1);
   166 by (Best_tac 1);
   164 by (Best_tac 1);
   167 qed"ext2_is_not_int1";
   165 qed"ext2_is_not_int1";
   168 
   166 
   169 val ext1_ext2_is_not_act2 = ext1_is_not_int2 RS int_and_ext_is_act;
   167 val ext1_ext2_is_not_act2 = ext1_is_not_int2 RS int_and_ext_is_act;
   170 val ext1_ext2_is_not_act1 = ext2_is_not_int1 RS int_and_ext_is_act;
   168 val ext1_ext2_is_not_act1 = ext2_is_not_int1 RS int_and_ext_is_act;
   171