Where First-Order and Monadic Second-Order Logic Coincide
Where First-Order and Monadic Second-Order Logic Coincide
复制标题
一阶逻辑和一元二阶逻辑重合的地方
DOI：
10.1145/2946799
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Till Tantau
中科院分区：
文献类型：
--
作者：
Michael Elberfeld;Martin Grohe;Till Tantau
研究了一阶逻辑和一元二阶逻辑在哪些图类上具有相同的表达能力。我们表明，对于每个类的图是封闭的下采取子图，FO和MSO有相同的表达能力的类，当且仅当，它有界树深度。树深度是一个图不变量，它以类似于树宽度测量图与树的相似性的方式测量图与星星的相似性。对于类只是关闭下诱导子图，我们证明了一个类似的结果，保护二阶逻辑（GSO），MSO的变体，不仅允许量化的顶点集，但也超过边缘集。在我们的证明中的一个关键工具是Feferman-Vaught型定理，它是建设性的，并且仍然适用于无界分区。
We study on which classes of graphs first-order logic (FO) and monadic second-order logic (MSO) have the same expressive power. We show that for each class of graphs that is closed under taking subgraphs, FO and MSO have the same expressive power on the class if, and only if, it has bounded tree depth. Tree depth is a graph invariant that measures the similarity of a graph to a star in a similar way that tree width measures the similarity of a graph to a tree. For classes just closed under taking induced subgraphs, we show an analogous result for guarded second-order logic (GSO), the variant of MSO that not only allows quantification over vertex sets but also over edge sets. A key tool in our proof is a Feferman-Vaught-type theorem that is constructive and still works for unbounded partitions.