matita/matita/contribs/lambdadelta/basic_2/rt_computation/lprs_cprs.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/rt_computation/cprs_cprs.ma".
  16 include "basic_2/rt_computation/lprs_cpms.ma".
  17
  18 (* PARALLEL R-COMPUTATION FOR FULL LOCAL ENVIRONMENTS ***********************)
  19
  20 (* Advanced properties ******************************************************)
  21
  22 (* Basic_2A1: was: lprs_pair2 *)
  23 lemma lprs_pair_dx (h) (G): ∀L1,L2. ❪G,L1❫ ⊢ ➡*[h,0] L2 →
  24                             ∀V1,V2. ❪G,L2❫ ⊢ V1 ➡*[h,0] V2 →
  25                             ∀I. ❪G,L1.ⓑ[I]V1❫ ⊢ ➡*[h,0] L2.ⓑ[I]V2.
  26 /3 width=3 by lprs_pair, lprs_cpms_trans/ qed.
  27
  28 (* Properties on context-sensitive parallel r-computation for terms *********)
  29
  30 lemma lprs_cprs_conf_dx (h) (G): ∀L0.∀T0,T1:term. ❪G,L0❫ ⊢ T0 ➡*[h,0] T1 →
  31                                  ∀L1. ❪G,L0❫ ⊢ ➡*[h,0] L1 →
  32                                  ∃∃T. ❪G,L1❫ ⊢ T1 ➡*[h,0] T & ❪G,L1❫ ⊢ T0 ➡*[h,0] T.
  33 #h #G #L0 #T0 #T1 #HT01 #L1 #H
  34 @(lprs_ind_dx … H) -L1 /2 width=3 by ex2_intro/
  35 #L #L1 #_ #HL1 * #T #HT1 #HT0 -L0
  36 elim (cprs_lpr_conf_dx … HT1 … HL1) -HT1 #T2 #HT2
  37 elim (cprs_lpr_conf_dx … HT0 … HL1) -L #T3 #HT3
  38 elim (cprs_conf … HT2 … HT3) -T
  39 /3 width=5 by cprs_trans, ex2_intro/
  40 qed-.
  41
  42 lemma lprs_cpr_conf_dx (h) (G): ∀L0. ∀T0,T1:term. ❪G,L0❫ ⊢ T0 ➡[h,0] T1 →
  43                                 ∀L1. ❪G,L0❫ ⊢ ➡*[h,0] L1 →
  44                                 ∃∃T. ❪G,L1❫ ⊢ T1 ➡*[h,0] T & ❪G,L1❫ ⊢ T0 ➡*[h,0] T.
  45 /3 width=3 by lprs_cprs_conf_dx, cpm_cpms/ qed-.
  46
  47 (* Note: this can be proved on its own using lprs_ind_sn *)
  48 lemma lprs_cprs_conf_sn (h) (G): ∀L0. ∀T0,T1:term. ❪G,L0❫ ⊢ T0 ➡*[h,0] T1 →
  49                                  ∀L1. ❪G,L0❫ ⊢ ➡*[h,0] L1 →
  50                                  ∃∃T. ❪G,L0❫ ⊢ T1 ➡*[h,0] T & ❪G,L1❫ ⊢ T0 ➡*[h,0] T.
  51 #h #G #L0 #T0 #T1 #HT01 #L1 #HL01
  52 elim (lprs_cprs_conf_dx … HT01 … HL01) -HT01
  53 /3 width=3 by lprs_cpms_trans, ex2_intro/
  54 qed-.
  55
  56 lemma lprs_cpr_conf_sn (h) (G): ∀L0. ∀T0,T1:term. ❪G,L0❫ ⊢ T0 ➡[h,0] T1 →
  57                                 ∀L1. ❪G,L0❫ ⊢ ➡*[h,0] L1 →
  58                                 ∃∃T. ❪G,L0❫ ⊢ T1 ➡*[h,0] T & ❪G,L1❫ ⊢ T0 ➡*[h,0] T.
  59 /3 width=3 by lprs_cprs_conf_sn, cpm_cpms/ qed-.