The equivalence problem for single-valued two-way transducers (on NPDT0L languages) is decidable. (English) Zbl 0632.68077

The equivalence problem for deterministic two-way transducers was a longstanding problem finally shown decidable by E. M. Gurari. We show a generalization of this result, namely that it is decidable whether two single-valued two-way transducers are equivalent on an NPDT0L language. We obtain this result by showing that it is even decidable whether a two- way transducer is single-valued on an NPDT0L language.
Our solution is based on the compactness property of the systems of equations over a finitely generated free monoid shown recently by J. Lawrence and M. Albert and also by V. S. Guba. This was a longstanding open problem known as the Ehrenfeucht conjecture. Our approach also shows that for one-way transducers their single-valuedness on a given HDT0L language can be tested, and thus the equivalence of two single-valued one-way transducers on an HDT0L language is decidable, too.
Our results imply the decidability of the HD0L and HDT0L sequence equivalence problems, also longstanding open problems solved recently by K. Ruohonen and the authors, respectively.


68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI