10
$\begingroup$

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!

$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Wouldn't it be more accurate to say that the two un/decidability results prove that some non-deterministic FS transducers cannot be reduced to deterministic ones? BTW, Griffiths' proof is in Gurari's book, here -- scroll down to corollary 4.7.1. It uses Post's Correspondence Problem in a rather clever way. I suspect there is a more perspicacious proof based on TM's and the fact the a FS transducer can transform one TM snapshot into its successor, and will try to find it if I have time. $\endgroup$
    – David Lewis
    Commented Jun 13, 2012 at 4:55
  • $\begingroup$ @David: I know that Griffith’s proof is there: I specifically pointed to it with the first link in my answer and mentioned that it uses the PCP. My last sentence was addressing the OP’s surprise that the situation for FST’s is different from that for $FSM’s: I’ve not looked in detail and could be wrong, but the difference seems to be related to the way in which some FST’s fail to be reducible to deterministic ones. $\endgroup$
    – Brian M. Scott
    Commented Jun 13, 2012 at 5:01
  • $\begingroup$ Ok, sorry about the reference. But I still think your hypothesis about why things happen this way is a tautology. $\endgroup$
    – David Lewis
    Commented Jun 13, 2012 at 5:17
6
$\begingroup$

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 ;-)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .