A LOGICAL CHARACTERIZATION OF THE SETS OF HYPERGRAPHS DEFINED BY HYPEREDGE REPLACEMENT GRAMMARS

被引：31

作者：

COURCELLE, B ^{[1
]}

ENGELFRIET, J ^{[1
]}

机构：

[1] LEIDEN UNIV, DEPT COMP SCI, 2300 RA LEIDEN, NETHERLANDS

来源：

MATHEMATICAL SYSTEMS THEORY | 1995年 / 28卷 / 06期

关键词：

D O I：

10.1007/BF01204169

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A grammar-independent characterization of the sets of finite hypergraphs generated by Hyperedge Replacement hypergraph grammars is given. These sets are the images of the recognizable sets of finite trees under certain graph transformations definable in monadic second-order logic. Several results follow saying that a vertex-replacement set of graphs satisfying additional conditions (bounded degree, planarity, bounded tree-width, or closure under subgraphs or miners) is generable by hyperedge replacement.

引用

页码：515 / 552

页数：38

共 35 条

[1] GRAPH EXPRESSIONS AND GRAPH REWRITINGS
BAUDERON, M
COURCELLE, B
[J]. MATHEMATICAL SYSTEMS THEORY, 1987, 20 (2-3): : 83 - 127
[2] Berstel J., 1979, TRANSDUCTIONS CONTEX
[3] BRANDENBURG FJ, 1991, LECT NOTES COMPUT SC, V488, P312
[4] HANDLE-REWRITING HYPERGRAPH GRAMMARS
COURCELLE, B
ENGELFRIET, J
ROZENBERG, G
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 46 (02) : 218 - 270
[5] MONADIC 2ND-ORDER DEFINABLE GRAPH TRANSDUCTIONS - A SURVEY
COURCELLE, B
[J]. THEORETICAL COMPUTER SCIENCE, 1994, 126 (01) : 53 - 75
[6] THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .6. ON SEVERAL REPRESENTATIONS OF GRAPHS BY RELATIONAL STRUCTURES
COURCELLE, B
[J]. DISCRETE APPLIED MATHEMATICS, 1994, 54 (2-3) : 117 - 149
[7] MONADIC 2ND-ORDER EVALUATIONS ON TREE-DECOMPOSABLE GRAPHS
COURCELLE, B
MOSBAH, M
[J]. THEORETICAL COMPUTER SCIENCE, 1993, 109 (1-2) : 49 - 82
[8] THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .1. RECOGNIZABLE SETS OF FINITE GRAPHS
COURCELLE, B
[J]. INFORMATION AND COMPUTATION, 1990, 85 (01) : 12 - 75
[9] 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
[10] STRUCTURAL-PROPERTIES OF CONTEXT-FREE SETS OF GRAPHS GENERATED BY VERTEX REPLACEMENT
COURCELLE, B
[J]. INFORMATION AND COMPUTATION, 1995, 116 (02) : 275 - 293

← 1 2 3 4 →