Publication Details

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

MEDUNA Alexander and MARTIŠKO Jakub. CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages. In: 15th International Conference on Automata and Formal Languages. Debrecen: Open Publishing Association, 2017, pp. 170-179. ISSN 2075-2180. Available from: https://arxiv.org/abs/1708.06467v1
Czech title
CD gramatické systémy se dvěma komponentami s rozptýleným kontextem bez epsilon pravidel popisují třídu kontextových jazyků
Type
conference paper
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Martiško Jakub, Ing. (DIFS FIT BUT)
URL
Keywords

CD Grammar Systems, Context Sensitive Grammars, Propagating Scattered context Grammars,

Abstract

The paper deals with the modified version of L(CS) = L(PSCG) problem. The modified version of the problem compares the generative power of context sensitive grammars with the generative power of CD grammar systems with propagating scattered context components. The paper gives a proof that these two models have the same generative power.

Published
2017
Pages
170-179
Journal
Electronic Proceedings in Theoretical Computer Science, vol. 2017, no. 252, ISSN 2075-2180
Proceedings
15th International Conference on Automata and Formal Languages
Conference
15th International Conference on Automata and Formal Languages, Debrecen, HU
Publisher
Open Publishing Association
Place
Debrecen, HU
DOI
10.4204/EPTCS.252.17
UT WoS
000439346000018
EID Scopus
2-s2.0-85030163581
BibTeX 
@INPROCEEDINGS{FITPUB11445,
   author = "Alexander Meduna and Jakub Marti\v{s}ko",
   title = "CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages",
   pages = "170--179",
   booktitle = "15th International Conference on Automata and Formal Languages",
   journal = "Electronic Proceedings in Theoretical Computer Science",
   volume = 2017,
   number = 252,
   year = 2017,
   location = "Debrecen, HU",
   publisher = "Open Publishing Association",
   ISSN = "2075-2180",
   doi = "10.4204/EPTCS.252.17",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11445"
}
Back to top