DECIDING THE INEQUIVALENCE OF CONTEXT-FREE GRAMMARS WITH 1-LETTER TERMINAL ALPHABET IS SIGMA-2P COMPLETE

被引：14

作者：

HUYNH, DT ^{[1
]}

机构：

[1] UNIV SAARLAND,FACHBEREICH INFORMAT,D-6600 SAARBRUCKEN,FED REP GER

来源：

THEORETICAL COMPUTER SCIENCE | 1984年 / 33卷 / 2-3期

关键词：

D O I：

10.1016/0304-3975(84)90092-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The author deals with the complexity of context-free grammars with 1-letter terminal alphabet. He studies the complexity of the membership problem and the inequivalence problem. He shows that the first problem is NP-complete and the second one is SIGMA //2**p-complete with respect to log-space reduction. The second result also implies that the inequivalence problem is in PSPACE, solving an open problem.

引用

页码：305 / 326

页数：22

共 9 条

[1]

FURER M, 1980, LECT NOTES COMPUTER, V85, P234

[2]

Ginsburg S., 1966, MATH THEORY CONTEXT

[3] EQUIVALENCE, CONTAINMENT, AND COVERING PROBLEMS FOR REGULAR AND CONTEXT-FREE LANGUAGES [J].

HUNT, HB ;

ROSENKRANTZ, DJ ;

SZYMANSKI, TG .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 12 (02) :222-268

[4]

HUYNH DT, 1984, INFORM CONTROL, V57, P21

[5]

HUYNH DT, 1982, ACTA INFORMATICA, V7, P89

[6]

HUYNH DT, 1982, ELEKTR INFORM VERARB, V6, P291

[7]

RANGEL JL, 1974, 15TH ANN S SWITCH AU, P24

[8]

Stockmeyer LJ, 1973, 5TH P ANN ACM S THEO, P1, DOI DOI 10.1145/800125.804029

[9]

STOCKMEYER LJ, 1974, TR133 MIT PROJ MAC R

← 1 →