Detail publikace

CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages

MARTIŠKO, J.; KŘIVKA, Z.; MEDUNA, A. CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages. International Journal of Foundations of Computer Science, 2022, vol. 33, no. 03, p. 335-348. ISSN: 0129-0541.
Název česky
CD gramatické systémy se dvěma propagujícími komponentami s rozptýleným kontextem charakterizují třídu kontextových jazyků
Typ
článek v časopise
Jazyk
anglicky
Autoři
Martiško Jakub, Ing.
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Klíčová slova

formal language theory, CD grammar systems, scattered context grammars, propagating rules, erasing rules, context sensitive languages

Abstrakt

Problém PSCG = CS řeší, zda rozptýlené gramatiky bez vymazávajících pravidel charakterizují třídu kontextových jazyků. Tento článek odpovídá na analogickou otázku ve smyslu CD gramatických systémů. Přesněji řečeno, článek demonstruje charakterizaci třídy kontextových jazyků  pomoci CD gramatických systému se dvěmi komponentami s propagujícími (nevymazávajícími) rozptýlenými pravidly.

Rok
2022
Strany
335–348
Časopis
International Journal of Foundations of Computer Science, roč. 33, č. 03, ISSN 0129-0541
DOI
10.1142/S0129054122410088
UT WoS
000797246300009
EID Scopus
2-s2.0-85129494938
BibTeX 
@article{BUT162675,
  author="Jakub {Martiško} and Zbyněk {Křivka} and Alexandr {Meduna}",
  title="CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages",
  journal="International Journal of Foundations of Computer Science",
  year="2022",
  volume="33",
  number="03",
  pages="335--348",
  doi="10.1142/S0129054122410088",
  issn="0129-0541",
  url="https://www.fit.vut.cz/research/publication/11604/"
}
Nahoru