Result Details
CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages
MEDUNA, A.; MARTIŠKO, J. 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. Electronic Proceedings in Theoretical Computer Science, EPTCS. Debrecen: Open Publishing Association, 2017. no. 252, p. 170-179. ISSN: 2075-2180.
Type
conference paper
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Martiško Jakub, Ing., DIFS (FIT)
Martiško Jakub, Ing., DIFS (FIT)
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.
Keywords
CD Grammar Systems, Context Sensitive Grammars, Propagating Scattered context Grammars,
URL
Published
2017
Pages
170–179
Journal
Electronic Proceedings in Theoretical Computer Science, EPTCS, 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
Publisher
Open Publishing Association
Place
Debrecen
DOI
UT WoS
000439346000018
EID Scopus
BibTeX
@inproceedings{BUT144440,
author="Alexandr {Meduna} and Jakub {Martiško}",
title="CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages",
booktitle="15th International Conference on Automata and Formal Languages",
year="2017",
journal="Electronic Proceedings in Theoretical Computer Science, EPTCS",
volume="2017",
number="252",
pages="170--179",
publisher="Open Publishing Association",
address="Debrecen",
doi="10.4204/EPTCS.252.17",
issn="2075-2180",
url="https://arxiv.org/abs/1708.06467v1"
}
Files
Projects
IT4Innovations excellence in science, MŠMT, Národní program udržitelnosti II, LQ1602, start: 2016-01-01, end: 2020-12-31, completed
Nástroje, metody a technologie ICT pro podporu konceptu smart cities, BUT, Vnitřní projekty VUT, FIT-S-17-3964, start: 2017-03-01, end: 2020-02-29, completed
V3C - Visual Computing Competence Center, TAČR, Centra kompetence, TE01020415, start: 2012-05-01, end: 2019-12-31, completed
Nástroje, metody a technologie ICT pro podporu konceptu smart cities, BUT, Vnitřní projekty VUT, FIT-S-17-3964, start: 2017-03-01, end: 2020-02-29, completed
V3C - Visual Computing Competence Center, TAČR, Centra kompetence, TE01020415, start: 2012-05-01, end: 2019-12-31, completed
Research groups
Formal Model Research Group (RG FM)
Departments