Publication Details

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

KŘIVKA, Z.; MEDUNA, A. Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete. Fundamenta Informaticae, 2021, vol. 179, no. 4, p. 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)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)

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

DOI

10.3233/FI-2021-2028

UT WoS

000651794800003

EID Scopus

2-s2.0-85106764278

BibTeX

@article{BUT162265,
  author="Zbyněk {Křivka} and Alexandr {Meduna}",
  title="Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete",
  journal="Fundamenta Informaticae",
  year="2021",
  volume="179",
  number="4",
  pages="361--384",
  doi="10.3233/FI-2021-2028",
  issn="0169-2968",
  url="https://www.fit.vut.cz/research/publication/11559/"
}