Detail publikace

k-Limited Erasing Performed by Scattered Context Grammars

TECHET Jiří. k-Limited Erasing Performed by Scattered Context Grammars. In: Information Systems and Formal Models ISIM, WFM '07. Hradec nad Moravicí: Slezská univerzita v Opavě, 2007, s. 227-234. ISBN 978-80-7248006-7.
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
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
227-234
Sborník
Information Systems and Formal Models ISIM, WFM '07
Konference
2nd International Workshop on Formal Models WFM'07, Hradec nad Moravicí, CZ
ISBN
978-80-7248006-7
Vydavatel
Slezská univerzita v Opavě
Místo
Hradec nad Moravicí, CZ
BibTeX
@INPROCEEDINGS{FITPUB8314,
   author = "Ji\v{r}\'{i} Techet",
   title = "k-Limited Erasing Performed by Scattered Context Grammars",
   pages = "227--234",
   booktitle = "Information Systems and Formal Models ISIM, WFM '07",
   year = 2007,
   location = "Hradec nad Moravic\'{i}, CZ",
   publisher = "Silesian University",
   ISBN = "978-80-7248006-7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8314"
}
Nahoru