Complexity of Earliest Query Answering with Streaming Tree Automata

Olivier Gauwin 1 Anne-Cécile Caron 1, 2 Joachim Niehren 1 Sophie Tison 1, 2
1 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
2 LIFL - Laboratoire d'Informatique Fondamentale de Lille
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.
Type de document :
Communication dans un congrès
ACM SIGPLAN Workshop on Programming Language Techniques for XML (PLAN-X), Jan 2008, San Francisco, United States. 2008
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00336169
Contributeur : Anne-Cécile Caron <>
Soumis le : lundi 3 novembre 2008 - 15:13:24
Dernière modification le : lundi 9 avril 2018 - 22:20:02
Document(s) archivé(s) le : lundi 7 juin 2010 - 20:54:39

Fichier

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

Identifiants

  • HAL Id : inria-00336169, version 1

Collections

INRIA | UNIV-LILLE3 | LIFL | MOSTRARE

Citation

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. 2008. 〈inria-00336169〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

376

Téléchargements de fichiers

149

Contact


archive-ouverte@inria.fr