<p>According to the answer to this question:
<a href="https://cs.stackexchange.com/questions/13456/what-is-the-complexity-of-the-emptiness-problem-for-2-way-dfas">https://cs.stackexchange.com/questions/13456/what-is-the-complexity-of-the-emptiness-problem-for-2-way-dfas</a></p>
<p>The complexity of emptiness for 2-WAY DFAs is already PSPACE complete, so equivalence is also PSPACE-hard (and membership in PSPACE is easy by the single-exponential translation to DFA).</p>

CC BY-SA 4.0
2022-10-24T12:07:20.027Z
Thanks! This is the reference I needed.
Janmar
CC BY-SA 4.0
2022-10-24T11:53:06.427Z
2022-10-24T11:53:06.427Z
Shaull
<p>I'm interested in the computational complexity of deciding equivalence of 2DFAs.</p>
<p>It is known that converting 2DFA to DFA can incur a blow up in states. However I'm not sure whether this automatically tells us something about the complexity of 2DFA equivalence.</p>
<p>Which leads to my question: Is there a hardness result for 2DFA equivalence like the PSPACE-completeness of language equivalence of NFAs and regular expressions. Conversely, I am interested in literature I might have missed that algorithmically solves the equivalence problem directly on 2DFA, without translating to DFAs first.</p>

<fl.formal-languages><automata-theory>
Algorithms for equivalence of 2 way finite automata (2DFA)
Janmar
# Algorithms for equivalence of 2 way finite automata (2DFA)

(Asked by: username_0 on 2022-10-24)

I'm interested in the computational complexity of deciding equivalence of 2DFAs.

It is known that converting 2DFA to DFA can incur a blow up in states. However I'm not sure whether this automatically tells us something about the complexity of 2DFA equivalence.

Which leads to my question: Is there a hardness result for 2DFA equivalence like the PSPACE-completeness of language equivalence of NFAs and regular expressions. Conversely, I am interested in literature I might have missed that algorithmically solves the equivalence problem directly on 2DFA, without translating to DFAs first.

**Tags:** fl.formal-languages, automata-theory

---

## 1 answers

### Answer by username_1 on 2022-10-24. Score: 4 | Accepted answer

According to the answer to this question:
<https://cs.stackexchange.com/questions/13456/what-is-the-complexity-of-the-emptiness-problem-for-2-way-dfas>

The complexity of emptiness for 2-WAY DFAs is already PSPACE complete, so equivalence is also PSPACE-hard (and membership in PSPACE is easy by the single-exponential translation to DFA).

> **Comments:**
> **username_0**: Thanks! This is the reference I needed.  

---

