Taxonomy of XML schema languages using formal language theory

Makoto Murata, Dongwon Lee, Murali Mani, Kohsuke Kawaguchi

Research output: Contribution to journalArticlepeer-review

218 Scopus citations


On the basis of regular tree grammars, we present a formal framework for XML schema languages. This framework helps to describe, compare, and implement such schema languages in a rigorous manner. Our main results are as follows: (1) a simple framework to study three classes of tree languages (local, single-type, and regular); (2) classification and comparison of schema languages (DTD, W3C XML Schema, and RELAX NG) based on these classes; (3) efficient document validation algorithms for these classes; and (4) other grammatical concepts and advanced validation algorithms relevant to an XML model (e.g., binarization, derivative-based validation).

Original languageEnglish (US)
Pages (from-to)660-674
Number of pages15
JournalACM Transactions on Internet Technology
Issue number4
StatePublished - Dec 1 2005

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications


Dive into the research topics of 'Taxonomy of XML schema languages using formal language theory'. Together they form a unique fingerprint.

Cite this