Linear delay enumeration and monadic second-order logic Original Research Article

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 image, 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 image, where image is the number of vertices or elements. One can also output directly the image-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.