Enumeration of monadic second-order queries on trees

Wojciech Kazana 1 Luc Segoufin 1
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We consider the enumeration problem of monadic second-order (MSO) queries with first-order free variables over trees. Bagan showed ub 2006 that this problem is in CDlin. An enumeration problem belongs to CDlin if for an input structure of size n it can be solved by: * an O(n) precomputation phase building an index structure, * followed by a phase enumerating the answers with no repetition and a constant delay between two consecutive outputs. In this article we give a different proof of this result based on the deterministic factorization forest decomposition theorem of Colcombet.
Type de document :
Article dans une revue
ACM Transactions on Computational Logic, Association for Computing Machinery, 2013, 14 (4)
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00916400
Contributeur : Luc Segoufin <>
Soumis le : mardi 10 décembre 2013 - 11:22:22
Dernière modification le : mardi 13 mars 2018 - 14:24:05
Document(s) archivé(s) le : vendredi 14 mars 2014 - 09:52:28

Fichier

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

Identifiants

  • HAL Id : hal-00916400, version 1

Collections

Citation

Wojciech Kazana, Luc Segoufin. Enumeration of monadic second-order queries on trees. ACM Transactions on Computational Logic, Association for Computing Machinery, 2013, 14 (4). 〈hal-00916400〉

Partager

Métriques

Consultations de la notice

178

Téléchargements de fichiers

106