CIAA2003

START ConferenceManager

XML Schema Containment Checking based on Semi-implicit Techniques

Akihiko Tozawa and Masami Hagiya

Presented at Eighth International Conference on Implementation and Application of Automata (CIAA 2003), July 16-18, 2003 Santa Barbara, CA, USA

Abstract

XML schemas are computer languages defining grammars of XML (Extensible Markup Languages). Containment checking for XML schemas has many applications, and thus is important. Since XML schemas are related to the class of tree regular languages, their containment checking is reduced to the language containment problem for non-deterministic tree automata (NTAs). However, an NTA for a practical XML schema has 10^2-10^3 states for which the textbook algorithm based on naive determinization is expensive. Thus we in this paper consider techniques based on BDDs (binary decision diagrams). We used semi-implicit encoding which encodes a set of subsets of states as a BDD, rather than encoding a set of states by it. The experiment on several real-world XML schemas proves that our containment checker can answer problems that cannot be solved by previously known algorithms.