HANDLE-REWRITING HYPERGRAPH GRAMMARS

被引：223

作者：

COURCELLE, B ^{[1
]}

ENGELFRIET, J ^{[1
]}

ROZENBERG, G ^{[1
]}

机构：

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

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1993年 / 46卷 / 02期

关键词：

D O I：

10.1016/0022-0000(93)90004-G

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We introduce the handle-rewriting hypergraph grammars (HH grammars), based on the replacement of handles, i.e., of subhypergraphs consisting of one hyperedge together with its incident vertices. This extends hyperedge replacement, where only the hyperedge is replaced. A HH grammar is separated (an S-HH grammar) if nonterminal handles do not overlap. The S-HH grammars are context-free, and the sets they generate can be characterized as the least solutions of certain systems of equations. They generate the same sets of graphs as the NLC-like vertex-rewriting C-edNCE graph grammars that are also context-free. © 1993 Academic Press, Inc.

引用

页码：218 / 270

页数：53

共 40 条

[1] GRAPH EXPRESSIONS AND GRAPH REWRITINGS [J].

BAUDERON, M ;

COURCELLE, B .

MATHEMATICAL SYSTEMS THEORY, 1987, 20 (2-3) :83-127

[2]

BRANDENBURG FJ, 1987, LECT NOTES COMPUT SC, V294, P227

[3]

BRANDENBURG FJ, 1987, LECT NOTES COMPUT SC, V291, P99

[4] COMPLEMENT REDUCIBLE GRAPHS [J].

CORNEIL, DG ;

LERCHS, H ;

BURLINGHAM, LS .

DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) :163-174

[5]

COURCELLE B, 1987, LECT NOTES COMPUT SC, V291, P112

[6]

COURCELLE B, 1989, LECT NOTES COMPUT SC, V344, P30

[7] THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .1. RECOGNIZABLE SETS OF FINITE GRAPHS [J].

COURCELLE, B .

INFORMATION AND COMPUTATION, 1990, 85 (01) :12-75

[8] 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

[9] THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .3. TREE-DECOMPOSITIONS, MINORS AND COMPLEXITY ISSUES [J].

COURCELLE, B .

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1992, 26 (03) :257-286

[10] 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

← 1 2 3 4 →