↓Skip to main content

XML Schema, Tree Logic and Sheaves Automata

XML Automata Semantics
Table of Contents

Silvano Dal Zilio, Denis Lugiez
In RTA 2003 — 14th International Conference on Rewriting Techniques and Applications, jun 2003.

conference paper

 PDF  DOI〈10.1007/3-540-44881-0_18〉

Note
#

Best Paper Award

Abstract
#

XML documents, and other forms of semi-structured data, may be roughly described as edge labeled trees; it is therefore natural to use tree automata to reason on them. This idea has already been successfully applied in the context of Document Type Definition (DTD), the simplest standard for defining XML documents validity, but additional work is needed to take into account XML Schema, a more advanced standard, for which regular tree automata are not satisfactory. In this paper, we define a tree logic that directly embeds XML Schema as a plain subset as well as a new class of automata for unranked trees, used to decide this logic, which is well-suited to the processing of XML documents and schemas.

References
#

  • An extended version of this paper appears as Research Report 4631, INRIA, November 2002.  PDF

  • An abridged version appears in Applicable Algebra in Engineering, Communication and Computing 17(5):337-377, October 2006.  Link

Citation
#


@InProceedings{DalzilioS:xmlsheaves,
   author    = {{Dal Zilio}, Silvano and Lugiez, Denis},
   title     = {{XML Schema, Tree Logic and Sheaves Automata}},
   booktitle = {RTA 2003 -- 14th International Conference on Rewriting Techniques and Applications},
   series    = {Lecture Notes in Computer Science},
   volume    = {2706},
   publisher = {Springer-Verlag},
   doi = {10.1007/3-540-44881-0_18},
   pages     = {246--263},
   month     = jun, 
   year      = 2003
}