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 条
[21]  
J. R. Buchi, 1960, Z MATH LOG GRUNDL MA, V6, P66
[22]   THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].
JOHNSON, DS .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1985, 6 (03) :434-451
[23]  
LAUTEMANN C, 1988, LECT NOTES COMPUT SC, V317, P362
[24]  
LENGAUER T, 1988, LECT NOTES COMPUT SC, V317, P379
[25]   ALGEBRAIC AUTOMATA AND CONTEXT-FREE SETS [J].
MEZEI, J ;
WRIGHT, JB .
INFORMATION AND CONTROL, 1967, 11 (1-2) :3-&
[26]  
Rozenberg Grzegorz, 1980, MATH THEORY L SYSTEM
[27]  
SEESE D, 1975, WISS Z HUMBOLD U Z R, V24, P772
[28]  
SEESE D, IN PRESS ANN PURE AP
[29]  
THOMAS W, IN PRESS HDB THEORET
[30]  
Trakhtenbrot B.A., 1950, DOKL AKAD NAUK SSSR+, V70, P569
1234