Skip to Main content Skip to Navigation
New interface
Conference papers

Earliest Query Answering for Deterministic Nested Word Automata

Abstract : Earliest query answering (EQA) is an objective of many recent streaming algorithms for XML query answering, that aim for close to optimal memory management. In this paper, we show that EQA is infeasible even for a small fragment of Forward XPath except if P=NP. We then present an EQA algorithm for queries and schemas defined by deterministic nested word automata (dNWAs) and distinguish a large class of dNWAs for which streaming query answering is feasible in polynomial space and time.
Document type :
Conference papers
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Thursday, August 13, 2009 - 12:58:45 PM
Last modification on : Friday, February 4, 2022 - 3:15:52 AM
Long-term archiving on: : Wednesday, September 22, 2010 - 1:25:08 PM


Files produced by the author(s)


  • HAL Id : inria-00390236, version 2



Olivier Gauwin, Joachim Niehren, Sophie Tison. Earliest Query Answering for Deterministic Nested Word Automata. 17th International Symposium on Fundamentals of Computer Theory, Sep 2009, Wraclaw, Poland. pp.121-132. ⟨inria-00390236v2⟩



Record views


Files downloads