# Equivalence problem

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Equivalence_problem
> Markdown URL: https://mediated.wiki/source/Equivalence_problem.md
> Source: https://en.wikipedia.org/wiki/Equivalence_problem
> Source revision: 1149828999
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Question in theoretical computer science}}In [theoretical computer science](/source/theoretical_computer_science) and [formal language theory](/source/formal_language_theory), 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 [decision problem](/source/decision_problem) depend upon the type of representation under consideration.

For instance, in the case of [finite-state automata](/source/finite-state_automaton), equivalence is decidable, and the problem is [PSPACE-complete](/source/PSPACE-complete).
Further, in the case of [deterministic pushdown automata](/source/deterministic_pushdown_automaton), equivalence is decidable, [Géraud Sénizergues](/source/G%C3%A9raud_S%C3%A9nizergues) won the [Gödel Prize](/source/G%C3%B6del_Prize) for this result. Subsequently, the problem was shown to lie in TOWER, the least [non-elementary complexity class](/source/nonelementary_problem).<ref>P. Jančar. Equivalences of Pushdown Systems Are Hard, 2014.</ref>

It becomes an [undecidable](/source/Undecidable_problem) problem for [pushdown automata](/source/pushdown_automaton) or any machine that can decide [context-free language](/source/context-free_language)s or more powerful languages.<ref>J. E. Hopcroft and J. D. Ullman. [Introduction to Automata Theory, Languages, and Computation](/source/Introduction_to_Automata_Theory%2C_Languages%2C_and_Computation), first edition, 1979.</ref>

<!-- From memory, it should be in Hopcroft Ullman, but needs checking -->

==References==
{{reflist}}

{{comp-sci-stub}}

Category:Formal languages

---
Adapted from the Wikipedia article [Equivalence problem](https://en.wikipedia.org/wiki/Equivalence_problem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Equivalence_problem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.