## UCFL

 swMATH ID: 2951 Software Authors: Jurdziński, Tomasz; Lorys, Krzysztof Description: 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. Homepage: http://www.springerlink.com/content/5ey8510mtm7txh2f/fulltext.pdf Related Software: Referenced in: 11 Publications
all top 5

### Referenced by 12 Authors

 6 Otto, Friedrich 4 Jurdziński, Tomasz 2 Loryś, Krzysztof 2 Mráz, František 2 Plátek, Martin 1 Hundeshagen, Norbert 1 Kutrib, Martin 1 Messerschmidt, Hartmut 1 O’Dunlaing, Colm P. 1 Okhotin, Alexander 1 Schluter, Natalie 1 Vollweiler, Marcel

### Referenced in 5 Serials

 4 Theoretical Computer Science 1 Information and Computation 1 International Journal of Foundations of Computer Science 1 RAIRO. Theoretical Informatics and Applications 1 Fundamenta Informaticae

### Referenced in 1 Field

 11 Computer science (68-XX)