Querying Unranked Trees with Stepwise Tree Automata

Abstract : The problem of selecting nodes in unranked trees is the most basic querying problem for XML. We propose stepwise tree automata for querying unranked trees. Stepwise tree automata can express the same monadic queries as monadic Datalog and monadic second-order logic. We prove this result by reduction to the ranked case, via a new systematic correspondence that relates unranked and ranked queries.
Type de document :
Communication dans un congrès
Vincent van Oostrom. 19th International Conference on Rewriting Techniques and Applications, 2004, Aachen, Georgia. Springer, 3091, pp.105--118, 2004, LNCS
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00536529
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 13:41:40
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 17 février 2011 - 02:58:34

Fichier

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

Identifiants

  • HAL Id : inria-00536529, version 1

Collections

Citation

Julien Carme, Joachim Niehren, Marc Tommasi. Querying Unranked Trees with Stepwise Tree Automata. Vincent van Oostrom. 19th International Conference on Rewriting Techniques and Applications, 2004, Aachen, Georgia. Springer, 3091, pp.105--118, 2004, LNCS. 〈inria-00536529〉

Partager

Métriques

Consultations de la notice

360

Téléchargements de fichiers

178