# 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.

## Keywords for this software

Anything in here will be replaced on browsers that support the canvas element

## References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)