k+ 1Heads are better than k for PDAs

摘要

We prove the following conjecture stated by Harrison and Ibarra in (Inform. and Control 13 (1968), 462): There are languages accepted by (k + 1)-head 1-way deterministic pushdown automata (k+ 1)-DPDA) but not by k-head 1-way pushdown automata (k-PDA), for every k. On the assumption that their conjecture holds, Harrison and Ibarra also derived some other consequences. Now all those consequences become theorems. For example, the class of languages accepted by k-PDAs is not closed under intersection and complementation. Several other interesting consequences also follow: CFL ] ∪k DPDA(k) and FA(2) ǹ∪k DPDA(k) where DPDA(k)= [L|L is accepted by a k-DPDA and (FAQ) = [L|L is accepted by a 2-head FA s. Our proof is constructive (that is, not based on diagonalization ). Before, the “k + 1 versus k heads” problem was solved by diagonalization and translation methods for stronger machines (2-way, etc) and by traditional counting arguments for weaker machi (k-FA, k-head counter machines, etc).