Why is it undecidable whether two finite-state transducers are equivalent?

Question

According to the Wikipedia page on finite-state transducers, it is undecidable whether two finite-state transducers are equivalent. I find this result striking, since it is decidable whether two finite-state automata are equivalent to one another.

Unfortunately, Wikipedia doesn't provide any citations that provide a justification for this result. Does anyone know of a proof of this result? Alternatively, if the article is incorrect, does someone know an algorithm that could be used to show equivalence?

Thanks!

Answer 1

This web page from the on-line version of An Introduction to the Theory of Computation, by Eitan Gurari, shows that the equivalence problem for finite-state transducers is undecidable by reduction from the Post Correspondence Problem, whose undecidability is shown on the same page; he cites

Griffiths, T. (1968). "The unsolvability of the equivalence problem for $\Lambda$-free nondeterministic generalized machines," Journal of the Association for Computing Machinery 15, 409-413,

for the result.

Gurari himself proved that the equivalence problem is decidable for deterministic transducers:

The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM J. Comput. , 11(3):448–452, 1982.

Apparently the difficulty lies in the fact that some non-deterministic finite-state transducers cannot be reduced to deterministic ones.

Answer 2

To complement on Brian's answer, you might want to look at The equivalence problem of multitape finite automata, where the authors give an algorithm for deciding whether two deterministic transducers are equivalent. The key is that it is decidable if two automata are equivalent with regard to multiplicities (i.e. how many times the word is accepted).

This is very closely related to probabilistic automata, of which the equivalence algorithm was given in A polynomial-time algorithm for the equivalence of probabilistic automata. In this setting the question is whether two automata accept the word with the same probability.

You can generalize that for some weighted automatons, without loosing decidability (see here for nice slides with examples). Thus, you could transform deterministic (multitape) automatons into weighted version such that word is accepted if and only if it has (in some semiring) weight 1 (one), and afterwards just use the previous algorithm. However, please note that this is rather fragile result, even adding $\varepsilon$-edges would make this undecidable.

Hope this helps ;-)