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.


1 Answer 1


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).

  • $\begingroup$ Thanks! This is the reference I needed. $\endgroup$
    – Janmar
    Commented Oct 24, 2022 at 12:07

Your Answer

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

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