Fakulta informačních technologií VUT v Brně

Detail publikace

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

MEDUNA Alexander a 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, s. 170-179. ISSN 2075-2180. Dostupné z: https://arxiv.org/abs/1708.06467v1
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
angličtina
Autoři
URL
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, roč. 2017, č. 252, ISSN 2075-2180
Sborník
15th International Conference on Automata and Formal Languages
Konference
15th International Conference on Automata and Formal Languages, Debrecen, HU
Vydavatel
Open Publishing Association
Místo
Debrecen, HU
DOI
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",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11445"
}
Nahoru