HIGHLY UNDECIDABLE PROBLEMS FOR INFINITE COMPUTATIONS

We show that many classical decision problems about1-counter ω -languages, context free ω -languages, or infinitary ratio-nal relations, are Π12-complete, hence located at the second level ofthe analytical hierarchy, and “highly undecidable”. In particular, theuniversality problem, the inclusion problem, the equivalence problem,the determinizability problem, the complementability problem, and theunambiguity problem are all Π12-complete for context-free ω -languagesor for infinitary rational relations. Topological and arithmetical prop-erties of 1-counter ω -languages, context free ω -languages, or infinitaryrational relations, are also highly undecidable. These very surprisingresults provide the first examples of highly undecidable problems aboutthe behaviour of very simple finite machines like 1-counter automataor 2-tape automata