Detail publikace

General CD Grammar Systems and Their Simplification

KOCMAN Radim, KŘIVKA Zbyněk a MEDUNA Alexander. General CD Grammar Systems and Their Simplification. Journal of Automata, Languages and Combinatorics, roč. 25, č. 1, 2020, s. 37-54. ISSN 1430-189X.
Název česky
Obecné CD gramatické systémy a jejich zjednodušení
Typ
článek v časopise
Jazyk
angličtina
Autoři
Kocman Radim, Ing., Ph.D. (CVT FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Abstrakt

Tento článek studuje obecné CD gramatické systémy, jejichž komponentami jsou obecné gramatiky a jsou tedy výpočetně úplné, a zkoumá jejich chování v módech * a t. Článek prezentuje dva typy transformací, které dokáží převést libovolnou obecnou gramatiku na dvoukomponentový obecný CD gramatický systém s jednou bezkontextovou a jednou kontextovou komponentou. První typ transformací generuje kontextovou komponentu s pravidly 11->00 a 0000->epsilon, kdežto druhý typ využívá pravidla 11->00 a 0000->2222. Kromě této významné redukce a zjednodušení kontextových pravidel prezentuje článek také několik dalších užitečných vlastností souvisejících s těmito systémy. Na závěr je pak uvedeno několik poznámek a otevřených problémů.

Rok
2020
Strany
37-54
Časopis
Journal of Automata, Languages and Combinatorics, roč. 25, č. 1, ISSN 1430-189X
DOI
10.25596/jalc-2020-037
EID Scopus
2-s2.0-85085293890
BibTeX 
@ARTICLE{FITPUB11509,
   author = "Radim Kocman and Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
   title = "General CD Grammar Systems and Their Simplification",
   pages = "37--54",
   journal = "Journal of Automata, Languages and Combinatorics",
   volume = 25,
   number = 1,
   year = 2020,
   ISSN = "1430-189X",
   doi = "10.25596/jalc-2020-037",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11509"
}
Nahoru