The decidability of equivalence for deterministic finite-turn pushdown automata
Leslie Gabriel Valiant · 1974
A deterministic pushdown automaton (dpda) is described as finite-turn if there is a bound on the number of times the direction of the stack movement can change in the set of all derivations from the starting configuration. The purpose of this paper is to show that there exists a procedure for deciding whether two such finite-turn machines recognize the same language. By virtue of a direct correspondence between a restricted class of one-turn dpda and deterministic two-tape acceptors (Valiant (1973)), our proof also provides a solution to the equivalence problem for the latter, alternative to that of Bird (1973). Since some of the ideas we introduce are not related exclusively to the finite-turn property, or even pushdown machines, it is hoped that our methods can be adapted for constructing equivalence tests for other classes of deterministic automata.