Typing and querying XML documents: some complexity bounds Luc Segoufin   View Paper (PDF)   Return to XML Abstract We study the complexity bound of validating XML documents, viewed as labeled unranked ordered trees, against various typing systems like DTDs, XML schemas, tree automata... We also consider query evaluation complexities for various fragments of XPath. For both problems, validation and query evaluation, we consider data and combined complexity bounds. BIBTEX @inproceedings       {DBLP:conf/pods/Segoufin03,   author    = {Luc Segoufin},    booktitle = {PODS},    title     = {Typing and querying XML documents: some complexity bounds.},    pages     = {167-178},    year      = {2003},    url       = {db/conf/pods/pods2003.html#Segoufin03},    ee        = {http://doi.acm.org/10.1145/773153.773170},    crossref  = {conf/pods/2003},    bibsource = {DBLP, http://dblp.uni-trier.de}  } ©2004 Association for Computing Machinery