989
af02b193a19a
the supp of a lambda can now be characterised, *provided* the notion of free variables coincides with support on lambda terms
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
1 |
theory Abs
|
|
984
|
2 |
imports "Nominal2_Atoms" "Nominal2_Eqvt" "Nominal2_Supp" "../QuotMain"
|
|
|
3 |
begin
|
|
|
4 |
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
5 |
(* lemmas that should be in Nominal \<dots>\<dots>must be cleaned *)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
6 |
lemma in_permute_iff:
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
7 |
shows "(p \<bullet> x) \<in> (p \<bullet> X) \<longleftrightarrow> x \<in> X"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
8 |
apply(unfold mem_def permute_fun_def)[1]
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
9 |
apply(simp add: permute_bool_def)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
10 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
11 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
12 |
lemma fresh_star_permute_iff:
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
13 |
shows "(p \<bullet> a) \<sharp>* (p \<bullet> x) \<longleftrightarrow> a \<sharp>* x"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
14 |
apply(simp add: fresh_star_def)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
15 |
apply(auto)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
16 |
apply(drule_tac x="p \<bullet> xa" in bspec)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
17 |
apply(unfold mem_def permute_fun_def)[1]
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
18 |
apply(simp add: eqvts)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
19 |
apply(simp add: fresh_permute_iff)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
20 |
apply(rule_tac ?p1="- p" in fresh_permute_iff[THEN iffD1])
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
21 |
apply(simp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
22 |
apply(drule_tac x="- p \<bullet> xa" in bspec)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
23 |
apply(rule_tac ?p1="p" in in_permute_iff[THEN iffD1])
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
24 |
apply(simp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
25 |
apply(simp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
26 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
27 |
|
|
984
|
28 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
29 |
datatype 'a rabst =
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
30 |
RAbst "atom set" "'a::pt"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
31 |
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
32 |
fun map_fun
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
33 |
where "map_fun f (RAbst bs x) = RAbst bs (f x)"
|
|
984
|
34 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
35 |
fun map_rel
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
36 |
where "map_rel R (RAbst bs x) (RAbst cs y) = R x y"
|
|
984
|
37 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
38 |
declare [[map "rabst" = (map_fun, map_rel)]]
|
|
984
|
39 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
40 |
instantiation rabst :: (pt) pt
|
|
984
|
41 |
begin
|
|
|
42 |
|
|
|
43 |
primrec
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
44 |
permute_rabst
|
|
984
|
45 |
where
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
46 |
"p \<bullet> (RAbst bs x) = RAbst (p \<bullet> bs) (p \<bullet> x)"
|
|
984
|
47 |
|
|
|
48 |
instance
|
|
|
49 |
apply(default)
|
|
|
50 |
apply(case_tac [!] x)
|
|
|
51 |
apply(simp_all)
|
|
|
52 |
done
|
|
|
53 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
54 |
end
|
|
984
|
55 |
|
988
a987b5acadc8
improved the proof slightly by defining alpha as a function and completely characterised the equality between two abstractions
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
56 |
fun
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
57 |
alpha_gen
|
|
984
|
58 |
where
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
59 |
alpha_gen[simp del]:
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
60 |
"(alpha_gen (bs, x) R f pi (cs, y)) \<longleftrightarrow> (f x - bs = f y - cs) \<and> ((f x - bs) \<sharp>* pi) \<and> (R (pi \<bullet> x) y)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
61 |
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
62 |
notation
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
63 |
alpha_gen ("_ \<approx>gen _ _ _ _")
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
64 |
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
65 |
lemma alpha_gen_refl:
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
66 |
assumes a: "R x x"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
67 |
shows "(bs, x) \<approx>gen R f 0 (bs, x)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
68 |
using a by (simp add: alpha_gen fresh_star_def fresh_zero_perm)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
69 |
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
70 |
lemma alpha_gen_sym:
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
71 |
assumes a: "(bs, x) \<approx>gen R f p (cs, y)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
72 |
and b: "R (p \<bullet> x) y \<Longrightarrow> R (- p \<bullet> y) x"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
73 |
shows "(cs, y) \<approx>gen R f (- p) (bs, x)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
74 |
using a b by (simp add: alpha_gen fresh_star_def fresh_def supp_minus_perm)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
75 |
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
76 |
lemma alpha_gen_trans:
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
77 |
assumes a: "(bs, x) \<approx>gen R f p1 (cs, y)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
78 |
and b: "(cs, y) \<approx>gen R f p2 (ds, z)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
79 |
and c: "\<lbrakk>R (p1 \<bullet> x) y; R (p2 \<bullet> y) z\<rbrakk> \<Longrightarrow> R ((p2 + p1) \<bullet> x) z"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
80 |
shows "(bs, x) \<approx>gen R f (p2 + p1) (ds, z)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
81 |
using a b c using supp_plus_perm
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
82 |
apply(simp add: alpha_gen fresh_star_def fresh_def)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
83 |
apply(blast)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
84 |
done
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
85 |
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
86 |
lemma alpha_gen_eqvt:
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
87 |
assumes a: "(bs, x) \<approx>gen R f q (cs, y)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
88 |
and b: "R (q \<bullet> x) y \<Longrightarrow> R (p \<bullet> (q \<bullet> x)) (p \<bullet> y)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
89 |
and c: "p \<bullet> (f x) = f (p \<bullet> x)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
90 |
and d: "p \<bullet> (f y) = f (p \<bullet> y)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
91 |
shows "(p \<bullet> bs, p \<bullet> x) \<approx>gen R f (p \<bullet> q) (p \<bullet> cs, p \<bullet> y)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
92 |
using a b
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
93 |
apply(simp add: alpha_gen c[symmetric] d[symmetric] Diff_eqvt[symmetric])
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
94 |
apply(simp add: permute_eqvt[symmetric])
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
95 |
apply(simp add: fresh_star_permute_iff)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
96 |
apply(clarsimp)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
97 |
done
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
98 |
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
99 |
fun
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
100 |
alpha_rabst :: "('a::pt) rabst \<Rightarrow> 'a rabst \<Rightarrow> bool" ("_ \<approx>raw _")
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
101 |
where
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
102 |
"(RAbst bs x) \<approx>raw (RAbst cs y) = (\<exists>p. (bs, x) \<approx>gen (op=) supp p (cs, y))"
|
|
984
|
103 |
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
104 |
lemma alpha_reflp:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
105 |
shows "abst \<approx>raw abst"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
106 |
apply(induct abst)
|
988
a987b5acadc8
improved the proof slightly by defining alpha as a function and completely characterised the equality between two abstractions
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
107 |
apply(simp)
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
108 |
apply(rule exI)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
109 |
apply(rule alpha_gen_refl)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
110 |
apply(simp)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
111 |
done
|
|
984
|
112 |
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
113 |
lemma alpha_symp:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
114 |
assumes a: "abst1 \<approx>raw abst2"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
115 |
shows "abst2 \<approx>raw abst1"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
116 |
using a
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
117 |
apply(induct rule: alpha_rabst.induct)
|
988
a987b5acadc8
improved the proof slightly by defining alpha as a function and completely characterised the equality between two abstractions
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
118 |
apply(simp)
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
119 |
apply(erule exE)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
120 |
apply(rule exI)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
121 |
apply(rule alpha_gen_sym)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
122 |
apply(assumption)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
123 |
apply(clarsimp)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
124 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
125 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
126 |
lemma alpha_transp:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
127 |
assumes a1: "abst1 \<approx>raw abst2"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
128 |
and a2: "abst2 \<approx>raw abst3"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
129 |
shows "abst1 \<approx>raw abst3"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
130 |
using a1 a2
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
131 |
apply(induct rule: alpha_rabst.induct)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
132 |
apply(induct rule: alpha_rabst.induct)
|
988
a987b5acadc8
improved the proof slightly by defining alpha as a function and completely characterised the equality between two abstractions
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
133 |
apply(simp)
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
134 |
apply(erule exE)+
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
135 |
apply(rule exI)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
136 |
apply(rule alpha_gen_trans)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
137 |
apply(assumption)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
138 |
apply(assumption)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
139 |
apply(simp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
140 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
141 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
142 |
lemma alpha_eqvt:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
143 |
assumes a: "abst1 \<approx>raw abst2"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
144 |
shows "(p \<bullet> abst1) \<approx>raw(p \<bullet> abst2)"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
145 |
using a
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
146 |
apply(induct abst1 abst2 rule: alpha_rabst.induct)
|
|
984
|
147 |
apply(simp)
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
148 |
apply(erule exE)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
149 |
apply(rule exI)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
150 |
apply(rule alpha_gen_eqvt)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
151 |
apply(assumption)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
152 |
apply(simp)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
153 |
apply(simp add: supp_eqvt)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
154 |
apply(simp add: supp_eqvt)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
155 |
done
|
|
984
|
156 |
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
157 |
lemma test1:
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
158 |
assumes a1: "a \<notin> (supp x) - bs"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
159 |
and a2: "b \<notin> (supp x) - bs"
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
160 |
shows "(RAbst bs x) \<approx>raw (RAbst ((a \<rightleftharpoons> b) \<bullet> bs) ((a \<rightleftharpoons> b) \<bullet> x))"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
161 |
apply(simp)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
162 |
apply(rule_tac x="(a \<rightleftharpoons> b)" in exI)
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
163 |
apply(simp add: alpha_gen)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
164 |
apply(simp add: supp_eqvt[symmetric] Diff_eqvt[symmetric])
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
165 |
apply(simp add: swap_set_fresh[OF a1 a2])
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
166 |
apply(subgoal_tac "supp (a \<rightleftharpoons> b) \<subseteq> {a, b}")
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
167 |
using a1 a2
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
168 |
apply(simp add: fresh_star_def fresh_def)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
169 |
apply(blast)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
170 |
apply(simp add: supp_swap)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
171 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
172 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
173 |
fun
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
174 |
s_test
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
175 |
where
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
176 |
"s_test (RAbst bs x) = (supp x) - bs"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
177 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
178 |
lemma s_test_lemma:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
179 |
assumes a: "x \<approx>raw y"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
180 |
shows "s_test x = s_test y"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
181 |
using a
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
182 |
apply(induct rule: alpha_rabst.induct)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
183 |
apply(simp add: alpha_gen)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
184 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
185 |
|
|
984
|
186 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
187 |
quotient_type 'a abst = "('a::pt) rabst" / "alpha_rabst::('a::pt) rabst \<Rightarrow> 'a rabst \<Rightarrow> bool"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
188 |
apply(rule equivpI)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
189 |
unfolding reflp_def symp_def transp_def
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
190 |
apply(auto intro: alpha_reflp alpha_symp alpha_transp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
191 |
done
|
|
984
|
192 |
|
|
|
193 |
quotient_definition
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
194 |
"Abst::atom set \<Rightarrow> ('a::pt) \<Rightarrow> 'a abst"
|
|
984
|
195 |
as
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
196 |
"RAbst"
|
|
984
|
197 |
|
|
|
198 |
lemma [quot_respect]:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
199 |
shows "((op =) ===> (op =) ===> alpha_rabst) RAbst RAbst"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
200 |
apply(simp del: alpha_rabst.simps add: alpha_reflp)
|
|
984
|
201 |
done
|
|
|
202 |
|
|
|
203 |
lemma [quot_respect]:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
204 |
shows "((op =) ===> alpha_rabst ===> alpha_rabst) permute permute"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
205 |
apply(simp add: alpha_eqvt)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
206 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
207 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
208 |
lemma [quot_respect]:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
209 |
shows "(alpha_rabst ===> (op =)) s_test s_test"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
210 |
apply(simp add: s_test_lemma)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
211 |
done
|
|
984
|
212 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
213 |
lemma abst_induct:
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
214 |
"\<lbrakk>\<And>as (x::'a::pt). P (Abst as x)\<rbrakk> \<Longrightarrow> P t"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
215 |
apply(lifting rabst.induct)
|
|
984
|
216 |
done
|
|
|
217 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
218 |
instantiation abst :: (pt) pt
|
|
984
|
219 |
begin
|
|
|
220 |
|
|
|
221 |
quotient_definition
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
222 |
"permute_abst::perm \<Rightarrow> ('a::pt abst) \<Rightarrow> 'a abst"
|
|
984
|
223 |
as
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
224 |
"permute::perm \<Rightarrow> ('a::pt rabst) \<Rightarrow> 'a rabst"
|
|
984
|
225 |
|
|
|
226 |
lemma permute_ABS [simp]:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
227 |
fixes x::"'a::pt" (* ??? has to be 'a \<dots> 'b does not work *)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
228 |
shows "(p \<bullet> (Abst as x)) = Abst (p \<bullet> as) (p \<bullet> x)"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
229 |
apply(lifting permute_rabst.simps(1))
|
|
984
|
230 |
done
|
|
|
231 |
|
|
|
232 |
instance
|
|
|
233 |
apply(default)
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
234 |
apply(induct_tac [!] x rule: abst_induct)
|
|
984
|
235 |
apply(simp_all)
|
|
|
236 |
done
|
|
|
237 |
|
|
|
238 |
end
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
239 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
240 |
lemma test1_lifted:
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
241 |
assumes a1: "a \<notin> (supp x) - bs"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
242 |
and a2: "b \<notin> (supp x) - bs"
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
243 |
shows "(Abst bs x) = (Abst ((a \<rightleftharpoons> b) \<bullet> bs) ((a \<rightleftharpoons> b) \<bullet> x))"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
244 |
using a1 a2
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
245 |
apply(lifting test1)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
246 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
247 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
248 |
lemma Abst_supports:
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
249 |
shows "((supp x) - as) supports (Abst as x)"
|
|
984
|
250 |
unfolding supports_def
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
251 |
apply(clarify)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
252 |
apply(simp (no_asm))
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
253 |
apply(subst test1_lifted[symmetric])
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
254 |
apply(simp_all)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
255 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
256 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
257 |
quotient_definition
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
258 |
"s_test_lifted :: ('a::pt) abst \<Rightarrow> atom \<Rightarrow> bool"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
259 |
as
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
260 |
"s_test::('a::pt) rabst \<Rightarrow> atom \<Rightarrow> bool"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
261 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
262 |
lemma s_test_lifted_simp:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
263 |
shows "s_test_lifted (Abst bs x) = (supp x) - bs"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
264 |
apply(lifting s_test.simps(1))
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
265 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
266 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
267 |
lemma s_test_lifted_eqvt:
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
268 |
shows "(p \<bullet> (s_test_lifted ab)) = s_test_lifted (p \<bullet> ab)"
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
269 |
apply(induct ab rule: abst_induct)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
270 |
apply(simp add: s_test_lifted_simp supp_eqvt Diff_eqvt)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
271 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
272 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
273 |
lemma fresh_f_empty_supp:
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
274 |
assumes a: "\<forall>p. p \<bullet> f = f"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
275 |
shows "a \<sharp> x \<Longrightarrow> a \<sharp> (f x)"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
276 |
apply(simp add: fresh_def)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
277 |
apply(simp add: supp_def)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
278 |
apply(simp add: permute_fun_app_eq)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
279 |
apply(simp add: a)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
280 |
apply(rule finite_subset)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
281 |
prefer 2
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
282 |
apply(assumption)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
283 |
apply(auto)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
284 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
285 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
286 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
287 |
lemma s_test_fresh_lemma:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
288 |
shows "(a \<sharp> Abst bs x) \<Longrightarrow> (a \<sharp> s_test_lifted (Abst bs x))"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
289 |
apply(rule fresh_f_empty_supp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
290 |
apply(rule allI)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
291 |
apply(subst permute_fun_def)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
292 |
apply(simp add: s_test_lifted_eqvt)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
293 |
apply(simp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
294 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
295 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
296 |
lemma supp_finite_set:
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
297 |
fixes S::"atom set"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
298 |
assumes "finite S"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
299 |
shows "supp S = S"
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
300 |
apply(rule finite_supp_unique)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
301 |
apply(simp add: supports_def)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
302 |
apply(auto simp add: permute_set_eq swap_atom)[1]
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
303 |
apply(metis)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
304 |
apply(rule assms)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
305 |
apply(auto simp add: permute_set_eq swap_atom)[1]
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
306 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
307 |
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
308 |
lemma s_test_subset:
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
309 |
fixes x::"'a::fs"
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
310 |
shows "((supp x) - as) \<subseteq> (supp (Abst as x))"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
311 |
apply(rule subsetI)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
312 |
apply(rule contrapos_pp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
313 |
apply(assumption)
|
|
984
|
314 |
unfolding fresh_def[symmetric]
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
315 |
apply(drule_tac s_test_fresh_lemma)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
316 |
apply(simp only: s_test_lifted_simp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
317 |
apply(simp add: fresh_def)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
318 |
apply(subgoal_tac "finite (supp x - as)")
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
319 |
apply(simp add: supp_finite_set)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
320 |
apply(simp add: finite_supp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
321 |
done
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
322 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
323 |
lemma supp_Abst:
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
324 |
fixes x::"'a::fs"
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
325 |
shows "supp (Abst as x) = (supp x) - as"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
326 |
apply(rule subset_antisym)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
327 |
apply(rule supp_is_subset)
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
328 |
apply(rule Abst_supports)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
329 |
apply(simp add: finite_supp)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
330 |
apply(rule s_test_subset)
|
|
984
|
331 |
done
|
|
|
332 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
333 |
instance abst :: (fs) fs
|
|
984
|
334 |
apply(default)
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
335 |
apply(induct_tac x rule: abst_induct)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
336 |
apply(simp add: supp_Abst)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
337 |
apply(simp add: finite_supp)
|
|
984
|
338 |
done
|
|
|
339 |
|
988
a987b5acadc8
improved the proof slightly by defining alpha as a function and completely characterised the equality between two abstractions
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
340 |
lemma fresh_abs:
|
|
984
|
341 |
fixes x::"'a::fs"
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
342 |
shows "a \<sharp> Abst bs x = (a \<in> bs \<or> (a \<notin> bs \<and> a \<sharp> x))"
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
343 |
apply(simp add: fresh_def)
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
344 |
apply(simp add: supp_Abst)
|
986
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
345 |
apply(auto)
|
98375dde48fc
general abstraction operator and complete characterisation of its support and freshness
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
346 |
done
|
|
984
|
347 |
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
348 |
thm alpha_rabst.simps(1)
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
349 |
|
988
a987b5acadc8
improved the proof slightly by defining alpha as a function and completely characterised the equality between two abstractions
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
350 |
lemma abs_eq:
|
995
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
351 |
shows "(Abst bs x) = (Abst cs y) \<longleftrightarrow> (\<exists>p. (bs, x) \<approx>gen (op =) supp p (cs, y))"
|
ee0619b5adff
introduced a generic alpha (but not sure whether it is helpful)
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
352 |
apply(lifting alpha_rabst.simps(1))
|
|
984
|
353 |
done
|
|
|
354 |
|
989
af02b193a19a
the supp of a lambda can now be characterised, *provided* the notion of free variables coincides with support on lambda terms
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
355 |
end
|
988
a987b5acadc8
improved the proof slightly by defining alpha as a function and completely characterised the equality between two abstractions
Christian Urban <urbanc@in.tum.de>
diff
changeset
|
356 |
|