Schema Evolution publication categorizer

This paper presents XEvolve, a framework that unifies streaming validation of XML documents, and efficient testing of equivalence and inclusion of specifications for various XML schema languages. For these purposes, this framework relies on Visibly Pushdown Automata (VPA) as a unifying model for the various schema languages. Schemas are first translated into VPA; standard algorithms for VPA can be then used to validate documents as well as to test equivalence or inclusion of schemas. In general, inclusion and equivalence are tested in exponential-time. However, when the given specifications are provided as DTD or XSD, these tests have a polynomial-time complexity with respect to the automaton size. Moreover, in this case the memory foot-print of the validation does not depend on the size of the input document but only on its depth.