Result 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.
Type
journal article
Language
English
Authors
Martiško Jakub, Ing.
Křivka Zbyněk, Ing., Ph.D., DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
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

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/"
}
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
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top