Guarded Second-Order Logic, Spanning Trees, and Network Flows
Guarded Second-Order Logic, Spanning Trees, and Network Flows
复制标题
DOI：
10.2168/lmcs-6(1:4)2010
复制
发表时间：
2009-10
期刊：
影响因子：
--
通讯作者：
Achim Blumensath
中科院分区：
文献类型：
--
作者：
Achim Blumensath
根据Courcelle Monadic二阶逻辑和保护二阶逻辑的定理（其中还可以量化一组边缘）具有相同的表达能力，在所有可数$ K $ -Sparse HyperGraphs的类别上都具有相同的表达能力。在本文的第一部分中，我们将此结果扩展到任意基数的超图。在第二部分中，我们提出了一种概括，用于通过单个顶点编码顶点的方法。
According to a theorem of Courcelle monadic second-order logic and guarded second-order logic (where one can also quantify over sets of edges) have the same expressive power over the class of all countable $k$-sparse hypergraphs. In the first part of the present paper we extend this result to hypergraphs of arbitrary cardinality. In the second part, we present a generalisation dealing with methods to encode sets of vertices by single vertices.