-(* theorem 16: 4 *)
-nlemma star_dot: ∀S.∀e:pre S. 𝐋\p (e^⊛) = 𝐋\p e · (𝐋 |\fst e|)^*.
-#S p; ncases p; #e b; ncases b;
-##[ nchange in match (〈e,true〉^⊛) with 〈?,?〉;
- nletin e' ≝ (\fst (•e)); nletin b' ≝ (\snd (•e));
- nchange in ⊢ (??%?) with (?∪?);
- nchange in ⊢ (??(??%?)?) with (𝐋\p e' · 𝐋 |e'|^* );
- nrewrite > (?: 𝐋\p e' = 𝐋\p e ∪ (𝐋 |e| - ϵ b' )); ##[##2:
- nlapply (bull_cup ? e); #bc;
- nchange in match (𝐋\p (•e)) in bc with (?∪?);
- nchange in match b' in bc with b';
- ncases b' in bc; ##[##2: nrewrite > (cup0…); nrewrite > (sub0…); //]
- nrewrite > (cup_sub…); ##[napply rcanc_sing] //;##]
- nrewrite > (cup_dotD…); nrewrite > (cupA…);nrewrite > (erase_bull…);
- nrewrite > (sub_dot_star…);
- nchange in match (𝐋\p 〈?,?〉) with (?∪?);
- nrewrite > (cup_dotD…); nrewrite > (epsilon_dot…); //;
-##| nwhd in match (〈e,false〉^⊛); nchange in match (𝐋\p 〈?,?〉) with (?∪?);
- nrewrite > (cup0…);
- nchange in ⊢ (??%?) with (𝐋\p e · 𝐋 |e|^* );
- nrewrite < (cup0 ? (𝐋\p e)); //;##]
-nqed.
-
-nlet rec pre_of_re (S : Alpha) (e : re S) on e : pitem S ≝
- match e with
- [ z ⇒ pz ?
- | e ⇒ pe ?
- | s x ⇒ ps ? x
- | c e1 e2 ⇒ pc ? (pre_of_re ? e1) (pre_of_re ? e2)
- | o e1 e2 ⇒ po ? (pre_of_re ? e1) (pre_of_re ? e2)
- | k e1 ⇒ pk ? (pre_of_re ? e1)].
-
-nlemma notFalse : ¬False. @; //; nqed.
-
-nlemma dot0 : ∀S.∀A:word S → Prop. {} · A = {}.
-#S A; nnormalize; napply extP; #w; @; ##[##2: *]
-*; #w1; *; #w2; *; *; //; nqed.
-
-nlemma Lp_pre_of_re : ∀S.∀e:re S. 𝐋\p (pre_of_re ? e) = {}.
-#S e; nelim e; ##[##1,2,3: //]
-##[ #e1 e2 H1 H2; nchange in match (𝐋\p (pre_of_re S (e1 e2))) with (?∪?);
- nrewrite > H1; nrewrite > H2; nrewrite > (dot0…); nrewrite > (cupID…);//
-##| #e1 e2 H1 H2; nchange in match (𝐋\p (pre_of_re S (e1+e2))) with (?∪?);
- nrewrite > H1; nrewrite > H2; nrewrite > (cupID…); //
-##| #e1 H1; nchange in match (𝐋\p (pre_of_re S (e1^* ))) with (𝐋\p (pre_of_re ??) · ?);
- nrewrite > H1; napply dot0; ##]
-nqed.
-
-nlemma erase_pre_of_reK : ∀S.∀e. 𝐋 |pre_of_re S e| = 𝐋 e.
-#S A; nelim A; //;
-##[ #e1 e2 H1 H2; nchange in match (𝐋 (e1 · e2)) with (𝐋 e1·?);
- nrewrite < H1; nrewrite < H2; //
-##| #e1 e2 H1 H2; nchange in match (𝐋 (e1 + e2)) with (𝐋 e1 ∪ ?);
- nrewrite < H1; nrewrite < H2; //
-##| #e1 H1; nchange in match (𝐋 (e1^* )) with ((𝐋 e1)^* );
- nrewrite < H1; //]
-nqed.
-
-(* corollary 17 *)
-nlemma L_Lp_bull : ∀S.∀e:re S.𝐋 e = 𝐋\p (•pre_of_re ? e).
-#S e; nrewrite > (bull_cup…); nrewrite > (Lp_pre_of_re…);
-nrewrite > (cupC…); nrewrite > (cup0…); nrewrite > (erase_pre_of_reK…); //;
-nqed.
-
-nlemma Pext : ∀S.∀f,g:word S → Prop. f = g → ∀w.f w → g w.
-#S f g H; nrewrite > H; //; nqed.
-
-(* corollary 18 *)
-ntheorem bull_true_epsilon : ∀S.∀e:pitem S. \snd (•e) = true ↔ [ ] ∈ |e|.
-#S e; @;
-##[ #defsnde; nlapply (bull_cup ? e); nchange in match (𝐋\p (•e)) with (?∪?);
- nrewrite > defsnde; #H;
- nlapply (Pext ??? H [ ] ?); ##[ @2; //] *; //;
-
-STOP
-
-notation > "\move term 90 x term 90 E"
-non associative with precedence 60 for @{move ? $x $E}.
-nlet rec move (S: Alpha) (x:S) (E: pitem S) on E : pre S ≝
- match E with
- [ pz ⇒ 〈 ∅, false 〉
- | pe ⇒ 〈 ϵ, false 〉
- | ps y ⇒ 〈 `y, false 〉
- | pp y ⇒ 〈 `y, x == y 〉
- | po e1 e2 ⇒ \move x e1 ⊕ \move x e2
- | pc e1 e2 ⇒ \move x e1 ⊙ \move x e2
- | pk e ⇒ (\move x e)^⊛ ].
-notation < "\move\shy x\shy E" non associative with precedence 60 for @{'move $x $E}.
-notation > "\move term 90 x term 90 E" non associative with precedence 60 for @{'move $x $E}.
-interpretation "move" 'move x E = (move ? x E).
-
-ndefinition rmove ≝ λS:Alpha.λx:S.λe:pre S. \move x (\fst e).
-interpretation "rmove" 'move x E = (rmove ? x E).
-
-nlemma XXz : ∀S:Alpha.∀w:word S. w ∈ ∅ → False.
-#S w abs; ninversion abs; #; ndestruct;
-nqed.
-
-
-nlemma XXe : ∀S:Alpha.∀w:word S. w .∈ ϵ → False.
-#S w abs; ninversion abs; #; ndestruct;
-nqed.
-
-nlemma XXze : ∀S:Alpha.∀w:word S. w .∈ (∅ · ϵ) → False.
-#S w abs; ninversion abs; #; ndestruct; /2/ by XXz,XXe;
-nqed.
-
-
-naxiom in_move_cat:
- ∀S.∀w:word S.∀x.∀E1,E2:pitem S. w .∈ \move x (E1 · E2) →
- (∃w1.∃w2. w = w1@w2 ∧ w1 .∈ \move x E1 ∧ w2 ∈ .|E2|) ∨ w .∈ \move x E2.
-#S w x e1 e2 H; nchange in H with (w .∈ \move x e1 ⊙ \move x e2);
-ncases e1 in H; ncases e2;
-##[##1: *; ##[*; nnormalize; #; ndestruct]
- #H; ninversion H; ##[##1,4,5,6: nnormalize; #; ndestruct]
- nnormalize; #; ndestruct; ncases (?:False); /2/ by XXz,XXze;
-##|##2: *; ##[*; nnormalize; #; ndestruct]
- #H; ninversion H; ##[##1,4,5,6: nnormalize; #; ndestruct]
- nnormalize; #; ndestruct; ncases (?:False); /2/ by XXz,XXze;
-##| #r; *; ##[ *; nnormalize; #; ndestruct]
- #H; ninversion H; ##[##1,4,5,6: nnormalize; #; ndestruct]
- ##[##2: nnormalize; #; ndestruct; @2; @2; //.##]
- nnormalize; #; ndestruct; ncases (?:False); /2/ by XXz;
-##| #y; *; ##[ *; nnormalize; #defw defx; ndestruct; @2; @1; /2/ by conj;##]
- #H; ninversion H; nnormalize; #; ndestruct;
- ##[ncases (?:False); /2/ by XXz] /3/ by or_intror;
-##| #r1 r2; *; ##[ *; #defw]
- ...
-nqed.
-
-ntheorem move_ok:
- ∀S:Alpha.∀E:pre S.∀a,w.w .∈ \move a E ↔ (a :: w) .∈ E.
-#S E; ncases E; #r b; nelim r;
-##[##1,2: #a w; @;
- ##[##1,3: nnormalize; *; ##[##1,3: *; #; ndestruct; ##| #abs; ncases (XXz … abs); ##]
- #H; ninversion H; #; ndestruct;
- ##|##*:nnormalize; *; ##[##1,3: *; #; ndestruct; ##| #H1; ncases (XXz … H1); ##]
- #H; ninversion H; #; ndestruct;##]
-##|#a c w; @; nnormalize; ##[*; ##[*; #; ndestruct; ##] #abs; ninversion abs; #; ndestruct;##]
- *; ##[##2: #abs; ninversion abs; #; ndestruct; ##] *; #; ndestruct;
-##|#a c w; @; nnormalize;
- ##[ *; ##[ *; #defw; nrewrite > defw; #ca; @2; nrewrite > (eqb_t … ca); @; ##]
- #H; ninversion H; #; ndestruct;
- ##| *; ##[ *; #; ndestruct; ##] #H; ninversion H; ##[##2,3,4,5,6: #; ndestruct]
- #d defw defa; ndestruct; @1; @; //; nrewrite > (eqb_true S d d); //. ##]
-##|#r1 r2 H1 H2 a w; @;
- ##[ #H; ncases (in_move_cat … H);
- ##[ *; #w1; *; #w2; *; *; #defw w1m w2m;
- ncases (H1 a w1); #H1w1; #_; nlapply (H1w1 w1m); #good;
- nrewrite > defw; @2; @2 (a::w1); //; ncases good; ##[ *; #; ndestruct] //.
- ##|
- ...
-##|
-##|
-##]
-nqed.
-
-
-notation > "x ↦* E" non associative with precedence 60 for @{move_star ? $x $E}.
-nlet rec move_star (S : decidable) w E on w : bool × (pre S) ≝
- match w with
- [ nil ⇒ E
- | cons x w' ⇒ w' ↦* (x ↦ \snd E)].
-
-ndefinition in_moves ≝ λS:decidable.λw.λE:bool × (pre S). \fst(w ↦* E).
-
-ncoinductive equiv (S:decidable) : bool × (pre S) → bool × (pre S) → Prop ≝
- mk_equiv:
- ∀E1,E2: bool × (pre S).
- \fst E1 = \fst E2 →
- (∀x. equiv S (x ↦ \snd E1) (x ↦ \snd E2)) →
- equiv S E1 E2.
-
-ndefinition NAT: decidable.
- @ nat eqb; /2/.
-nqed.
-
-include "hints_declaration.ma".
-
-alias symbol "hint_decl" (instance 1) = "hint_decl_Type1".
-unification hint 0 ≔ ; X ≟ NAT ⊢ carr X ≡ nat.
-
-ninductive unit: Type[0] ≝ I: unit.
-
-nlet corec foo_nop (b: bool):
- equiv ?
- 〈 b, pc ? (ps ? 0) (pk ? (pc ? (ps ? 1) (ps ? 0))) 〉
- 〈 b, pc ? (pk ? (pc ? (ps ? 0) (ps ? 1))) (ps ? 0) 〉 ≝ ?.
- @; //; #x; ncases x
- [ nnormalize in ⊢ (??%%); napply (foo_nop false)
- | #y; ncases y
- [ nnormalize in ⊢ (??%%); napply (foo_nop false)
- | #w; nnormalize in ⊢ (??%%); napply (foo_nop false) ]##]
-nqed.