On the computational power of pushdown a
β
A.V. Aho; J.D. Ullman; J.E. Hopcroft
π
Article
π
1970
π
Elsevier Science
π
English
β 361 KB
We present a relation between the sets accepted by two-way pushdown automata and certain tape complexity classes of off-line Turing machines. Specifically, let L be a language accepted by a nondeterministic off-line Turing machine T. Let T have a t-symbol storage-tape alphabet. If for all but a fini