# Equivalence of deterministic finite transducers over finite/infinite words

Equivalence of deterministic finite transducers - a special case of single-valued finite transducers - is decidable because it is decidable whether a transducer is single-valued. Note that two deterministic finite transducers $T_1$, $T_2$ are equivalent iff $T_1 \cup T_2$ is single-valued and their domains are equivalent which reduces to a DFA equivalence check on $T_1$, $T_2$ without output.

Can you point to a reference of an efficient algorithm to decide equivalence of deterministic finite transducers over finite words?

I am also interested in a decision procedure for infinite words assuming that all states are final. The latter transducer variant is also known as generalized sequential machine (GSM). Equivalence is also decidable for GSMs.

• iirc determining equivalence of transducers with $\epsilon$-transitions is undecidable. also transducers are not exactly the same as 2DFAs because the latter has inputs only & former has inputs/outputs although there is a correspondence.
– vzn
Jan 14, 2015 at 20:04
• I was referring to deterministic 2-tape DFA, i.e. there are no $\epsilon$ transitions or they can be eliminated without introducing non-determinism. But indeed, you are right that a deterministic 2-tape DFA does not correspond to a deterministic transducer. I am going to change the question. Jan 14, 2015 at 23:32
• what do you mean "finite words"? a finite set of words, ie language? one can just run the transducers over those words to determine if they give equivalent outputs for equivalent inputs. then they are equivalent over a set of finite words.
– vzn
Jan 15, 2015 at 16:33
• No i mean an infinite language of either finite or infinite words defined by a transducer. Jan 15, 2015 at 18:09
• "assuming all states are final"? "known as a gsm"? huh? that does not sound like the defn of a gsm (eg re intro to languages/ automata theory, hopcroft/ ullman). think there is a fairly straightfwd algorithm for equivalence of non-$\epsilon$ transition automata of traversing each graph in a synchronized fashion.... dont know if it has been described/ published anywhere....
– vzn
Jan 15, 2015 at 19:31