Date Added: Jan 2011
The authors investigate the problem of querying (regular) sets of XML documents represented with tree automata and the authors consider n-ary tree automata queries whose expressive power captures MSO on trees. Because finite automata can represent infinite sets of documents, they propose the notions of universal and existential query answers, answers that are present resp. in all and some documents. The authors study complexity of query answering and show that computing existential query answers is in PTIME if people assume the arity of the query to be a fixed parameter. On the other hand, computing universal query answers is EXPTIME-complete, but they show that it is in PTIME if people assume that the query is fixed (data complexity).