Highly Undecidable Problems For Infinite Computations

Olivier Finkel

We show that many classical decision problems about 1-counter omega-languages, context free omega-languages, or infinitary rational relations, are ${\Pi }_2^1$-complete, hence located a…