matita/matita/contribs/lambda/labelled_sequential_reduction.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 "redex_pointer.ma".
  16 include "multiplicity.ma".
  17
  18 (* LABELLED SEQUENTIAL REDUCTION (ONE STEP) *********************************)
  19
  20 (* Note: the application "(A B)" is represented by "@B.A" following:
  21          F. Kamareddine and R.P. Nederpelt: "A useful λ-notation".
  22          Theoretical Computer Science 155(1), Elsevier (1996), pp. 85-109.
  23 *)
  24 inductive lsred: rpointer → relation term ≝
  25 | lsred_beta   : ∀A,D. lsred (◊) (@D.𝛌.A) ([⬐D]A)
  26 | lsred_abst   : ∀p,A,C. lsred p A C → lsred p (𝛌.A) (𝛌.C)
  27 | lsred_appl_sn: ∀p,B,D,A. lsred p B D → lsred (true::p) (@B.A) (@D.A)
  28 | lsred_appl_dx: ∀p,B,A,C. lsred p A C → lsred (false::p) (@B.A) (@B.C)
  29 .
  30
  31 interpretation "labelled sequential reduction"
  32     'LablSeqRed M p N = (lsred p M N).
  33
  34 (* Note: we do not use → since it is reserved by CIC *)
  35 notation "hvbox( M break ⇀ [ term 46 p ] break term 46 N )"
  36    non associative with precedence 45
  37    for @{ 'LablSeqRed $M $p $N }.
  38
  39 theorem lsred_fwd_mult: ∀p,M,N. M ⇀[p] N → #{N} < #{M} * #{M}.
  40 #p #M #N #H elim H -p -M -N
  41 [ #A #D @(le_to_lt_to_lt … (#{A}*#{D})) //
  42   normalize /3 width=1 by lt_minus_to_plus_r, lt_times/ (**) (* auto: too slow without trace *)
  43 | //
  44 | #p #B #D #A #_ #IHBD
  45   @(lt_to_le_to_lt … (#{B}*#{B}+#{A})) [ /2 width=1/ ] -D -p
  46 | #p #B #A #C #_ #IHAC
  47   @(lt_to_le_to_lt … (#{B}+#{A}*#{A})) [ /2 width=1/ ] -C -p
  48 ]
  49 @(transitive_le … (#{B}*#{B}+#{A}*#{A})) [ /2 width=1/ ]
  50 >distributive_times_plus normalize /2 width=1/
  51 qed-.