On the computational power of some machines with pushdown-like storage

The computational power of 2-way pushdown automata with m additional counters (called mC-PDA) is investigated. It is shown that any multi-tape Turingmachine (with a two-way input tape) which accepts within time T(n), where n is the input length, can be simulated by a 3C-PDA whose counters are bounded by T(n) and that any such Turing machine can also be simulated by a 2C-PDA whose counters are bounded by T(n)2. A number of other results relating the power of 1C-PDA and that of other types of machines are also obtained.