Detail publikace

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. p. 170-179. ISSN: 2075-2180.
Název česky
CD gramatické systémy se dvěma komponentami s rozptýleným kontextem bez epsilon pravidel popisují třídu kontextových jazyků
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Martiško Jakub, Ing.
URL
Klíčová slova

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

Abstrakt

Příspěvek studuje modifikovanou verzi L(CS) = L(PSCG) problému. Tato modifikovaná verze porovnává generativní sílu kontextových gramatik a CD gramatických systémů s komponentami, jež jsou tvořeny gramatikami s rozptýleným kontextem bez epsilon pravidel. V rámci příspěvku je pak prezentován důkaz ekvivalence těchto dvou modelů.

Rok
2017
Strany
170–179
Časopis
Electronic Proceedings in Theoretical Computer Science, EPTCS, roč. 2017, č. 252, ISSN 2075-2180
Sborník
15th International Conference on Automata and Formal Languages
Vydavatel
Open Publishing Association
Místo
Debrecen
DOI
10.4204/EPTCS.252.17
UT WoS
000439346000018
EID Scopus
2-s2.0-85030163581
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"
}
Nahoru