1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "delayed_updating/syntax/path_labels.ma".
16 include "delayed_updating/notation/functions/downarrowright_2.ma".
17 include "ground/arith/nat_plus.ma".
18 include "ground/arith/nat_pred_succ.ma".
20 (* HEAD FOR PATH ************************************************************)
22 rec definition path_head (n) (p) on p: path ā
27 [ list_empty ā šāān
30 [ label_d k ā (path_head (n+k) q)āl
31 | label_m ā (path_head n q)āl
32 | label_L ā (path_head (ām) q)āl
33 | label_A ā (path_head n q)āl
34 | label_S ā (path_head n q)āl
41 'DownArrowRight n p = (path_head n p).
43 (* basic constructions ****************************************************)
45 lemma path_head_zero (p):
49 lemma path_head_empty (n):
50 (šāān) = ā³[n]š.
53 lemma path_head_d_dx (p) (n) (k:pnat):
54 (ā³[ān+k]p)āš±k = ā³[ān](pāš±k).
57 lemma path_head_m_dx (p) (n):
58 (ā³[ān]p)āšŗ = ā³[ān](pāšŗ).
61 lemma path_head_L_dx (p) (n):
62 (ā³[n]p)āš = ā³[ān](pāš).
67 lemma path_head_A_dx (p) (n):
68 (ā³[ān]p)āš = ā³[ān](pāš).
71 lemma path_head_S_dx (p) (n):
72 (ā³[ān]p)āš¦ = ā³[ān](pāš¦).
75 (* Basic inversions *********************************************************)
77 lemma eq_inv_path_head_zero_dx (q) (p):
78 q = ā³[š]p ā š = q.
82 lemma eq_inv_path_empty_head (p) (n):
83 (š) = ā³[n]p ā š = n.
85 [ #n <path_head_empty #H0
86 <(eq_inv_empty_labels ā¦ H0) -n //
87 | * [ #k ] #p #n @(nat_ind_succ ā¦ n) -n // #n #_
97 (* Constructions with path_append *******************************************)
99 lemma path_head_refl_append_bi (p) (q) (m) (n):
100 p = ā³[m]p ā q = ā³[n]q ā pāq = ā³[n+m](pāq).
103 <(eq_inv_path_empty_head ā¦ H0) -n //
104 | #l #q #IH #m #n #Hp
105 @(nat_ind_succ ā¦ n) -n // #n #_
107 <list_append_lcons_sn <nplus_succ_sn
108 [ <path_head_d_dx <path_head_d_dx #Hq
109 elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq
110 >(IH ā¦ Hp Hq) in ā¢ (??%?); -IH -Hp -Hq
111 <nplus_plus_comm_23 //
112 | <path_head_m_dx <path_head_m_dx #Hq
113 elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq
114 >(IH ā¦ Hp Hq) in ā¢ (??%?); -IH -Hp -Hq //
115 | <path_head_L_dx <path_head_L_dx #Hq
116 elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq
117 >(IH ā¦ Hp Hq) in ā¢ (??%?); -IH -Hp -Hq //
118 | <path_head_A_dx <path_head_A_dx #Hq
119 elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq
120 >(IH ā¦ Hp Hq) in ā¢ (??%?); -IH -Hp -Hq //
121 | <path_head_S_dx <path_head_S_dx #Hq
122 elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq
123 >(IH ā¦ Hp Hq) in ā¢ (??%?); -IH -Hp -Hq //
127 lemma path_head_refl_append_sn (p) (q) (n):
128 q = ā³[n]q ā q = ā³[n](pāq).
130 [ #n #Hn <(eq_inv_path_empty_head ā¦ Hn) -Hn //
131 | #l #q #IH #n @(nat_ind_succ ā¦ n) -n
132 [ #Hq | #n #_ cases l [ #k ] ]
133 [ lapply (eq_inv_path_head_zero_dx ā¦ Hq) -Hq #Hq destruct
134 | <path_head_d_dx <path_head_d_dx
135 | <path_head_m_dx <path_head_m_dx
136 | <path_head_L_dx <path_head_L_dx
137 | <path_head_A_dx <path_head_A_dx
138 | <path_head_S_dx <path_head_S_dx
140 elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq
145 (* Inversions with path_append **********************************************)
147 lemma eq_inv_path_head_refl_append_sn (p) (q) (n):
148 q = ā³[n](pāq) ā q = ā³[n]q.
150 [ #n #Hn <(eq_inv_path_empty_head ā¦ Hn) -p //
151 | #l #q #IH #n @(nat_ind_succ ā¦ n) -n //
153 [ <path_head_d_dx <path_head_d_dx
154 | <path_head_m_dx <path_head_m_dx
155 | <path_head_L_dx <path_head_L_dx
156 | <path_head_A_dx <path_head_A_dx
157 | <path_head_S_dx <path_head_S_dx
159 elim (eq_inv_list_lcons_bi ????? Hq) -Hq #_ #Hq