matita/matita/contribs/lambdadelta/basic_2/dynamic/cnv_cpms_tdeq_conf.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/dynamic/cnv_cpm_tdeq_conf.ma".
  16 include "basic_2/dynamic/cnv_cpms_tdeq.ma".
  17
  18 (* CONTEXT-SENSITIVE NATIVE VALIDITY FOR TERMS ******************************)
  19
  20 (* Sub confluence propery with restricted rt-transition for terms ***********)
  21
  22 fact cnv_cpms_tdeq_strip_lpr_aux (a) (h) (G0) (L0) (T0):
  23      (∀G,L,T. ⦃G0,L0,T0⦄ >[h] ⦃G,L,T⦄ → IH_cnv_cpm_trans_lpr a h G L T) →
  24      (∀G,L,T. ⦃G0,L0,T0⦄ >[h] ⦃G,L,T⦄ → IH_cnv_cpms_conf_lpr a h G L T) →
  25      ∀n1,T1. ⦃G0,L0⦄ ⊢ T0 ➡*[n1,h] T1 → ⦃G0,L0⦄ ⊢ T0 ![a,h] → T0 ≛ T1 →
  26      ∀n2,T2. ⦃G0,L0⦄ ⊢ T0 ➡[n2,h] T2 → T0 ≛ T2 →
  27      ∀L1. ⦃G0,L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G0,L0⦄ ⊢ ➡[h] L2 →
  28      ∃∃T. ⦃G0,L1⦄ ⊢ T1 ➡[n2-n1,h] T & T1 ≛ T & ⦃G0,L2⦄ ⊢ T2 ➡*[n1-n2,h] T & T2 ≛ T.
  29 #a #h #G #L0 #T0 #IH2 #IH1 #n1 #T1 #H1T01 #H0T0 #H2T01
  30 @(cpms_tdeq_ind_sn … H1T01 H0T0 H2T01 IH1 IH2) -n1 -T0
  31 [ #H0T1 #n2 #T2 #H1T12 #H2T12 #L1 #HL01 #L2 #HL02
  32   <minus_O_n <minus_n_O
  33   elim (cnv_cpm_tdeq_conf_lpr … H0T1 0 T1 … H1T12 H2T12 … HL01 … HL02) // -L0 -H2T12
  34   <minus_O_n <minus_n_O #T #H1T1 #H2T1 #H1T2 #H2T2
  35   /3 width=5 by cpm_cpms, ex4_intro/
  36 | #m1 #m2 #T0 #T3 #H1T03 #H0T0 #H2T03 #_ #_ #_ #IH
  37   #n2 #T2 #H1T02 #H2T02 #L1 #HL01 #L2 #HL02
  38   elim (cnv_cpm_tdeq_conf_lpr … H0T0 … H1T03 H2T03 … H1T02 H2T02 … L0 … HL02) -T0 //
  39   #T0 #H1T30 #H2T30 #H1T20 #H2T20
  40   elim (IH … H1T30 H2T30 … HL01 … HL02) -L0 -T3
  41   #T3 #H1T13 #H2T13 #H1T03 #H2T03
  42   <minus_plus >arith_l3
  43   /3 width=7 by cpms_step_sn, tdeq_trans, ex4_intro/
  44 ]
  45 qed-.
  46
  47 fact cnv_cpms_tdeq_conf_lpr_aux (a) (h) (G0) (L0) (T0):
  48      (∀G,L,T. ⦃G0,L0,T0⦄ >[h] ⦃G,L,T⦄ → IH_cnv_cpm_trans_lpr a h G L T) →
  49      (∀G,L,T. ⦃G0,L0,T0⦄ >[h] ⦃G,L,T⦄ → IH_cnv_cpms_conf_lpr a h G L T) →
  50      ∀n1,T1. ⦃G0,L0⦄ ⊢ T0 ➡*[n1,h] T1 → ⦃G0,L0⦄ ⊢ T0 ![a,h] → T0 ≛ T1 →
  51      ∀n2,T2. ⦃G0,L0⦄ ⊢ T0 ➡*[n2,h] T2 → T0 ≛ T2 →
  52      ∀L1. ⦃G0,L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G0,L0⦄ ⊢ ➡[h] L2 →
  53      ∃∃T. ⦃G0,L1⦄ ⊢ T1 ➡*[n2-n1,h] T & T1 ≛ T & ⦃G0,L2⦄ ⊢ T2 ➡*[n1-n2,h] T & T2 ≛ T.
  54 #a #h #G #L0 #T0 #IH2 #IH1 #n1 #T1 #H1T01 #H0T0 #H2T01
  55 generalize in match IH1; generalize in match IH2;
  56 @(cpms_tdeq_ind_sn … H1T01 H0T0 H2T01 IH1 IH2) -n1 -T0
  57 [ #H0T1 #IH2 #IH1 #n2 #T2 #H1T12 #H2T12 #L1 #HL01 #L2 #HL02
  58   <minus_O_n <minus_n_O
  59   elim (cnv_cpms_tdeq_strip_lpr_aux … IH2 IH1 … H1T12 H0T1 H2T12 0 T1 … HL02 … HL01) // -L0 -H2T12
  60   <minus_O_n <minus_n_O #T #H1T2 #H2T2 #H1T1 #H2T1
  61   /3 width=5 by cpm_cpms, ex4_intro/
  62 | #m1 #m2 #T0 #T3 #H1T03 #H0T0 #H2T03 #_ #_ #_ #IH #IH2 #IH1
  63   #n2 #T2 #H1T02 #H2T02 #L1 #HL01 #L2 #HL02
  64   elim (cnv_cpms_tdeq_strip_lpr_aux … IH2 IH1 … H1T02 H0T0 H2T02 … H1T03 H2T03 … HL02 L0) -H0T0 -H2T03 //
  65   #T4 #H1T24 #H2T24 #H1T34 #H2T34
  66   elim (IH … H1T34 H2T34 … HL01 … HL02) [|*: /4 width=5 by cpm_fpbq, fpbq_fpbg_trans/ ] -L0 -T0 -T3 (**)
  67   #T3 #H1T13 #H2T13 #H1T43 #H2T43
  68   <minus_plus >arith_l3
  69   /3 width=7 by cpms_step_sn, tdeq_trans, ex4_intro/
  70 ]
  71 qed-.