Publication Details

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

KŘIVKA Zbyněk, MARTIŠKO Jakub and MEDUNA Alexander. CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages. International Journal of Foundations of Computer Science, vol. 33, no. 03, 2022, pp. 335-348. ISSN 0129-0541.
Czech title
CD gramatické systémy se dvěma propagujícími komponentami s rozptýleným kontextem charakterizují třídu kontextových jazyků
Type
journal article
Language
english
Authors
Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT)
Martiško Jakub, Ing. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Keywords

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

Abstract

The PSCG = CS problem asks whether propagating scattered context grammars and context sensitive grammars are equivalent. The presented paper reformulates and answers this problem in terms of CD grammar systems. More specifically, it characterizes the family of context sensitive languages by two-component CD grammar systems with propagating scattered context rules.

Published
2022
Pages
335-348
Journal
International Journal of Foundations of Computer Science, vol. 33, no. 3, ISSN 0129-0541
DOI
10.1142/S0129054122410088
UT WoS
000797246300009
EID Scopus
2-s2.0-85129494938
BibTeX 
@ARTICLE{FITPUB11604,
   author = "Zbyn\v{e}k K\v{r}ivka and Jakub Marti\v{s}ko and Alexander Meduna",
   title = "CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages",
   pages = "335--348",
   journal = "International Journal of Foundations of Computer Science",
   volume = 33,
   number = 03,
   year = 2022,
   ISSN = "0129-0541",
   doi = "10.1142/S0129054122410088",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11604"
}
Back to top