THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .1. RECOGNIZABLE SETS OF FINITE GRAPHS

被引：862
作者：
COURCELLE, B
机构：
[1] Bordeaux I University, Laboratoire d'Informatique, Unité de Recherche Associée au CNRS no 726. 351, 33405 Talence, Cours de la Libération
来源：
INFORMATION AND COMPUTATION | 1990年 / 85卷 / 01期
关键词：
D O I：
10.1016/0890-5401(90)90043-H
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The notion of a recognizable set of finite graphs is introduced. Every set of finite graphs, that is definable in monadic second-order logic is recognizable, but not vice versa. The monadic second-order theory of a context-free set of graphs is decidable. © 1990.
引用
收藏
页码：12 / 75
页数：64
相关论文
共 31 条
[1]  
ARNBORG S, 1988, LECT NOTES COMPUT SC, V317, P38
[2]   GRAPH EXPRESSIONS AND GRAPH REWRITINGS [J].
BAUDERON, M ;
COURCELLE, B .
MATHEMATICAL SYSTEMS THEORY, 1987, 20 (2-3) :83-127
[3]  
BODLAENDER HL, 1988, LECT NOTES COMPUT SC, V317, P105
[4]  
COURCELLE B, 1987, LECT NOTES COMPUT SC, V291, P112
[5]  
COURCELLE B, 1989, LECT NOTES COMPUT SC, V344, P30
[6]  
COURCELLE B, 1989, MATH SYST THEORY, V21, P187
[7]   FUNDAMENTAL-STUDIES - EQUIVALENCES AND TRANSFORMATIONS OF REGULAR SYSTEMS - APPLICATIONS TO RECURSIVE PROGRAM SCHEMES AND GRAMMARS [J].
COURCELLE, B .
THEORETICAL COMPUTER SCIENCE, 1986, 42 (01) :1-122
[8]   AN AXIOMATIC DEFINITION OF CONTEXT-FREE REWRITING AND ITS APPLICATION TO NLC GRAPH-GRAMMARS [J].
COURCELLE, B .
THEORETICAL COMPUTER SCIENCE, 1987, 55 (2-3) :141-181
[9]  
COURCELLE B, 1987, LECT NOTES COMPUT SC, V291, P133
[10]  
COURCELLE B, 1988, 8830 RES REP
1234