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 条

[1] ARNBORG S, 1988, LECT NOTES COMPUT SC, V317, P38
[2] GRAPH EXPRESSIONS AND GRAPH REWRITINGS
BAUDERON, M
COURCELLE, B
[J]. 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
COURCELLE, B
[J]. THEORETICAL COMPUTER SCIENCE, 1986, 42 (01) : 1 - 122
[8] AN AXIOMATIC DEFINITION OF CONTEXT-FREE REWRITING AND ITS APPLICATION TO NLC GRAPH-GRAMMARS
COURCELLE, B
[J]. 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

← 1 2 3 4 →