Typing and querying XML documents: some complexity bounds
paper (PODS 2003)
Luc Segoufin
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\ldots 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.
Back to Luc Segoufin's home page.