proposition: Lemma SubTrieOK : forall trie k subtrie st, TrieOK trie st -> find k (SubTries trie) = Some subtrie -> TrieOK subtrie (st ++ [k]).
proof: Proof. destruct trie; simpl. induction m; simpl in *; intros. - discriminate. - inversion H; subst. case_eq (X.compare k0 k); intros; rewrite H1 in H0. + eapply IHm1; eauto. econstructor; simpl in *; eauto. inversion H4; subst; eauto. + injections; simpl in *. eapply (H7 k0 _); eauto. + eapply IHm2; eauto. econstructor; simpl in *; eauto. inversion H4; subst; eauto. Qed.
imports: Fiat.Common.Coq__8_4__8_5__Compat Fiat.QueryStructure.Implementation.DataStructures.Bags.BagsInterface Fiat.QueryStructure.Implementation.DataStructures.Bags.BagsProperties Coq.FSets.FMapInterface Coq.FSets.FMapFacts Coq.FSets.FMapAVL Coq.ZArith.ZArith Fiat.Common Fiat.Common.List.ListFacts Fiat.Common.List.FlattenList Fiat.Common.SetEqProperties Fiat.Common.FMapExtensions Fiat.Common.List.PermutationFacts Fiat.QueryStructure.Specification.SearchTerms.ListPrefix