STRING GRAMMARS WITH DISCONNECTING OR A BASIC ROOT OF THE DIFFICULTY IN GRAPH GRAMMAR PARSING

被引：25

作者：

LANGE, KJ ^{[1
]}

WELZL, E ^{[1
]}

机构：

[1] UNIV LEIDEN,INST APPL MATH & COMP SCI,LEIDEN,NETHERLANDS

来源：

DISCRETE APPLIED MATHEMATICS | 1987年 / 16卷 / 01期

关键词：

AUTOMATA THEORY - Context Free Grammars;

D O I：

10.1016/0166-218X(87)90051-5

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The complexity of languages generated by so-called context-free string grammars with disconnecting is investigated. The result is then applied to a number of graph grammar models with finite Church Rosser property. In particular, it is shown that these graph grammars can generate NP-complete languages.

引用

页码：17 / 30

页数：14

共 19 条

[1]

BRANDENBURG FJ, 1982, LECT NOTES COMPUT SC, V145, P91, DOI 10.1007/BFb0009636

[2]

Brandenburg FJ, 1983, P WORKSHOP GRAPHTHEO, P40

[3]

BUCHER W, 1984, THEORETISCHE GRUNDLA, P41

[4] CONTEXT-FREE GRAPH GRAMMARS [J].

DELLAVIGNA, P ;

GHEZZI, C .

INFORMATION AND CONTROL, 1978, 37 (02) :207-233

[5]

EHRIG H, 1979, LECT NOTES COMP SCI, V73, P1, DOI DOI 10.1007/BFB0025714

[6] CLASS OF LINEARLY PARSABLE GRAPH GRAMMARS [J].

FRANCK, R .

ACTA INFORMATICA, 1978, 10 (02) :175-201

[7]

Garey MR., 1979, COMPUTERS INTRACTABI

[8] RESTRICTIONS, EXTENSIONS, AND VARIATIONS OF NLC GRAMMARS [J].

JANSSENS, D ;

ROZENBERG, G .

INFORMATION SCIENCES, 1980, 20 (03) :217-244

[9] ON THE STRUCTURE OF NODE-LABEL-CONTROLLED GRAPH LANGUAGES [J].

JANSSENS, D ;

ROZENBERG, G .

INFORMATION SCIENCES, 1980, 20 (03) :191-216

[10]

KAUL M, 1983, LECT NOTES COMPUT SC, V153, P206

← 1 2 →