Undecidable problems
Specific undecidable problems and the reductions proving them undecidable: the Post correspondence problem and its variants, string rewriting, undecidable questions about context-free grammars (ambiguity, intersection, universality, regularity), and emptiness of linear bounded automata.
- Diophantine sets and Hilbert's tenth problem
- Emptiness problem for linear bounded automata
- Post correspondence problem
- Intersection problem for context-free languages
- Ambiguity problem for context-free grammars
- String rewriting systems
- Universality problem for context-free grammars
- Undecidable problems for context-free grammars
- Regularity problem for context-free languages
Loading dependency explorer…
The dependency explorer needs JavaScript and its graph data.