A Note on the P-completeness of Deterministic One-way Stack Language

被引：0

作者：

Lange, Klaus-Joern ^{[1
]}

机构：

[1] Univ Tubingen, WSI, D-72074 Tubingen, Germany

来源：

JOURNAL OF UNIVERSAL COMPUTER SCIENCE | 2010年 / 16卷 / 05期

关键词：

Automata; Grammars; Complexity classes; Completeness; AUTOMATA;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The membership problems of both stack automata and nonerasing stack automata are shown to be complete for polynomial time.

引用

页码：795 / 799

页数：5

共 19 条

[1] INDEXED GRAMMARS - AN EXTENSION OF CONTEXT-FREE GRAMMARS [J].

AHO, AV .

JOURNAL OF THE ACM, 1968, 15 (04) :647-&

[2] NESTED STACK AUTOMATA [J].

AHO, AV .

JOURNAL OF THE ACM, 1969, 16 (03) :383-&

[3] 2-WAY NESTED STACK AUTOMATA ARE EQUIVALENT TO 2-WAY STACK AUTOMATA [J].

BEERI, C .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1975, 10 (03) :317-339

[4] STACK-MACHINES AND CLASSES OF NON-NESTED MACRO LANGUAGES [J].

ENGELFRIET, J ;

SCHMIDT, EM ;

VANLEEUWEN, J .

JOURNAL OF THE ACM, 1980, 27 (01) :96-117

[5] 1-WAY STACK AUTOMATA [J].

GINSBURG, S ;

GREIBACH, SA ;

HARRISON, MA .

JOURNAL OF THE ACM, 1967, 14 (02) :389-&

[6] STACK AUTOMATA AND COMPILING [J].

GINSBURG, S ;

GREIBACH, SA ;

HARRISON, MA .

JOURNAL OF THE ACM, 1967, 14 (01) :172-&

[7]

Goldschlager L. M., 1977, SIGACT News, V9, P25, DOI 10.1145/1008354.1008356

[8]

Greibach Sheila A., 1969, J. Comput. Syst. Sci., V3, P196, DOI [10.1016/S0022-0000(69)80012-7, DOI 10.1016/S0022-0000(69)80012-7]

[9]

HARRISON M, 1978, INTRO FORMAL LANGUAG

[10]

HOLZER M, 1993, LECT NOTES COMPUTER, V710, P299

← 1 2 →