| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Complexity of Earliest Query Answering with Streaming Tree Automata
Abstract : We investigate the complexity of earliest query answering for n-ary node selection queries defined by streaming tree automata (STAs). We elaborate an algorithm that selects query answers upon reception of the shortest relevant prefix of the input tree on the stream. For queries defined by deterministic STAs, our algorithm runs in polynomial time combined complexity. In the general case, we show that earliest query answering is DEXPTIME-hard (even for n=0) and thus DEXPTIME-complete.
Cited literature [21 references]
https://hal.inria.fr/inria-00336169
Contributor : Anne-Cécile Caron <>
Submitted on : Monday, November 3, 2008 - 3:13:24 PM
Last modification on : Thursday, July 25, 2019 - 8:50:06 AM
Long-term archiving on: : Monday, June 7, 2010 - 8:54:39 PM
Contributor : Anne-Cécile Caron <>
Submitted on : Monday, November 3, 2008 - 3:13:24 PM
Last modification on : Thursday, July 25, 2019 - 8:50:06 AM
Long-term archiving on: : Monday, June 7, 2010 - 8:54:39 PM
File
planx08.pdf
Files produced by the author(s)