Journal article
Authors list: Kutrib, Martin; Malcher, Andreas
Publication year: 2007
Pages: 1293-1302
Journal: International Journal of Foundations of Computer Science
Volume number: 18
Issue number: 6
ISSN: 0129-0541
eISSN: 1793-6373
DOI Link: https://doi.org/10.1142/S0129054107005339
Publisher: 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.
Citation Styles
Harvard Citation style: 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 Citation style: 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
Keywords
arithmetic hierarchy; Church-Rosser languages; context-free languages; SENSITIVE LANGUAGES; strongly context-free languages
