4
$\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.

Improve this question
$\endgroup$
9
  • $\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, 2015 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, 2015 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, 2015 at 16:33
  • $\begingroup$ No i mean an infinite language of either finite or infinite words defined by a transducer. $\endgroup$
    – Mathabc
    Jan 15, 2015 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, 2015 at 19:31

1 Answer 1

Reset to default
4
$\begingroup$

It is mentioned in Muscholl and Puppis's survey on transducers (Theorem 3) that single-valuedness of finite transducers is NL-complete. Hence, equivalence of deterministic finite transducers is in NL.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.