3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vzn Jan 14 '15 at 20:04
  • $\begingroup$ 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. $\endgroup$ – Mathabc Jan 14 '15 at 23:32
  • $\begingroup$ 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. $\endgroup$ – vzn Jan 15 '15 at 16:33
  • $\begingroup$ No i mean an infinite language of either finite or infinite words defined by a transducer. $\endgroup$ – Mathabc Jan 15 '15 at 18:09
  • $\begingroup$ "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.... $\endgroup$ – vzn Jan 15 '15 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.