src/HOL/IMP/Def_Init.thy
author paulson <lp15@cam.ac.uk>
Mon May 23 15:33:24 2016 +0100 (2016-05-23)
changeset 63114 27afe7af7379
parent 53015 a1119cf551e8
permissions -rw-r--r--
Lots of new material for multivariate analysis
     1 theory Def_Init
     2 imports Vars Com
     3 begin
     4 
     5 subsection "Definite Initialization Analysis"
     6 
     7 inductive D :: "vname set \<Rightarrow> com \<Rightarrow> vname set \<Rightarrow> bool" where
     8 Skip: "D A SKIP A" |
     9 Assign: "vars a \<subseteq> A \<Longrightarrow> D A (x ::= a) (insert x A)" |
    10 Seq: "\<lbrakk> D A\<^sub>1 c\<^sub>1 A\<^sub>2;  D A\<^sub>2 c\<^sub>2 A\<^sub>3 \<rbrakk> \<Longrightarrow> D A\<^sub>1 (c\<^sub>1;; c\<^sub>2) A\<^sub>3" |
    11 If: "\<lbrakk> vars b \<subseteq> A;  D A c\<^sub>1 A\<^sub>1;  D A c\<^sub>2 A\<^sub>2 \<rbrakk> \<Longrightarrow>
    12   D A (IF b THEN c\<^sub>1 ELSE c\<^sub>2) (A\<^sub>1 Int A\<^sub>2)" |
    13 While: "\<lbrakk> vars b \<subseteq> A;  D A c A' \<rbrakk> \<Longrightarrow> D A (WHILE b DO c) A"
    14 
    15 inductive_cases [elim!]:
    16 "D A SKIP A'"
    17 "D A (x ::= a) A'"
    18 "D A (c1;;c2) A'"
    19 "D A (IF b THEN c1 ELSE c2) A'"
    20 "D A (WHILE b DO c) A'"
    21 
    22 lemma D_incr: 
    23   "D A c A' \<Longrightarrow> A \<subseteq> A'"
    24 by (induct rule: D.induct) auto
    25 
    26 end