Linear delay enumeration and monadic second-order logic

The results of a query expressed by a monadic second-order formula on a tree, on a graph or on a relational structure of tree-width at most kk, can be enumerated with a delay between two outputs proportional to the size of the next output. This is possible by using a preprocessing that takes time O(n⋅log(n))O(n⋅log(n)), where nn is the number of vertices or elements. One can also output directly the ii-th element with respect to a fixed ordering, however, in more than linear time in its size. These results extend to graphs of bounded clique-width. We also consider the enumeration of finite parts of recognizable sets of terms specified by parameters such as size, height or Strahler number.