Skip to Main content Skip to Navigation
New interface
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Anne-Cécile Caron Connect in order to contact the contributor
Submitted on : Monday, November 3, 2008 - 3:13:24 PM
Last modification on : Friday, February 4, 2022 - 3:14:42 AM
Long-term archiving on: : Monday, June 7, 2010 - 8:54:39 PM


Files produced by the author(s)


  • HAL Id : inria-00336169, version 1



Olivier Gauwin, Anne-Cécile Caron, Joachim Niehren, Sophie Tison. Complexity of Earliest Query Answering with Streaming Tree Automata. ACM SIGPLAN Workshop on Programming Language Techniques for XML (PLAN-X), Jan 2008, San Francisco, United States. ⟨inria-00336169⟩



Record views


Files downloads