proposition: Lemma fold_loop_aux_spec e f todo: forall todo', below_I ((e,f)::todo) -> ofold (loop_aux e f) A todo = Some todo' -> todo ≦ todo' /\ below_I todo' /\ forall a, In a A -> epsilon' a e = epsilon' a f /\ forall i, In i I -> In (pderiv' a i e, pderiv' a i f) todo'.
proof: Proof. induction A as [|b B IH]; simpl ofold; intros todo'. intros Hvars H. injection H. intros <-. split. reflexivity. split. intros ? ? ?. apply Hvars. now right. intros _ []. unfold obind. fold_ugregex_type. case_eq (ofold (X:=ord Pred -> bool) (loop_aux e f) B todo). 2: discriminate. intros todo'' Htodo'' Hvars Htodo'. apply IH in Htodo'' as [Htodo''_leq [Hvars' Htodo'']]. 2: assumption. clear IH. apply loop_aux_spec in Htodo' as (Heps&Htodo'_leq&Hvars''&Htodo'). split. etransitivity; eassumption. split. assumption. intros a [<-|Ha]. now split. apply Htodo'' in Ha as [Haeps Ha]. split. assumption. intros. now apply Htodo'_leq, Ha. intros ? ? [E|?]. injection E; intros <- <-. apply Hvars; now left. now apply Hvars'. Qed.
imports: lset kat positives sums glang boolean comparisons powerfix ugregex