Enumeration of monadic second-order queries on trees
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.
Domaines
Informatique et langage [cs.CL]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...