Relationships between pushdown automata with counters and complexity classes |
| |
Authors: | Burkhard Monien |
| |
Affiliation: | (1) Institut für Informatik, Universität Hamburg, Hamburg, West Germany |
| |
Abstract: | 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 boundcnp,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 boundcnplog2n.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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|