In [2] Ibarra introduced a restricted version of one-way multihead pushdown automaton (PDA), called a simple one-way multihead PDA, and showed that such machines recognize only languages with semilinear property. The main result of this paper is that for each k 1, simple (sensing) one-way (k + 1)-head PDA's are more powerful than simple (sensing) one-way k-head PDA's. This paper also investigates closure properties for simple (sensing) one-way multihead PDA's

This paper establishes a relationship among the accepting powers of deterministic, nondeterministic, and alternating one-way auxiliary pushdown automata, for any tape bound below n. Some other related results are also presented.