theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

and

formal language theory In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sy ...

, 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 of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

depend upon the type of representation under consideration. For instance, in the case of finite-state automata, 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 ( polynomial space) and if every other problem that can be solved in polynomial space can ...

. Further, in the case of deterministic pushdown automata, 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. (D ...

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

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) is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...

s or more powerful languages.J. E. Hopcroft and J. D. Ullman.

Introduction to Automata Theory, Languages, and Computation ''Introduction to Automata Theory, Languages, and Computation'' is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later edition ...

, first edition, 1979.

References

{{comp-sci-stub Formal languages