Bounded Delay and Concurrency for Earliest Query Answering

Abstract : Earliest query answering is needed for streaming XML processing with optimal memory management. We study the feasibility of earliest query answering for node selection queries. Tractable queries are distinguished by a bounded number of concurrently alive answer candidates at every time point, and a bounded delay for node selection. We show that both properties are decidable in polynomial time for queries defined by deterministic automata for unranked trees. Our results are obtained by reduction to the bounded valuedness problem for recognizable relations between unranked trees.
Type de document :
Communication dans un congrès
Adrian Horia Dediu and Armand Mihai Ionescu and Carlos Martin-Vide. 3rd International Conference on Language and Automata Theory and Applications, Apr 2009, Tarragona, Spain. Springer, 5457, pp.350-361, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-00982-2〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00348463
Contributeur : Olivier Gauwin <>
Soumis le : vendredi 19 décembre 2008 - 10:39:41
Dernière modification le : jeudi 30 août 2018 - 13:58:01
Document(s) archivé(s) le : mardi 8 juin 2010 - 16:44:18

Identifiants

Collections

Citation

Olivier Gauwin, Joachim Niehren, Sophie Tison. Bounded Delay and Concurrency for Earliest Query Answering. Adrian Horia Dediu and Armand Mihai Ionescu and Carlos Martin-Vide. 3rd International Conference on Language and Automata Theory and Applications, Apr 2009, Tarragona, Spain. Springer, 5457, pp.350-361, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-00982-2〉. 〈inria-00348463〉

Partager

Métriques

Consultations de la notice

350

Téléchargements de fichiers

220