matita/matita/contribs/lambdadelta/basic_2/dynamic/cnv_cpms_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/notation/relations/predstar_7.ma".
  16 include "basic_2/dynamic/cnv_cpm_trans.ma".
  17 include "basic_2/dynamic/cnv_cpm_conf.ma".
  18
  19 (* CONTEXT-SENSITIVE NATIVE VALIDITY FOR TERMS ******************************)
  20
  21 definition cpsms (n) (h) (o): relation4 genv lenv term term ≝ λG,L,T1,T2.
  22                  ∃∃n1,n2,T. T1 ≛[h,o] T → ⊥ & ⦃G, L⦄ ⊢ T1 ➡[n1,h] T & ⦃G, L⦄ ⊢ T ➡*[n2,h] T2 & n1+n2 = n.
  23
  24 interpretation
  25    "context-sensitive parallel stratified t-bound  rt-computarion (term)"
  26    'PRedStar n h o G L T1 T2 = (cpsms n h o G L T1 T2).
  27
  28 definition IH_cnv_cpsms_conf_lpr (a) (h) (o): relation3 genv lenv term ≝
  29                                  λG,L0,T0. ⦃G, L0⦄ ⊢ T0 ![a,h] →
  30                                  ∀n1,T1. ⦃G, L0⦄ ⊢ T0 ➡*[n1,h,o] T1 → ∀n2,T2. ⦃G, L0⦄ ⊢ T0 ➡*[n2,h,o] T2 →
  31                                  ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 →
  32                                  ∃∃T. ⦃G, L1⦄ ⊢ T1 ➡*[n2-n1,h] T & ⦃G, L2⦄ ⊢ T2 ➡*[n1-n2,h] T.
  33
  34 (* Sub confluence propery with t-bound rt-computation for terms *************)
  35
  36 fact cnv_cpsms_conf_lpr_aux (a) (h) (o):
  37                             ∀G0,L0,T0.
  38                             (∀G1,L1,T1. ⦃G0, L0, T0⦄ >[h, o] ⦃G1, L1, T1⦄ → IH_cnv_cpm_trans_lpr a h G1 L1 T1) →
  39                             (∀G1,L1,T1. ⦃G0, L0, T0⦄ >[h, o] ⦃G1, L1, T1⦄ → IH_cnv_cpms_conf_lpr a h G1 L1 T1) →
  40                             ∀G1,L1,T1. G0 = G1 → L0 = L1 → T0 = T1 → IH_cnv_cpsms_conf_lpr a h o G1 L1 T1.
  41 #a #h #o #G #L #T #IH2 #IH1 #G0 #L0 #T0 #HG #HL #HT #HT0
  42 #n1 #T1 * #m11 #m12 #X1 #HnX01 #HX01 #HXT1 #H1
  43 #n2 #T2 * #m21 #m22 #X2 #HnX02 #HX02 #HXT2 #H2
  44 #L1 #HL01 #L2 #HL02 destruct
  45 lapply (cnv_cpm_trans_lpr_aux … IH1 IH2 … HX01 … L0 ?) // #HX1
  46 lapply (cnv_cpm_trans_lpr_aux … IH1 IH2 … HX02 … L0 ?) // #HX2
  47 elim (cnv_cpm_conf_lpr_aux … IH2 IH1 … HX01 … HX02 … L0 … L0) // #Z0 #HXZ10 #HXZ20
  48 cut (⦃G0,L0,T0⦄ >[h,o] ⦃G0,L0,X1⦄) [ /4 width=5 by cpms_fwd_fpbs, cpm_fpb, ex2_3_intro/ ] #H1fpbg (**) (* cut *)
  49 lapply (fpbg_fpbs_trans ??? G0 ? L0 ? Z0 ? … H1fpbg) [ /2 width=2 by cpms_fwd_fpbs/ ] #H2fpbg
  50 lapply (cnv_cpms_trans_lpr_sub … IH2 … HXZ10 … L0 ?) // #HZ0
  51 elim (IH1 … HXT1 … HXZ10 … L1 … L0) [|*: /4 width=2 by fpb_fpbg, cpm_fpb/ ] -HXT1 -HXZ10 #Z1 #HTZ1 #HZ01
  52 elim (IH1 … HXT2 … HXZ20 … L2 … L0) [|*: /4 width=2 by fpb_fpbg, cpm_fpb/ ] -HXT2 -HXZ20 #Z2 #HTZ2 #HZ02
  53 elim (IH1 … HZ01 … HZ02  L1 … L2) // -L0 -T0 -X1 -X2 -Z0 #Z #HZ01 #HZ02
  54 lapply (cpms_trans … HTZ1 … HZ01) -Z1 <arith_l4 #HT1Z
  55 lapply (cpms_trans … HTZ2 … HZ02) -Z2 <arith_l4 #HT2Z
  56 /2 width=3 by ex2_intro/
  57 qed-.