In
theoretical computer science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
and
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet".
The alphabet of a formal language consists of symbol ...
, 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
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
depend upon the type of representation under consideration.
For instance, in the case of
finite-state automata
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
, equivalence is decidable, and the problem is
PSPACE-complete
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (PSPACE, polynomial space) and if every other problem that can be solved in polynomial sp ...
.
Further, in the case of
deterministic pushdown automata
In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages ...
, equivalence is decidable,
Géraud Sénizergues
Géraud Sénizergues (born 9 March 1957) is a French computer scientist at the University of Bordeaux.
He is known for his contributions to automata theory, combinatorial group theory and abstract rewriting systems.
He received his Ph.D. (Doct ...
won the
Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...
for this result. Subsequently, the problem was shown to lie in TOWER, the least
non-elementary complexity class.
It becomes an
undecidable problem for
pushdown automata
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is
a type of automaton that employs a stack.
Pushdown automata are used in theories about what can be computed by machines. They are more capab ...
or any machine that can decide
context-free language
In formal language theory, a context-free language (CFL), also called a Chomsky type-2 language, is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, mos ...
s or more powerful languages.
[J. E. Hopcroft and J. D. Ullman. , first edition, 1979.]
References
{{comp-sci-stub
Formal languages