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
References in zbMATH (referenced in 11 articles )
Showing results 1 to 11 of 11.
- Hundeshagen, Norbert; Otto, Friedrich; Vollweiler, Marcel: Transductions computed by PC-systems of monotone deterministic restarting automata (2011)
- Okhotin, Alexander: Expressive power of $\textLL(k)$ Boolean grammars (2011)
- Kutrib, Martin; Messerschmidt, Hartmut; Otto, Friedrich: On stateless two-pushdown automata and restarting automata (2010)
- Ódúnlaing, Colm; Schluter, Natalie: A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems (2010)
- Mráz, F.; Otto, F.; Plátek, M.: The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages (2009)
- Otto, Friedrich: Left-to-right regular languages and two-way restarting automata (2009)
- Jurdziński, Tomasz: The Boolean closure of growing context-sensitive languages (2008)
- Jurdziński, Tomasz; Loryś, Krzysztof: Lower bound technique for length-reducing automata (2007)
- Jurdziński, T.; Mráz, F.; Otto, F.; Plátek, M.: Degrees of non-monotonicity for restarting automata (2006)
- Otto, Friedrich: Restarting automata and their relations to the Chomsky hierarchy (2003)
- Jurdziński, Tomasz; Lorys, Krzysztof: Church-Rosser languages vs. UCFL. (2002)