The monadic second-order logic of graphs XV: On a conjecture by D. Seese

被引：0

作者：

LaBRI, CNRS, Bordeaux 1 University, 351 cours de la Libération, F-33405 Talence, France ^{[1
]}

机构：

[1] LaBRI, CNRS, Bordeaux 1 University, F-33405 Talence

来源：

J. Appl. Logic | 2006年 / 1卷 / 79-114期

关键词：

Clique-width; Comparability graph; Decidable theory; Graph; Interval graph; Line graph; Monadic second-order logic; Monadic second-order transduction;

D O I：

10.1016/j.jal.2005.08.004

中图分类号：

学科分类号：

摘要：

A conjecture by D. Seese states that if a set of graphs has a decidable monadic second-order theory, then it is the image of a set of trees under a transformation of relational structures defined by monadic second-order formulas, or equivalently, has bounded clique-width. We prove that this conjecture is true if and only if it is true for the particular cases of bipartite undirected graphs, of directed graphs, of partial orders and of comparability graphs. We also prove that it is true for line graphs, for interval graphs and for partial orders of dimension 2. Our treatment of certain countably infinite graphs uses a representation of countable linear orders by binary trees that can be constructed by monadic second-order formulas. By using a counting argument, we show the intrinsic limits of the methods used here to handle this conjecture. © 2005 Elsevier B.V. All rights reserved.

引用

页码：79 / 114

页数：35

共 38 条

[1]

Bodlaender H., A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, pp. 1-45, (1998)

[2]

Brandstadt A., Van Bang Le, Spinrad J., Graph Classes, a Survey, Monographs on Discrete Mathematics, (1999)

[3]

Courcelle B., The monadic second-order logic of graphs II: Infinite graphs of bounded width, Math. Syst. Theory, 21, pp. 187-221, (1989)

[4]

Courcelle B., The monadic second-order logic of graphs V: On closing the gap between definability and recognizability, Theoret. Comput. Sci., 80, pp. 153-202, (1991)

[5]

Courcelle B., The monadic second-order logic of graphs VI: On several representations of graphs by relational structures, Discrete Appl. Math., 54, pp. 117-149, (1994)

[6]

Corrections in Discrete Appl. Math., 63, pp. 199-200, (1995)

[7]

Courcelle B., Monadic second-order graph transductions: A survey, Theoret. Comput. Sci., 126, pp. 53-75, (1994)

[8]

Courcelle B., The monadic second-order logic of graphs VIII: Orientations, Ann. Pure Appl. Logic, 72, pp. 103-143, (1995)

[9]

Courcelle B., The monadic second-order logic of graphs X: Linear orders, Theoret. Comput. Sci., 160, pp. 87-143, (1996)

[10]

Courcelle B., The expression of graph properties and graph transformations in monadic second-order logic, Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1: Foundations, pp. 313-400, (1997)

← 1 2 3 4 →