Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete

Article type: Research Article

Authors: Křivka, Zbyněk | Meduna, Alexander^{; *}

Affiliations: Brno University of Technology, Faculty of Information Technology, IT4Innovations Centre of Excellence, Božetěchova 2, 612 66 Brno, Czech Republic. krivka@fit.vutbr.cz, meduna@fit.vutbr.cz

Correspondence: [*] Address for correspondence: Brno University of Technology, Faculty of Information Technology, IT4Innovations Centre of Excellence, Božetěchova 2, 612 66 Brno, Czech Republic.

Abstract: This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions. It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.

Keywords: Scattered context grammars, size reduction, the number of non-context-free productions, parallel productions, computational completeness, descriptional complexity

DOI: 10.3233/FI-2021-2028

Journal: Fundamenta Informaticae, vol. 179, no. 4, pp. 361-384, 2021