Pushdown automata with reversal-bounded counters (Q1112611)

The theme behind the paper is the effect of adding a pushdown store to R(n) reversal-bounded multicounter machines. It is shown that a 2-way nondeterministic pushdown automaton (PDA) with R(n) reversal-bounded counters can be simulated by a nondeterministic multitape Turing machine in time polynomial in \(n^{n^ 2}+R(n)\), and in time polynomial in \(n+R(n)\) if we consider 1-way PDAs only. Together with previous results this shows that for R(n) large enough the addition of a pushdown store has little effect on the computing power of R(n) reversal-bounded multicounter machines. The proof of the main result occupies most of the paper and can be divided roughly into three stages: -\ transformation of an accepting computation into a suitable norm form, -\ subsequent transformation to a linear diophantine system, -\ simulation by a nondeterministic Turing machine (simulation needs not to be step-by-step, so some time is saved). The rest of the paper contains modifications of the basic proof which allow to prove related results for some special cases, namely for 1-way machines, machines with counters allowed to make only 1 reversal each, or restricting the pushdown store alphabet to a single letter. Finally some open questions are outlined.