TIME AND TAPE COMPLEXITY OF PUSHDOWN AUTOMATON LANGUAGES

被引：45

作者：

AHO, AV

HOPCROFT, JE

ULLMAN, JD

机构：

[1] Bell Telephone Laboratories, Incorporated, Murray Hill

来源：

INFORMATION AND CONTROL | 1968年 / 13卷 / 03期

关键词：

D O I：

10.1016/S0019-9958(68)91087-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An algorithm is presented which will determine whether any string w in Σ*, of length n, is contained in a language L ⊆ Σ* defined by a two-way nondeterministic pushdown automation. This algorithm requires time n3 when implemented on a random access computer. It requires n4 time and n2 tape when implemented on a multitape Turing machine. If the pushdown automaton is deterministic, the algorithm requires n2 time on a random access computer and n2 log n time on a multitape Turing machine. © 1968 Academic Press Inc.

引用

页码：186 / &

共 10 条

[1]

CHOMSKY N, 1962, 65 MASS I TECHN RES

[2]

EARLEY J, 1967, N2RECOGNIZER CONTEXT

[3] DETERMINISTIC CONTEXT FREE LANGUAGES [J].

GINSBURG, S ;

GREIBACH, S .

INFORMATION AND CONTROL, 1966, 9 (06) :620-&

[4] 2-WAY PUSHDOWN AUTOMATA [J].

GRAY, JN ;

HARRISON, MA ;

IBARRA, OH .

INFORMATION AND CONTROL, 1967, 11 (1-2) :30-&

[5] ON COMPUTATIONAL COMPLEXITY OF ALGORITHMS [J].

HARTMANIS, J ;

STEARNS, RE .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 117 (05) :285-+

[6]

HOPCROFT JE, IN PRESS

[7] ON TRANSLATION OF LANGUAGES FROM LEFT TO RIGHT [J].

KNUTH, DE .

INFORMATION AND CONTROL, 1965, 8 (06) :607-&

[8]

LEWIS PM, 1965, IEEE C RECORD SWITCH, P191

[9]

Stearns R.E., 1965, IEEE C REC SWITCHING, P179, DOI DOI 10.1109/FOCS.1965.11

[10] RECOGNITION AND PARSING OF CONTEXT-FREE LANGUAGES IN TIME N3 [J].

YOUNGER, DH .

INFORMATION AND CONTROL, 1967, 10 (02) :189-&

← 1 →