Formalsprachliche Aspekte von XML

Abstract

Die Dissertation befasst sich mit XML artigen Grammatiken. Dabei werden Abschlusseigenschaften, Entscheidbarkeitsfragen und die Einordnung in die Chomsky Hierarchie von den XML Grammatiken, den einfachen balanacierten Grammatiken, den konkurrenzverhindernden balancierten Grammatiken, den RegDyck Grammatiken und den balancierten Grammatiken untersucht.

XML-like grammars are an abstraction of XML description systemswhich have the aim to structure the content of XML documents. Thereare a lot of different types of XML description systems used in practice:DTD, XML schema, TREX, RELAX NG,... They can be translatedinto grammars which are called XML-like grammars. The XML descriptionsystems which are used in practice can be classified in threedifferent grammar types: balanced grammars, XMLgrammars and single-type balanced grammars. The motivationfor studying these grammars is twofold: first from the theoreticalview, they relate to three other types of grammars which are studiedin the past: parenthesis grammars, bracketed grammars and Chomsky-Schützenberger grammars. Second thereis a practical requirement to study these grammars. The closure propertiesas well as the decision problems are important for XML softwareproducts and the classification in relation to the Chomsky Hierarchycould be important for parsers and parser generators. Besides it couldbe necessary to search for new XML-like grammars, which have betterclosure properties or have more decision problems which are decidableor rather are more efficient to parse. The restrained competition balancedgrammars and the RegDyck grammars are two newones.