Equivalence problem

In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a> and <a href="/facts/Formal_language_theory/crDTyP8q">formal language theory</a>, the equivalence problem is the question of determining, given two representations of formal languages, whether they denote the same formal language. 
The complexity and decidability of this <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> depend upon the type of representation under consideration.
For instance, in the case of <a href="/facts/Finite-state_automaton/GMusWd0a">finite-state automata</a>, equivalence is decidable, and the problem is <a href="/facts/PSPACE-complete/gkV3vHfX">PSPACE-complete</a>.
Further, in the case of <a href="/facts/Deterministic_pushdown_automaton/WHaMPJcS">deterministic pushdown automata</a>, equivalence is decidable, <a href="/facts/G%25C3%25A9raud_S%25C3%25A9nizergues/0DIP9jPJ">Géraud Sénizergues</a> won the <a href="/facts/G%25C3%25B6del_Prize/RdbqdDj6">Gödel Prize</a> for this result. Subsequently, the problem was shown to lie in TOWER, the least <a href="/facts/Nonelementary_problem/PYLSyvHo">non-elementary complexity class</a>.
It becomes an <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable</a> problem for <a href="/facts/Pushdown_automaton/kEPRC70F">pushdown automata</a> or any machine that can decide <a href="/facts/Context-free_language/sHDxB5So">context-free languages</a> or more powerful languages.

Equivalence problem open-in-new

Equivalence problem