Linear delay enumeration and monadic second-order logic
Linear delay enumeration and monadic second-order logic
复制标题
线性延迟枚举和一元二阶逻辑
DOI：
10.1016/j.dam.2008.08.021
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
B. Courcelle
中科院分区：
文献类型：
--
作者：
B. Courcelle
由树、图或树宽至多为k的关系结构上的一元二阶公式表示的查询结果可以在两个输出之间以与下一个输出的大小成比例的延迟来枚举。这是可能的，通过使用预处理，需要时间O（n log（n）），其中n是顶点或元素的数量。人们也可以直接输出第i个元素相对于一个固定的顺序，但是，在其大小超过线性时间。这些结果推广到有界圈宽的图。我们还考虑枚举有限部分的可识别集的条款指定的参数，如大小，高度或Strahler数。
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 k, 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)), where n is the number of vertices or elements. One can also output directly the i-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.