Detail publikace

k-Limited Erasing Performed by Scattered Context Grammars

TECHET, J. k-Limited Erasing Performed by Scattered Context Grammars. In Information Systems and Formal Models ISIM, WFM '07. Hradec nad Moravicí: Silesian University, 2007. p. 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
anglicky
Autoři
Techet Jiří, Ing., Ph.D.
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
ISBN
978-80-7248006-7
Vydavatel
Silesian University
Místo
Hradec nad Moravicí
BibTeX 
@inproceedings{BUT28590,
  author="Jiří {Techet}",
  title="k-Limited Erasing Performed by Scattered Context Grammars",
  booktitle="Information Systems and Formal Models ISIM, WFM '07",
  year="2007",
  pages="227--234",
  publisher="Silesian University",
  address="Hradec nad Moravicí",
  isbn="978-80-7248006-7"
}
Nahoru