A note on non-singular deterministic pushdown automata

The non-singular deterministic pushdown automata were first defined by Valiant as an example of a class of machines with a decidable equivalence problem [3]. No algorithm currently exist for deciding whether or not a deterministic pushdown automation is non-singular, so the applicability of Valiant's equivalence decision procedure cannot be readily (if ever) determined. In this paper, it is shown that the equivalence problem for non-singular automata is reducible to the problem of deciding whether or not a deterministic pushdown automaton is non-singular.