Detail publikačního výsledku

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

KŘIVKA, Z.; MEDUNA, A.

Originální název

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

Anglický název

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

Druh

Článek WoS

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

KŘIVKA, Z.; MEDUNA, A.

Rok RIV

2022

Vydáno

12.05.2021

ISSN

0169-2968

Periodikum

FUNDAMENTA INFORMATICAE

Svazek

179

Číslo

4

Stát

Polská republika

Strany od

361

Strany do

384

Strany počet

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

Dokumenty

paper
scg1rule_printed_version