Relationships between pushdown automata with counters and complexity classes

In this paper a machine model is defined whose access to the storage cells is controlled by means of address registers. It is shown that every set acceptable by such a machine within time boundcn ^p,p , is accepted by a deterministic 2p-head two-way pushdown automaton which has additional counters of length log₂ n. On the other hand every set acceptable by a deterministicp-head two-way pushdown automaton can be accepted by this machine model within time boundcn ^plog₂ n. A result similar to one of the main theorems (theorem 4) of this paper has been proved also by S. A. Cook. Both proofs are based on the same idea but have been found independently.