Detail publikace

General CD Grammar Systems and Their Simplification

KOCMAN, R.; KŘIVKA, Z.; MEDUNA, A. General CD Grammar Systems and Their Simplification. Journal of Automata, Languages and Combinatorics, 2020, vol. 25, no. 1, p. 37-54. ISSN: 1430-189X.
Název česky
Obecné CD gramatické systémy a jejich zjednodušení
Typ
článek v časopise
Jazyk
anglicky
Autoři
Kocman Radim, Ing., Ph.D. (CVT)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Klíčová slova

general grammars, CD grammar systems, simulated non-context-free rules, homogeneous rules, evenly homogeneous rules

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{BUT162079,
  author="Radim {Kocman} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="General CD Grammar Systems and Their Simplification",
  journal="Journal of Automata, Languages and Combinatorics",
  year="2020",
  volume="25",
  number="1",
  pages="37--54",
  doi="10.25596/jalc-2020-037",
  issn="1430-189X",
  url="https://www.fit.vut.cz/research/publication/11509/"
}
Nahoru