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

被引：845
作者：
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
    JOHNSON, DS
    [J]. 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
    MEZEI, J
    WRIGHT, JB
    [J]. 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