Článek v časopise

MEDUNA Alexander a ZEMEK Petr. One-Sided Forbidding Grammars and Selective Substitution Grammars. International Journal of Computer Mathematics. 2012, roč. 89, č. 5, s. 586-596. ISSN 0020-7160. Dostupné z: http://www.tandfonline.com/doi/abs/10.1080/00207160.2011.642300
Jazyk publikace:angličtina
Název publikace:One-Sided Forbidding Grammars and Selective Substitution Grammars
Název (cs):Jednostranné zakazující gramatiky a selektivní gramatiky
Strany:586-596
Místo vydání:GB
Rok:2012
URL:http://www.tandfonline.com/doi/abs/10.1080/00207160.2011.642300
Časopis:International Journal of Computer Mathematics, roč. 89, č. 5, GB
ISSN:0020-7160
Klíčová slova
Teorie formálních jazyků, řízené přepisování, jednostranné zakazující gramatiky, selektivní gramatiky, generativní síla
Anotace
V jednostranných zakazujících gramatikách je množina pravidel rozdělena na množinu levě zakazujících pravidel a množinu pravě zakazujících pravidel. Levě zakazující pravidlo může přepsat neterminál pokud aktuální větná forma vlevo od přepisovaného symbolu neobsahuje žádný ze zakázaných symbolů. Pravě zakazující pravidlo je aplikováno analogicky, pouze kontrola se provádí doprava místo doleva. Jinak tyto gramatiky pracují stejně jako obyčejné zakazující gramatiky.

V článku je jako hlavní výsledek dokázáno, že jednostranné zakazující gramatiky jsou ekvivalentní selektivním gramatikám. Tato ekvivalence je dokázána jak pro gramatiky připouštějící vymazávací pravidla, tak pro gramatiky bez těchto pravidel. Dále je dokázáno, že jednostranné zakazující gramatiky s množinou levě zakazujících pravidel identickou s množinou pravě zakazujících pravidel generují pouze třídu bezkontextových jazyků. V závěru článku je diskutován význam dosažených výsledků.
BibTeX:
@ARTICLE{
   author = {Alexander Meduna and Petr Zemek},
   title = {One-Sided Forbidding Grammars and Selective Substitution
	Grammars},
   pages = {586--596},
   journal = {International Journal of Computer Mathematics},
   volume = {89},
   number = {5},
   year = {2012},
   ISSN = {0020-7160},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9716}
}

Vaše IPv4 adresa: 54.211.219.20
Přepnout na IPv6 spojení

DNSSEC [dnssec]