An improvement on valiant's decision procedure for equivalence of deterministic finite turn pushdown machines

AbstractValiant has shown that the equivalence problem for deterministic finite turn pushdown machines is decidable. In this paper we show that his partial procedure for equivalence can be made constructive. To test equivalence for two given machines it suffices to construct one pda and test for emptiness. It is also shown that the time complexity of the algorithm is bounded by a double exponential function of the size of the input. The algorithm can be applied to deterministic two-tape automata and in this case the time complexity is exponential