AN AXIOMATIC DEFINITION OF CONTEXT-FREE REWRITING AND ITS APPLICATION TO NLC GRAPH-GRAMMARS

被引：97

作者：

COURCELLE, B

机构：

[1] CNRS, Talence, Fr, CNRS, Talence, Fr

来源：

THEORETICAL COMPUTER SCIENCE | 1987年 / 55卷 / 2-3期

关键词：

D O I：

10.1016/0304-3975(87)90102-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An abstract notion of context-free grammar is introduced. It deals with abstract objects that can be words, trees, graphs or other combinatorial objects. It is applied to NLC graph grammars introduced by G. Rozenberg and D. Janssens. The monadic second-order theory of a context-free NLC set of graphs is decidable.

引用

页码：141 / 181

页数：41

共 19 条

[1] BAUDERON M, IN PRESS MATH SYSTEM
[2] 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
[3] COURCELLE B, 1988, IN PRESS 3RD P INT W
[4] COURCELLE B, 1986, 8634 BORD 1 U RES RE
[5] EHRIG H, 1979, LECT NOTES COMP SCI, V73, P1, DOI DOI 10.1007/BFB0025714
[6] IO AND OI.I
ENGELFRIET, J
SCHMIDT, EM
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1977, 15 (03) : 328 - 353
[7] IO AND OI .2.
ENGELFRIET, J
SCHMIDT, EM
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1978, 16 (01) : 67 - 99
[8] Gecseg F., 1984, TREE AUTOMATA
[9] 2 FAMILIES OF LANGUAGES RELATED TO ALGOL
GINSBURG, S
RICE, HG
[J]. JOURNAL OF THE ACM, 1962, 9 (03) : 350 - +
[10] HABEL A, 1987, LECT NOTES COMPUT SC, V247, P207

← 1 2 →