Journalartikel

Jahr der Veröffentlichung: 2007

Seiten: 1293-1302

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 18

Heftnummer: 6

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054107005339

Verlag: World Scientific Publishing

Abstract: 
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.

Harvard-Zitierstil: Kutrib, M. and Malcher, A. (2007) When Church-Rosser becomes context free, International Journal of Foundations of Computer Science, 18(6), pp. 1293-1302. https://doi.org/10.1142/S0129054107005339

APA-Zitierstil: Kutrib, M., & Malcher, A. (2007). When Church-Rosser becomes context free. International Journal of Foundations of Computer Science. 18(6), 1293-1302. https://doi.org/10.1142/S0129054107005339