When Church-Rosser becomes context free
We investigate the intersection of Church-Rosser languages and (strongly) context-free languages. The intersection is still a proper superset of the deterministic context-free languages as well as of their reversals, while its membership problem is solvable in linear time. For the problem whether a given Church-Rosser or context-free language belongs to the intersection we show completeness for the second level of the arithmetic hierarchy. The equivalence of Church-Rosser and context-free languages is Pi(1)-complete. It is proved that all considered intersections are pairwise incomparable. Finally, closure properties under several operations are investigated.
church-rosser languages context-free languages arithmetic hierarchy strongly context-free languages