Overview

This paper deals with the expression power and decidability of XML schema lan-guages. In the first section we will analyze Document Type Definitions (DTDs) by transforming them to string grammars and taking a closer look at the re-sulting language classes. In the second section one-unambiguity—a property of language classes that will proof itself very useful for further analysis—is in-troduced and methods are given, which can be used to determine if a certain regular expression or regular language is in fact one-unambiguous. Finally in the third section of this paper we will compare XML schema languages using formal language theory. 1 XML Languages and Grammars 1.1 Introduction and Basics XML is a general-purpose markup language widely in use. However the syn-tactical constraints imposed by XML itself are too general to be sufficient for most applications. To further restrict the set of valid documents, XML schema languages are used to define the relative positions of pairs of corresponding tag