The modular decomposition of countable graphs. Definition and construction in monadic second-order logic

被引：25
作者：
Courcelle, Bruno [1 ,2 ]
Delhomme, Christian [3 ]
机构：
[1] Univ Bordeaux 1, 351 Cours Liberat, F-33405 Talence, France
[2] Inst Univ France, LaBRI, CNRS, F-33405 Talence, France
[3] Univ La Reunion, ERMIT, F-97715 St Denis 9, Reunion, France
来源：
THEORETICAL COMPUTER SCIENCE | 2008年 / 394卷 / 1-2期
关键词：
modular decomposition; tree; linear order; monadic second-order logic; monadic second-order transduction;
D O I：
10.1016/j.tcs.2007.10.046
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We consider the notion of modular decomposition for countable graphs. The modular decomposition of a graph given with an enumeration of its set of vertices can be defined by formulas of monadic second-order logic. Another result is the definition of a representation of modular decompositions by low degree relational structures. Such relational structures can also be defined in the considered graph by monadic second-order formulas. (C) 2007 Elsevier B.V. All fights reserved.
引用
收藏
页码：1 / 38
页数：38
相关论文
共 44 条
[1]  
[Anonymous], 1990, GRAPH DECOMPOSITIONS
[2]  
Barthelmann K, 1998, LECT NOTES COMPUT SC, V1450, P543, DOI 10.1007/BFb0055804
[3]  
Benedikt M, 2005, LECT NOTES COMPUT SC, V3634, P276, DOI 10.1007/11538363_20
[4]   Finite presentations of infinite structures:: Automata and interpretations [J].
Blumensath, A ;
Grädel, E .
THEORY OF COMPUTING SYSTEMS, 2004, 37 (06) :641-674
[5]  
Carayol A, 2003, LECT NOTES COMPUT SC, V2914, P112
[6]   ON THE REGULAR STRUCTURE OF PREFIX REWRITING [J].
CAUCAL, D .
THEORETICAL COMPUTER SCIENCE, 1992, 106 (01) :61-86
[7]  
Colcombet Thomas, 2004, THESIS U RENNES 1
[8]   ON BETTER QUASI-ORDERING COUNTABLE TREES [J].
COROMINAS, E .
DISCRETE MATHEMATICS, 1985, 53 (MAR) :35-53
[9]  
Courcelle B, 2005, LECT NOTES COMPUT SC, V3634, P325, DOI 10.1007/11538363_23
[10]   MONADIC 2ND-ORDER DEFINABLE GRAPH TRANSDUCTIONS - A SURVEY [J].
COURCELLE, B .
THEORETICAL COMPUTER SCIENCE, 1994, 126 (01) :53-75
12345