Detail publikace

k-Limited Erasing Performed by Scattered Context Grammars

TECHET Jiří. k-Limited Erasing Performed by Scattered Context Grammars. In: Proceedings of the 13th Conference STUDENT EEICT 2007, Volume 4. Brno: Fakulta elektrotechniky a komunikačních technologií VUT v Brně, 2007, s. 419-423. ISBN 978-80214-3410-3.
Název česky
k-limitované vymazávání prováděné gramatikami s rozptýleným kontextem
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Techet Jiří, Ing., Ph.D. (UIFS FIT VUT)
Klíčová slova

gramatiky s rozptýleným kontextem, vymazávání nonterminálů

Abstrakt

Gramatika s rozptýleným kontextem G vymazává nonterminály k-limitovaným způsobem, kde k je kladné celé číslo, jestliže pro každou větu náležející do jazyka G existuje taková derivace, že v každé větné formě je mezi každými dvěma symboly, ze kterých G derivuje neprázdné řetězce, řetězec obsahující maximálně k nonterminálů, ze kterých se generují prázdné řetězce. V této práci je dokázáno, že libovolná gramatika s rozptýleným kontextem, která vymazává nonterminály k-limitovaným způsobem může být převedena na ekvivalentní gramatiku s rozptýleným kontextem bez vymazávacích pravidel, což v obecném případě není možné.

Rok
2007
Strany
419-423
Sborník
Proceedings of the 13th Conference STUDENT EEICT 2007, Volume 4
Konference
Student EEICT 2007, Brno, CZ
ISBN
978-80214-3410-3
Vydavatel
Fakulta elektrotechniky a komunikačních technologií VUT v Brně
Místo
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB8320,
   author = "Ji\v{r}\'{i} Techet",
   title = "k-Limited Erasing Performed by Scattered Context Grammars",
   pages = "419--423",
   booktitle = "Proceedings of the 13th Conference STUDENT EEICT 2007, Volume 4",
   year = 2007,
   location = "Brno, CZ",
   publisher = "Faculty of Electrical Engineering and Communication BUT",
   ISBN = "978-80214-3410-3",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8320"
}
Nahoru