1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "basic_2/relocation/drops_ceq.ma".
16 include "basic_2/relocation/drops_lexs.ma".
17 include "basic_2/static/frees_drops.ma".
18 include "basic_2/static/lfxs.ma".
20 (* GENERIC EXTENSION ON REFERRED ENTRIES OF A CONTEXT-SENSITIVE REALTION ****)
22 definition dedropable_sn: predicate (relation3 lenv term term) ≝
23 λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≡ K1 →
24 ∀K2,T. K1 ⦻*[R, T] K2 → ∀U. ⬆*[f] T ≡ U →
25 ∃∃L2. L1 ⦻*[R, U] L2 & ⬇*[b, f] L2 ≡ K2 & L1 ≡[f] L2.
27 definition dropable_sn: predicate (relation3 lenv term term) ≝
28 λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≡ K1 → 𝐔⦃f⦄ →
29 ∀L2,U. L1 ⦻*[R, U] L2 → ∀T. ⬆*[f] T ≡ U →
30 ∃∃K2. K1 ⦻*[R, T] K2 & ⬇*[b, f] L2 ≡ K2.
32 definition dropable_dx: predicate (relation3 lenv term term) ≝
33 λR. ∀L1,L2,U. L1 ⦻*[R, U] L2 →
34 ∀b,f,K2. ⬇*[b, f] L2 ≡ K2 → 𝐔⦃f⦄ → ∀T. ⬆*[f] T ≡ U →
35 ∃∃K1. ⬇*[b, f] L1 ≡ K1 & K1 ⦻*[R, T] K2.
37 (* Properties with generic slicing for local environments *******************)
39 (* Basic_2A1: includes: llpx_sn_lift_le llpx_sn_lift_ge *)
40 lemma lfxs_liftable_dedropable: ∀R. (∀L. reflexive ? (R L)) →
41 d_liftable2 R → dedropable_sn R.
42 #R #H1R #H2R #b #f #L1 #K1 #HLK1 #K2 #T * #f1 #Hf1 #HK12 #U #HTU
43 elim (frees_total L1 U) #f2 #Hf2
44 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -HTU #Hf
45 elim (lexs_liftable_co_dedropable … H1R … H2R … HLK1 … HK12 … Hf) -f1 -K1
46 /3 width=6 by cfull_lift, ex3_intro, ex2_intro/
49 (* Inversion lemmas with generic slicing for local environments *************)
51 (* Basic_2A1: restricts: llpx_sn_inv_lift_le llpx_sn_inv_lift_be llpx_sn_inv_lift_ge *)
52 (* Basic_2A1: was: llpx_sn_drop_conf_O *)
53 lemma lfxs_dropable_sn: ∀R. dropable_sn R.
54 #R #b #f #L1 #K1 #HLK1 #H1f #L2 #U * #f2 #Hf2 #HL12 #T #HTU
55 elim (frees_total K1 T) #f1 #Hf1
56 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -HTU #H2f
57 elim (lexs_co_dropable_sn … HLK1 … HL12 … H2f) -f2 -L1
58 /3 width=3 by ex2_intro/
61 (* Basic_2A1: was: llpx_sn_drop_trans_O *)
62 (* Note: the proof might be simplified *)
63 lemma lfxs_dropable_dx: ∀R. dropable_dx R.
64 #R #L1 #L2 #U * #f2 #Hf2 #HL12 #b #f #K2 #HLK2 #H1f #T #HTU
65 elim (drops_isuni_ex … H1f L1) #K1 #HLK1
66 elim (frees_total K1 T) #f1 #Hf1
67 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -K1 #H2f
68 elim (lexs_co_dropable_dx … HL12 … HLK2 … H2f) -L2
69 /4 width=9 by frees_inv_lifts, ex2_intro/
72 (* Basic_2A1: was: llpx_sn_inv_lift_O *)
73 lemma lfxs_inv_lift_bi: ∀R,L1,L2,U. L1 ⦻*[R, U] L2 →
74 ∀K1,K2,i. ⬇*[i] L1 ≡ K1 → ⬇*[i] L2 ≡ K2 →
75 ∀T. ⬆*[i] T ≡ U → K1 ⦻*[R, T] K2.
76 #R #L1 #L2 #U #HL12 #K1 #K2 #i #HLK1 #HLK2 #T #HTU
77 elim (lfxs_dropable_sn … HLK1 … HL12 … HTU) -L1 -U // #Y #HK12 #HY
78 lapply (drops_mono … HY … HLK2) -L2 -i #H destruct //
81 lemma lfxs_inv_lref_sn: ∀R,L1,L2,i. L1 ⦻*[R, #i] L2 → ∀I,K1,V1. ⬇*[i] L1 ≡ K1.ⓑ{I}V1 →
82 ∃∃K2,V2. ⬇*[i] L2 ≡ K2.ⓑ{I}V2 & K1 ⦻*[R, V1] K2 & R K1 V1 V2.
83 #R #L1 #L2 #i #HL12 #I #K1 #V1 #HLK1 elim (lfxs_dropable_sn … HLK1 … HL12 (#0)) -HLK1 -HL12 //
84 #Y #HY #HLK2 elim (lfxs_inv_zero_pair_sn … HY) -HY
85 #K2 #V2 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/
88 lemma lfxs_inv_lref_dx: ∀R,L1,L2,i. L1 ⦻*[R, #i] L2 → ∀I,K2,V2. ⬇*[i] L2 ≡ K2.ⓑ{I}V2 →
89 ∃∃K1,V1. ⬇*[i] L1 ≡ K1.ⓑ{I}V1 & K1 ⦻*[R, V1] K2 & R K1 V1 V2.
90 #R #L1 #L2 #i #HL12 #I #K2 #V2 #HLK2 elim (lfxs_dropable_dx … HL12 … HLK2 … (#0)) -HLK2 -HL12 //
91 #Y #HLK1 #HY elim (lfxs_inv_zero_pair_dx … HY) -HY
92 #K1 #V1 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/