The equivalence problem for two dpda's, one of which is a finite-turn or one-counter machine

摘要

For some non-real-time subclasses C of deterministic pushdown automata (dpda), we give a general scheme to extend a decision procedure of the equivalence to that for two dpda's, one of which is in C. Using this scheme, we prove that the equivalence problem is decidable for two dpda's, one of which is a finite-turn or one-counter machine.