Publication Details

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.
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
Martiško Jakub, Ing.
Křivka Zbyněk, Ing., Ph.D. (DIFS)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
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. 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/"
}
Back to top