New techniques for proving the decidability of equivalence problems. (English) Zbl 0662.68079

Automata, languages and programming, Proc. 15th Int. Colloq., Tampere/Finn. 1988, Lect. Notes Comput. Sci. 317, 162-175 (1988).
[For the entire collection see Zbl 0639.00042.]
The author discusses the recently developed techniques for proving decidability of equivalence problems. The first technique is based on the positive solution of the Ehrenfeucht conjecture. The second technique is based on synchronizability of the two devices tested for equivalence. As an application, the author proves that the equivalence problem of two synchronizable deterministic pushdown automata is decidable. The third technique is based on the decidability of the morphic equivalence for DT0L languages.
Reviewer: G.Slutzki


68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems


Zbl 0639.00042