Detail publikace

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.
Název česky
Gramatiky s rozptýleným kontextem s jediným nebezkontextovým pravidlem jsou výpočetně úplné
Typ
článek v časopise
Jazyk
anglicky
Autoři
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Klíčová slova

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

Abstrakt

Článek zkoumá redukci počtu nebezkotextových pravidel u gramatik s  rozptýleným kontextem. Dokazuje, že každý rekurzivně spočetný jazyk je generován gramatikou s rozptýleným kontextem, která nemá více než jedno nebezkontextové pravidlo. Na závěr je formulován otevřený problém.

Rok
2021
Strany
361–384
Časopis
Fundamenta Informaticae, roč. 179, č. 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/"
}
Nahoru