<p>It is mentioned in <a href="https://drops.dagstuhl.de/opus/volltexte/2019/10241/" rel="nofollow noreferrer">Muscholl and Puppis's survey on transducers</a> (Theorem 3) that single-valuedness of finite transducers is NL-complete. Hence, equivalence of <em>deterministic</em> finite transducers is in NL.</p>

CC BY-SA 4.0
2022-11-03T01:36:24.927Z
2022-11-03T01:36:24.927Z
Lê Thành Dũng 'Tito' Nguyễn
<p>Equivalence of deterministic finite transducers - a special case of single-valued finite transducers - is decidable because it is <a href="http://www.infres.enst.fr/~jsaka/PUB/Files/DBVT.pdf" rel="nofollow">decidable whether a transducer is single-valued</a>. 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.</p>

<p>Can you point to a reference of an efficient algorithm to decide equivalence of <strong>deterministic</strong> finite transducers over finite words?</p>

<p>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 <a href="http://www.sciencedirect.com/science/article/pii/002001908690058X" rel="nofollow">decidable for GSMs</a>.</p>

CC BY-SA 3.0
2015-01-14T20:04:12.783Z
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
CC BY-SA 3.0
2015-01-14T23:32:03.437Z
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.
Mathabc
CC BY-SA 3.0
2015-01-15T16:33:21.980Z
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
CC BY-SA 3.0
2015-01-15T18:09:42.563Z
No i mean an infinite language of either finite or infinite words defined by a transducer.
Mathabc
CC BY-SA 3.0
2015-01-15T19:31:15.593Z
"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
CC BY-SA 3.0
2015-01-15T22:53:39.390Z
With "all states are final" I mean that there is no special acceptance condition like Büchi or Müller. A GSM is a Mealy machine where the output on each transition is a word and not just a symbol. It would be great if you could sketch the algorithm to decide equivalence if it is so simple.
Mathabc
CC BY-SA 3.0
2015-01-16T00:17:58.717Z
what is your ref that says it is decidable? think it might be for deterministic and/or non-$\epsilon$ transition machines but not sure. see [Why is it undecidable whether two finite-state transducers are equivalent?](http://math.stackexchange.com/questions/157585/why-is-it-undecidable-whether-two-finite-state-transducers-are-equivalent) math.se
vzn
CC BY-SA 3.0
2015-01-16T00:45:28.147Z
I updated my question accordingly. I am aware that equivalence is undecidable for general non-deterministic transducers but it is decidable for single-valued ones (in general for finite-valued ones). However, I am concerned with the special case of deterministic transducers over finite resp. infinite words which are less expressive than single-valued transducers.
Mathabc
CC BY-SA 3.0
2015-01-16T03:42:22.537Z
see the math.se question for refs on both the decidable (Griffiths 1968) and undecidable case (Gurari 1982). do not understand some of your terms such as "finite resp infinite words" or "single/finite valued transducers" etc, suggest you use std terms from elsewhere or carefully define terms. admittedly at times there is not so much stdized terminology in this area.
vzn
<ds.algorithms><reference-request><graph-algorithms><automata-theory>
Equivalence of deterministic finite transducers over finite/infinite words
Mathabc
# Equivalence of deterministic finite transducers over finite/infinite words

(Asked by: username_0 on 2015-01-13)

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](http://www.infres.enst.fr/~jsaka/PUB/Files/DBVT.pdf). 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](http://www.sciencedirect.com/science/article/pii/002001908690058X).

**Tags:** ds.algorithms, reference-request, graph-algorithms, automata-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: No i mean an infinite language of either finite or infinite words defined by a transducer.  
> **username_1**: "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....  
> **username_0**: With "all states are final" I mean that there is no special acceptance condition like Büchi or Müller. A GSM is a Mealy machine where the output on each transition is a word and not just a symbol. It would be great if you could sketch the algorithm to decide equivalence if it is so simple.  
> **username_1**: what is your ref that says it is decidable? think it might be for deterministic and/or non-$\epsilon$ transition machines but not sure. see [Why is it undecidable whether two finite-state transducers are equivalent?](http://math.stackexchange.com/questions/157585/why-is-it-undecidable-whether-two-finite-state-transducers-are-equivalent) math.se  
> **username_0**: I updated my question accordingly. I am aware that equivalence is undecidable for general non-deterministic transducers but it is decidable for single-valued ones (in general for finite-valued ones). However, I am concerned with the special case of deterministic transducers over finite resp. infinite words which are less expressive than single-valued transducers.  
> **username_1**: see the math.se question for refs on both the decidable (Griffiths 1968) and undecidable case (Gurari 1982). do not understand some of your terms such as "finite resp infinite words" or "single/finite valued transducers" etc, suggest you use std terms from elsewhere or carefully define terms. admittedly at times there is not so much stdized terminology in this area.  

---

## 1 answers

### Answer by username_2 on 2022-11-03. Score: 4

It is mentioned in [Muscholl and Puppis's survey on transducers](https://drops.dagstuhl.de/opus/volltexte/2019/10241/) (Theorem 3) that single-valuedness of finite transducers is NL-complete. Hence, equivalence of *deterministic* finite transducers is in NL.


---

