UCFL

Church-Rosser languages vs. UCFL. The class of growing context-sensitive languages (GCSL) was proposed as a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. In this paper we concentrate on the class of Church Rosser Languages (CRL), the “deterministic counterpart” of GCSL. We prove the conjecture that the set of palindromes is not in CRL. This implies that CFL $cap$ co-CFL as well as UCFL $cap$ co-UCFL are not included in CRL, where UCFL denotes the class of unambiguous context-free languages. Our proof uses a novel pumping technique, which is of independent interest.