Skip to Main content Skip to Navigation
New interface
Journal articles

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], Inria Saclay - Ile de France
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Luc Segoufin Connect in order to contact the contributor
Submitted on : Tuesday, December 10, 2013 - 11:22:22 AM
Last modification on : Thursday, January 20, 2022 - 4:13:06 PM
Long-term archiving on: : Friday, March 14, 2014 - 9:52:28 AM


Files produced by the author(s)


  • HAL Id : hal-00916400, version 1


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



Record views


Files downloads