A simulation result for the auxiliary pushdown automata

摘要

We shall show that the S(n)-tape bounded and T(n)-time bounded nondeterministic auxiliary pushdown automata can be simulated by S(n)-tape bounded deterministic auxiliary pushdown automata which are S(n) · logT(n)-stack bounded whenever S(n) is tape constructible and S(n) ⩾ log n. Hence S(n)-tape bounded nondeterministic Turing machines can be simulated by S(n)-tape bounded deterministic automata which have an auxiliary pushdown storage of length S2(n).