Přístupnostní navigace
E-application
Search Search Close
Publication detail
MARTIŠKO, J. KŘIVKA, Z. MEDUNA, A.
Original Title
CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages
Type
journal article in Web of Science
Language
English
Original 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.
Keywords
formal language theory, CD grammar systems, scattered context grammars, propagating rules, erasing rules, context sensitive languages
Authors
MARTIŠKO, J.; KŘIVKA, Z.; MEDUNA, A.
Released
23. 4. 2022
ISBN
0129-0541
Periodical
International Journal of Foundations of Computer Science
Year of study
33
Number
03
State
Republic of Singapore
Pages from
335
Pages to
348
Pages count
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/" }