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.

Originální název

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

Typ

článek v časopise ve Web of Science, Jimp

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

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

Autoři

MARTIŠKO, J.; KŘIVKA, Z.; MEDUNA, A.

Vydáno

23. 4. 2022

ISSN

0129-0541

Periodikum

International Journal of Foundations of Computer Science

Ročník

33

Číslo

03

Stát

Singapurská republika

Strany od

335

Strany do

348

Strany počet

14

URL

https://www.fit.vut.cz/research/publication/11604/

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/"
}

Dokumenty

cdgs_2pscc.pdf