Publication Details

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

KŘIVKA Zbyněk and MEDUNA Alexander. Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete. Fundamenta Informaticae, vol. 179, no. 4, 2021, pp. 361-384. ISSN 0169-2968.

Czech title

Gramatiky s rozptýleným kontextem s jediným nebezkontextovým pravidlem jsou výpočetně úplné

Type

journal article

Language

english

Authors

Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)

Keywords

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

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.

Published

2021

Pages

361-384

Journal

Fundamenta Informaticae, vol. 179, no. 4, ISSN 0169-2968

Publisher

IOS Press

DOI

10.3233/FI-2021-2028

UT WoS

000651794800003

EID Scopus

2-s2.0-85106764278

BibTeX

@ARTICLE{FITPUB11559,
   author = "Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
   title = "Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete",
   pages = "361--384",
   journal = "Fundamenta Informaticae",
   volume = 179,
   number = 4,
   year = 2021,
   ISSN = "0169-2968",
   doi = "10.3233/FI-2021-2028",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11559"
}