论文标题
MSO对遗传性阶级无限元的不可证明
MSO Undecidability for Hereditary Classes of Unbounded Clique-Width
论文作者
论文摘要
塞斯对有限图的猜想指出，在所有无界的集团宽度的所有图类别上都无法确定Monadic二阶逻辑（MSO）。我们表明，要确定这一点足以证明，可以在两个绘图类别中解释无限尺寸的网格：最小的遗传阶层，无限的集团较大范围；以及在诱导子图之间的无界集团宽度的抗小节。我们探索了前一种类别的所有当前知名类别，并确定在其中确实可以解释无限尺寸的网格。
Seese's conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced subgraph relation. We explore all the currently known classes of the former category and establish that grids of unbounded size can indeed be interpreted in them.
