proposition: Lemma max_label_collect: forall a i e f A, i < max_label (build a e f A) -> (exists2 j, i<=j & NumSet.In (state_of_nat j) (collect a NumSet.empty)) \/ i < max_label A.
proof: Proof. induction a; simpl; intros i e f A Hi; rewrite ?max_label_add_one, ?max_label_incr in *; auto. eapply IHa1 in Hi as [[j ? Hj]|Hi]. left. exists j; auto. eapply collect_incr_1 in Hj as [?|?]. eassumption. NumSetProps.setdec. eapply IHa2 in Hi as [[j ? ?]|Hi]. left. exists j; auto using collect_incr_2. right. destruct A. assumption. eapply IHa1 in Hi as [[j ? Hj]|Hi]. left. exists j; auto. eapply collect_incr_1 in Hj as [?|?]. eassumption. NumSetProps.setdec. eapply IHa2 in Hi as [[j ? ?]|Hi]. left. exists j; auto using collect_incr_2. right. assumption. eapply IHa in Hi as [Hi|Hi]; auto. revert Hi. rewrite max_label_add_one, max_label_incr. auto. revert Hi. rewrite max_label_add_var. num_simpl. apply Nat.max_case; auto. intro Hi. left. exists (nat_of_num p). auto with arith. num_simpl. auto with set. Qed.
imports: ATBR(Common) ATBR(Classes) ATBR(Graph) ATBR(Monoid) ATBR(SemiLattice) ATBR(SemiRing) ATBR(KleeneAlgebra) ATBR(MxGraph) ATBR(MxSemiLattice) ATBR(MxSemiRing) ATBR(MxKleeneAlgebra) ATBR(DKA_Definitions) ATBR(DKA_CheckLabels) ATBR(StrictStarForm) ATBR(Utils_WF) Coq(Relations)