document: Learning deterministic regular expressions for the inference of schemas from XML data Inferring an appropriate DTD or XML Schema Definition ( XSD ) for a given collection of XML documents essentially reduces to learning deterministic regular expressions from sets of positive example words . Unfortunately , there is no algorithm capable of learning the complete class of deterministic regular expressions from positive examples only , as we will show . The regular expressions occurring in practical DTDs and XSDs , however , are such that every alphabet symbol occurs only a small number of times . As such , in practice it suffices to learn the subclass of regular expressions in which each alphabet symbol occurs at most k times , for some small k. We refer to such expressions as k-occurrence regular expressions ( k-OREs for short ) . Motivated by this observation , we provide a probabilistic algorithm that learns k-OREs for increasing values of k , and selects the one that best describes the sample based on a Minimum Description Length argument . The effectiveness of the method is empirically validated both on real world and synthetic data . Furthermore , the method is shown to be conservative over the simpler classes of expressions considered in previous work .
doc_bio_tags: B O B I O O O O O O B O O O O O O B O O O O O O O O O O B O O O O B O B I O O O O O O O O O O O O O O O B O O O O O B I O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O