The Power of Counting Logics on Restricted Classes of Finite Structures
The Power of Counting Logics on Restricted Classes of Finite Structures
复制标题
有限结构受限类的计数逻辑的威力
DOI：
10.1007/978-3-540-74915-8_10
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
David Richerby
中科院分区：
文献类型：
--
作者：
A. Dawar;David Richerby
虽然蔡、富勒和Immerman已经证明了带计数的定点逻辑（IFP+C）并不能表达有限结构的所有多项式时间性质，但有许多结果证明了该逻辑确实在特定的结构类上捕获了P。Grohe和Marino证明了IFP+C在有界树宽的结构类上捕获P，Grohe证明了IFP+C在平面图上捕获P。我们表明，这些结果中的第一个是最佳的在两个意义上。我们证明了在图的树宽由一个非常数限定的图类上，IFP+C不能捕获P。我们还证明了在图的局部树宽由一个非常数函数限定的图类上，IFP+C不能捕获P。这两个结果都是通过分析Cai-Furer-Immerman（CFI）构造图的树宽得到的，警察和强盗的游戏;我们提出了一些其他的影响，这种分析。然后，我们证明了这种方法的局限性，显示CFI建设不能用来表明IFP+C未能捕获P适当的小封闭类。
Although Cai, Furer and Immerman have shown that fixed-point logic with counting (IFP+C) does not express all polynomial-time properties of finite structures, there have been a number of results demonstrating that the logic does capture P on specific classes of structures. Grohe and Marino showed that IFP+C captures P on classes of structures of bounded treewidth, and Grohe showed that IFP+C captures P on planar graphs. We show that the first of these results is optimal in two senses. We show that on the class of graphs defined by a non-constant bound on the tree-width of the graph, IFP+C fails to capture P. We also show that on the class of graphs whose local tree-width is bounded by a non-constant function, IFP+C fails to capture P. Both these results are obtained by an analysis of the Cai---Furer---Immerman (CFI) construction in terms of the treewidth of graphs, and cops and robber games; we present some other implications of this analysis. We then demonstrate the limits of this method by showing that the CFI construction cannot be used to show that IFP+C fails to capture P on proper minor-closed classes.
DOI：
10.1109/lics.2006.13
发表时间：
2006
期刊：
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)
影响因子：
--
作者：
Anuj Dawar;Martin Grohe;Stephan Kreutzer;Nicole Schweikardt
通讯作者：
Nicole Schweikardt