Decidability of DPDA equivalence
A proof of decidability of equivalence between deterministic pushdown automata is presented using a mixture of methods developed in concurrency and language theory. The technique appeals to a tableau proof system for equivalence of configurations of strict deterministic grammars. (C) 2001 Elsevier Science B.V. All rights reserved.
decidability dpda language equivalence bisimulation fundamental study