Detail publikace

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

KŘIVKA Zbyněk a MEDUNA Alexander. Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete. Fundamenta Informaticae, roč. 179, č. 4, 2021, s. 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
angličtina
Autoři
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
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
Vydavatel
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"
}
Nahoru