  The advantages for the presence of an XML schema for XML documents are
numerous. However, many XML documents in practice are not accompanied by a
schema or by a valid schema. Relax NG is a popular and powerful schema
language, which supports the unconstrained interleaving operator. Focusing on
the inference of Relax NG, we propose a new subclass of regular expressions
with interleaving and design a polynomial inference algorithm. Then we
conducted a series of experiments based on large-scale real data and on three
XML data corpora, and experimental results show that our subclass has a better
practicality than previous ones, and the regular expressions inferred by our
algorithm are more precise.
