]> matita.cs.unibo.it Git - helm.git/blob - matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr_cpr.ma
- context-sensitive computation: more properties
[helm.git] / matita / matita / contribs / lambda_delta / basic_2 / reducibility / cpr_cpr.ma
1 (**************************************************************************)
2 (*       ___                                                              *)
3 (*      ||M||                                                             *)
4 (*      ||A||       A project by Andrea Asperti                           *)
5 (*      ||T||                                                             *)
6 (*      ||I||       Developers:                                           *)
7 (*      ||T||         The HELM team.                                      *)
8 (*      ||A||         http://helm.cs.unibo.it                             *)
9 (*      \   /                                                             *)
10 (*       \ /        This file is distributed under the terms of the       *)
11 (*        v         GNU General Public License Version 2                  *)
12 (*                                                                        *)
13 (**************************************************************************)
14
15 include "basic_2/reducibility/tpr_tpr.ma".
16 include "basic_2/reducibility/cpr.ma".
17
18 (* CONTEXT-SENSITIVE PARALLEL REDUCTION ON TERMS ****************************)
19
20 (* Advanced properties ******************************************************)
21
22 lemma cpr_bind_sn: ∀I,L,V1,V2,T1,T2. L ⊢ V1 ➡ V2 → T1 ➡ T2 →
23                    L ⊢ ⓑ{I} V1. T1 ➡ ⓑ{I} V2. T2.
24 #I #L #V1 #V2 #T1 #T2 * #V #HV1 #HV2 #HT12
25 @ex2_1_intro [2: @(tpr_delta … HV1 HT12) | skip ] /2 width=3/ (* /3 width=5/ is too slow *)
26 qed.
27
28 (* Basic_1: was only: pr2_gen_cbind *)
29 lemma cpr_bind_dx: ∀I,L,V1,V2,T1,T2. V1 ➡ V2 → L. ⓑ{I} V2 ⊢ T1 ➡ T2 →
30                    L ⊢ ⓑ{I} V1. T1 ➡ ⓑ{I} V2. T2.
31 #I #L #V1 #V2 #T1 #T2 #HV12 * #T #HT1 normalize #HT2
32 elim (tpss_split_up … HT2 1 ? ?) -HT2 // #T0 <minus_n_O #HT0 normalize <minus_plus_m_m #HT02
33 lapply (tpss_lsubs_conf … HT0 (⋆. ⓑ{I} V2) ?) -HT0 /2 width=1/ #HT0
34 lapply (tpss_tps … HT0) -HT0 #HT0
35 @ex2_1_intro [2: @(tpr_delta … HV12 HT1 HT0) | skip | /2 width=1/ ] (**) (* /3 width=5/ is too slow *)
36 qed.
37
38 (* Basic_1: was only: pr2_head_1 *) 
39 lemma cpr_pair_sn: ∀I,L,V1,V2,T1,T2. L ⊢ V1 ➡ V2 → T1 ➡ T2 →
40                    L ⊢ ②{I} V1. T1 ➡ ②{I} V2. T2.
41 * /2 width=1/ /3 width=1/
42 qed.
43
44 (* Advanced forward lemmas **************************************************)
45
46 lemma cpr_shift_fwd: ∀L,T1,T2. L ⊢ T1 ➡ T2 → L @ T1 ➡ L @ T2.
47 #L elim L -L
48 [ #T1 #T2 #HT12 @(cpr_inv_atom … HT12)
49 | normalize /3 width=1/
50 ].
51 qed-.
52
53 (* Main properties **********************************************************)
54
55 (* Basic_1: was: pr2_confluence *)
56 theorem cpr_conf: ∀L,U0,T1,T2. L ⊢ U0 ➡ T1 → L ⊢ U0 ➡ T2 →
57                   ∃∃T. L ⊢ T1 ➡ T & L ⊢ T2 ➡ T.
58 #L #U0 #T1 #T2 * #U1 #HU01 #HUT1 * #U2 #HU02 #HUT2
59 elim (tpr_conf … HU01 HU02) -U0 #U #HU1 #HU2 
60 elim (tpr_tpss_ltpr ? L … HU1 … HUT1) -U1 // #U1 #HTU1 #HU1
61 elim (tpr_tpss_ltpr ? L … HU2 … HUT2) -U2 // #U2 #HTU2 #HU2
62 elim (tpss_conf_eq … HU1 … HU2) -U /3 width=5/
63 qed.