|Abstract of Paper|
by Jean Berstel, Luc Boasson
XML documents are described by a document type definition (DTD). An XMLgrammar is a formal grammar that captures the syntactic features of a DTD. We investigate properties of this family of grammars. We show that an XMLlanguage basically has a unique XMLgrammar. We give two characterizations of languages generated by XMLgrammars, one is settheoretic, the other is by a kind of saturation property. We investigate decidability problems and prove that some properties that are undecidable for general contextfree languages become decidable for XMLlanguages.