Publication detail

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

KŘIVKA, Z. MEDUNA, A.

Original Title

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

Type

journal article in Web of Science

Language

English

Original 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

Authors

KŘIVKA, Z.; MEDUNA, A.

Released

12. 5. 2021

ISBN

0169-2968

Periodical

Fundamenta Informaticae

Year of study

179

Number

4

State

Republic of Poland

Pages from

361

Pages to

384

Pages count

24

URL

https://www.fit.vut.cz/research/publication/11559/

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/"
}

Documents

scg1rule_printed_version.pdf
paper.pdf