Relationships between pushdown automata with counters and complexity classes

Research paper by Burkhard Monien

Indexed on: 01 Sep '75Published on: 01 Sep '75Published in: Theory of Computing Systems


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 boundc⋅np,p ∈ ℕ, is accepted by a deterministic 2p-head two-way pushdown automaton which has additional counters of length log2n. On the other hand every set acceptable by a deterministicp-head two-way pushdown automaton can be accepted by this machine model within time boundc⋅np⋅log2n.