Abstract
XML documents are described by a document type definition (DTD). An XML-grammar is a formal grammar that captures the syntactic features of a DTD. We investigate properties of this family of grammars. We show that an XML-language basically has a unique XML-grammar. We give two characterizations of languages generated by XML-grammars, one is set-theoretic, the other is by a kind of saturation property. We investigate decidability problems and prove that some properties that are undecidable for general context-free languages become decidable for XML-languages.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Ginsburg and M. A. Harrison. Bracketed context-free languages. J. Comput. Syst. Sci., 1:1–23, 1967.
Michael A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, Reading, Mass., 1978.
D. E. Knuth. A characterization of parenthesis languages. Inform. Control, 11:269–289, 1967.
A. J. Korenjak and J. E. Hopcroft. Simple deterministic grammars. In 7th Switching and Automata Theory, pages 36–46, 1966.
R. McNaughton. Parenthesis grammars. J. Assoc. Mach. Comput., 14:490–500, 1967.
W3C Recommendation REC-xml-19980210. Extensible Markup Language (XML) 1.0, 10 February 1998. http://www.w3.org/TR/REC-XML.
W3C Working Draft. Canonical XML Version 1.0, 15 November 1999. http://www.w3.org/TR/xml-c14n.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berstel, J., Boasson, L. (2000). XML Grammars. In: Nielsen, M., Rovan, B. (eds) Mathematical Foundations of Computer Science 2000. MFCS 2000. Lecture Notes in Computer Science, vol 1893. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44612-5_14
Download citation
DOI: https://doi.org/10.1007/3-540-44612-5_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67901-1
Online ISBN: 978-3-540-44612-5
eBook Packages: Springer Book Archive