Enumeration of monadic second-order queries on trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue ACM Transactions on Computational Logic Année : 2013

Enumeration of monadic second-order queries on trees

Wojciech Kazana
  • Fonction : Auteur
  • PersonId : 948901
Luc Segoufin

Résumé

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.
Fichier principal
Vignette du fichier
enummso.pdf (188.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00916400 , version 1 (10-12-2013)

Identifiants

  • HAL Id : hal-00916400 , version 1

Citer

Wojciech Kazana, Luc Segoufin. Enumeration of monadic second-order queries on trees. ACM Transactions on Computational Logic, 2013, 14 (4). ⟨hal-00916400⟩
120 Consultations
199 Téléchargements

Partager

Gmail Facebook X LinkedIn More