From 119da3f9ce130f7c4e8b23fcc491d221472ad657 Mon Sep 17 00:00:00 2001 From: Ferruccio Guidi Date: Wed, 2 Nov 2022 18:30:43 +0100 Subject: [PATCH] update in delayed_updating commutations of balanced reduction completed --- .../delayed_updating/reduction/dbfr_ibfr.ma | 4 +- .../delayed_updating/reduction/dbfr_lift.ma | 56 +++++++++++++++ .../delayed_updating/reduction/dfr_ifr.ma | 4 +- .../delayed_updating/reduction/dfr_lift.ma | 2 +- .../delayed_updating/reduction/ibfr_lift.ma | 63 +++++++++++++++++ .../delayed_updating/reduction/ibfr_unwind.ma | 70 +++++++++++++++++++ .../delayed_updating/reduction/ifr_lift.ma | 2 +- .../delayed_updating/reduction/ifr_unwind.ma | 4 +- .../substitution/lift_rmap_closed.ma | 30 ++++++-- .../unwind/unwind2_rmap_closed.ma | 31 ++++---- 10 files changed, 238 insertions(+), 28 deletions(-) create mode 100644 matita/matita/contribs/lambdadelta/delayed_updating/reduction/dbfr_lift.ma create mode 100644 matita/matita/contribs/lambdadelta/delayed_updating/reduction/ibfr_lift.ma create mode 100644 matita/matita/contribs/lambdadelta/delayed_updating/reduction/ibfr_unwind.ma diff --git a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dbfr_ibfr.ma b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dbfr_ibfr.ma index fd62cdd78..eee619916 100644 --- a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dbfr_ibfr.ma +++ b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dbfr_ibfr.ma @@ -45,7 +45,7 @@ theorem dbfr_des_ibfr (f) (t1) (t2) (r): t1 ϵ 𝐓 → /2 width=2 by path_closed_structure_depth/ | lapply (in_comp_unwind2_path_term f … Ht1) -H0t1 -Hb -Hm -Ht2 -Ht1 list_append_rcons_dx >list_append_assoc - unwind2_rmap_A_dx /2 width=2 by tls_succ_plus_unwind2_rmap_append_closed_bLq_dx/ ] diff --git a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dbfr_lift.ma b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dbfr_lift.ma new file mode 100644 index 000000000..fc67c5779 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dbfr_lift.ma @@ -0,0 +1,56 @@ +(**************************************************************************) +(* ___ *) +(* ||M|| *) +(* ||A|| A project by Andrea Asperti *) +(* ||T|| *) +(* ||I|| Developers: *) +(* ||T|| The HELM team. *) +(* ||A|| http://helm.cs.unibo.it *) +(* \ / *) +(* \ / This file is distributed under the terms of the *) +(* v GNU General Public License Version 2 *) +(* *) +(**************************************************************************) + +include "delayed_updating/reduction/dbfr.ma". + +include "delayed_updating/substitution/fsubst_lift.ma". +include "delayed_updating/substitution/fsubst_eq.ma". +include "delayed_updating/substitution/lift_constructors.ma". +include "delayed_updating/substitution/lift_path_structure.ma". +include "delayed_updating/substitution/lift_path_closed.ma". +include "delayed_updating/substitution/lift_rmap_closed.ma". + +(* DELAYED BALANCED FOCUSED REDUCTION ***************************************) + +(* Constructions with lift **************************************************) + +theorem dbfr_lift_bi (f) (t1) (t2) (r): + t1 ➡𝐝𝐛𝐟[r] t2 → 🠡[f]t1 ➡𝐝𝐛𝐟[🠡[f]r] 🠡[f]t2. +#f #t1 #t2 #r +* #p #b #q #m #n #Hr #Hb #Hm #Hn #Ht1 #Ht2 destruct +@(ex6_5_intro … (🠡[f]p) (🠡[🠢[f](p◖𝗔)]b) (🠡[🠢[f](p◖𝗔●b◖𝗟)]q) (🠢[f](p●𝗔◗b)@❨m❩) (🠢[f](p●𝗔◗b●𝗟◗q)@§❨n❩)) +[ -Hb -Hm -Hn -Ht1 -Ht2 // +| -Hm -Hn -Ht1 -Ht2 // +| -Hb -Hn -Ht1 -Ht2 + /2 width=1 by lift_path_closed/ +| -Hb -Hm -Ht1 -Ht2 + /2 width=1 by lift_path_rmap_closed_L/ +| lapply (in_comp_lift_path_term f … Ht1) -Ht2 -Ht1 -Hn + list_append_assoc + >(nap_plus_lift_rmap_append_closed_Lq_dx … Hn) + @iref_eq_repl + @(subset_eq_canc_sn … (lift_term_grafted_S …)) + @lift_term_eq_repl_sn +(* Note: crux of the proof begins *) + >lift_rmap_A_dx + /2 width=2 by tls_succ_plus_lift_rmap_append_closed_bLq_dx/ +(* Note: crux of the proof ends *) +] +qed. diff --git a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dfr_ifr.ma b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dfr_ifr.ma index c07a3d26a..1cb62ed3b 100644 --- a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dfr_ifr.ma +++ b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/dfr_ifr.ma @@ -42,7 +42,7 @@ theorem dfr_des_ifr (f) (t1) (t2) (r): t1 ϵ 𝐓 → /2 width=2 by path_closed_structure_depth/ | lapply (in_comp_unwind2_path_term f … Ht1) -Ht2 -Ht1 -H0t1 list_append_assoc + >(nap_plus_lift_rmap_append_closed_Lq_dx … Hn) -Hn // + | >lift_rmap_A_dx >nsucc_unfold + /2 width=2 by tls_succ_plus_lift_rmap_append_closed_bLq_dx/ + ] +(* Note: crux of the proof ends *) +] +qed. diff --git a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ibfr_unwind.ma b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ibfr_unwind.ma new file mode 100644 index 000000000..f3d7d16fa --- /dev/null +++ b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ibfr_unwind.ma @@ -0,0 +1,70 @@ +(**************************************************************************) +(* ___ *) +(* ||M|| *) +(* ||A|| A project by Andrea Asperti *) +(* ||T|| *) +(* ||I|| Developers: *) +(* ||T|| The HELM team. *) +(* ||A|| http://helm.cs.unibo.it *) +(* \ / *) +(* \ / This file is distributed under the terms of the *) +(* v GNU General Public License Version 2 *) +(* *) +(**************************************************************************) + +include "delayed_updating/reduction/ibfr.ma". + +include "delayed_updating/unwind/unwind2_preterm_fsubst.ma". +include "delayed_updating/unwind/unwind2_preterm_eq.ma". +include "delayed_updating/unwind/unwind2_prototerm_lift.ma". +include "delayed_updating/unwind/unwind2_rmap_closed.ma". + +include "delayed_updating/substitution/fsubst_eq.ma". +include "delayed_updating/substitution/lift_prototerm_eq.ma". + +include "delayed_updating/syntax/path_closed_structure.ma". +include "delayed_updating/syntax/path_structure_depth.ma". + +(* IMMEDIATE BALANCED FOCUSED REDUCTION *************************************) + +(* Constructions with unwind2 ***********************************************) + +lemma ibfr_unwind_bi (f) (t1) (t2) (r): + t1 ϵ 𝐓 → r ϵ 𝐈 → + t1 ➡𝐢𝐛𝐟[r] t2 → ▼[f]t1 ➡𝐢𝐛𝐟[⊗r] ▼[f]t2. +#f #t1 #t2 #r #H1t1 #H2r +* #p #b #q #m #n #Hr #Hb #Hm #Hn #Ht1 #Ht2 destruct +@(ex6_5_intro … (⊗p) (⊗b) (⊗q) (♭b) (♭q)) +[ -H1t1 -H2r -Hb -Hm -Hn -Ht1 -Ht2 // +| -H1t1 -H2r -Hm -Hn -Ht1 -Ht2 // +| -H1t1 -H2r -Hb -Hn -Ht1 -Ht2 + /2 width=2 by path_closed_structure_depth/ +| -H1t1 -H2r -Hb -Hm -Ht1 -Ht2 + /2 width=2 by path_closed_structure_depth/ +| lapply (in_comp_unwind2_path_term f … Ht1) -Ht2 -Ht1 -H1t1 -H2r -Hb + list_append_assoc + unwind2_rmap_A_dx + /2 width=2 by tls_succ_plus_unwind2_rmap_append_closed_bLq_dx/ + ] +(* Note: crux of the proof ends *) + | // + | /2 width=2 by ex_intro/ + | // + ] +] +qed. diff --git a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ifr_lift.ma b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ifr_lift.ma index 35a00a368..cd597c2bb 100644 --- a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ifr_lift.ma +++ b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ifr_lift.ma @@ -49,7 +49,7 @@ theorem ifr_lift_bi (f) (t1) (t2) (r): (* Note: crux of the proof begins *) @(stream_eq_trans … (tr_compose_uni_dx_pap …)) nsucc_unfold - /2 width=2 by tls_succ_lift_rmap_append_L_closed_dx/ + /2 width=2 by tls_succ_lift_rmap_append_closed_Lq_dx/ (* Note: crux of the proof ends *) ] qed. diff --git a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ifr_unwind.ma b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ifr_unwind.ma index 2e048c7a5..d931a1a7b 100644 --- a/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ifr_unwind.ma +++ b/matita/matita/contribs/lambdadelta/delayed_updating/reduction/ifr_unwind.ma @@ -40,7 +40,7 @@ lemma ifr_unwind_bi (f) (t1) (t2) (r): /2 width=2 by path_closed_structure_depth/ | lapply (in_comp_unwind2_path_term f … Ht1) -Ht2 -Ht1 -H1t1 -H2r nplus_succ_dx (unwind2_rmap_append_closed_true_dx_xap_depth f p … Hb) -Hb ->(unwind2_rmap_append_closed_Lq_dx_nap_plus … Hq) -Hq // +>(xap_unwind2_rmap_append_closed_true_dx_depth f p … Hb) -Hb +>(nap_plus_unwind2_rmap_append_closed_Lq_dx_depth … Hq) -Hq // qed-. lemma tls_succ_plus_unwind2_rmap_append_closed_bLq_dx (o) (f) (p) (b) (q) (m) (n): b ϵ 𝐂❨Ⓣ,m❩ → q ϵ 𝐂❨o,n❩ → ▶[f]p ≗ ⇂*[↑(m+n)]▶[f](p●b●𝗟◗q). #o #f #p #b #q #m #n #Hb #Hq ->nplus_succ_dx nplus_succ_dx list_append_assoc @(stream_eq_trans … (tls_unwind2_rmap_append_closed_true_dx … Hb)) -Hb -@stream_tls_eq_repl -@(stream_eq_trans … (tls_succ_unwind2_rmap_append_closed_Lq_dx … Hq)) -Hq // +/3 width=2 by stream_tls_eq_repl, tls_succ_unwind2_rmap_append_closed_Lq_dx/ qed-. -- 2.39.2