The equivalence problem for some non-real-time deterministic pushdown automata
Esko Ukkonen · Journal of the ACM · 1982
A generalizauon of the alternate stacking procedure of Valiant for decidmg the eqmvalence of some determuusuc pushdown automata (dpda) Is introduced.To analyze the power of the generalized procedure, a subclass of dpdas, called the proper dpdas, is defined.This class properly contains the nonsingular dpdas and the real-time strict dpdas, and the corresponding class of languages properly contains the real-tune strict determmlsttc languages.The generalized procedure is shown to yield an equivalence test for proper dpdas, at least one of which ~s also a fuute-turn machine.It is also shown that the equivalence problem for proper automata is reducible to the problem of deodmg whether or not an automaton ~s proper.