Detail výsledku

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.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Martiško Jakub, Ing.
Křivka Zbyněk, Ing., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
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

Rok
2022
Strany
335–348
Časopis
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, roč. 33, č. 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/"
}
Soubory
Projekty
Centrum kompetence ve zpracování vizuálních informací (V3C - Visual Computing Competence Center), TAČR, Centra kompetence, TE01020415, zahájení: 2012-05-01, ukončení: 2019-12-31, ukončen
IT4Innovations excellence in science, MŠMT, Národní program udržitelnosti II, LQ1602, zahájení: 2016-01-01, ukončení: 2020-12-31, ukončen
Nástroje, metody a technologie ICT pro podporu konceptu smart cities, VUT, Vnitřní projekty VUT, FIT-S-17-3964, zahájení: 2017-03-01, ukončení: 2020-02-29, ukončen
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru