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.
Type de document :
Communication dans un congrès
17th International Symposium on Fundamentals of Computer Theory, Sep 2009, Wraclaw, Poland. SV, 5699, pp.121-132, 2009, LNCS
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00390236
Contributeur : Joachim Niehren <>
Soumis le : jeudi 13 août 2009 - 12:58:45
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 13:25:08

Fichier

0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00390236, version 2

Collections

Citation

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. SV, 5699, pp.121-132, 2009, LNCS. 〈inria-00390236v2〉

Partager

Métriques

Consultations de la notice

289

Téléchargements de fichiers

138