Formal Properties of XML Grammars and Languages

Simple item page
dc.creatorBerstel, Jean
dc.creatorBoasson, Luc
dc.date2000-11-07
dc.date.accessioned2026-07-07T03:16:42Z
dc.date.available2026-07-07T03:16:42Z
dc.descriptionXML 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 every 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. We also characterize those XML-grammars that generate regular XML-languages.
dc.description24 pages
dc.identifierhttps://arxiv.org/abs/cs/0011011
dc.identifierhttp://arxiv.org/abs/cs/0011011
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30451
dc.subjectDiscrete Mathematics
dc.subjectComputation and Language
dc.subjectF.4.2;F.4.3;D.3.1
dc.titleFormal Properties of XML Grammars and Languages
dc.typetext

Files

Collections

arXiv