Prof. RNDr. Alexander Meduna, CSc.

MEDUNA Alexander a ZEMEK Petr. Nonterminal Complexity of One-Sided Random Context Grammars. Acta Informatica. 2012, roč. 49, č. 2, s. 55-68. ISSN 0001-5903. Dostupné z: http://www.springerlink.com/content/5822041380786746/
Jazyk publikace:angličtina
Název publikace:Nonterminal Complexity of One-Sided Random Context Grammars
Název (cs):Neterminální složitost jednostranných gramatik s nahodilým kontextem
Strany:55-68
Místo vydání:DE
Rok:2012
URL:http://www.springerlink.com/content/5822041380786746/
Časopis:Acta Informatica, roč. 49, č. 2, DE
ISSN:0001-5903
DOI:10.1007/s00236-012-0150-6
Klíčová slova
Formální jazyky, neterminální složitost, jednostranné gramatiky s nahodilým kontextem, nahodile kontextové neterminály
Anotace
V článku je studována neterminální složitost jednostranných gramatiky s nahodilým kontextem. Je dokázáno, že každý rekurzivně spočetný jazyk lze generovat jednostrannou gramatikou s nahodilým kontextem mající nejvýše 10 neterminálů. Analogický výsledek platí pro třináct neterminálů v případě těchto gramatik mající množinu levě kontextových pravidel identickou s množinou pravě kontextových pravidel. Dále je zaveden pojem pravě kontextového neterminálu, který je definován jako neterminál vyskytující se na levé straně některého pravě kontextového pravidla. Článek ukazuje, jak transformovat každou jednostrannou gramatiku s nahodilým kontextem G na ekvivalentní jednostrannou gramatiku s nahodilým kontextem H mající pouze dva pravě kontextové neterminály. Analogický výsledek je dokázán (1) pro jednostranné gramatiky s nahodilým kontextem bez vymazávacích pravidel a (2) pro levě kontextové neterminály. V závěru článku jsou zmíněny dva otevřené problémy.
BibTeX:
@ARTICLE{
   author = {Alexander Meduna and Petr Zemek},
   title = {Nonterminal Complexity of One-Sided Random Context
	Grammars},
   pages = {55--68},
   journal = {Acta Informatica},
   volume = 49,
 number = 2,
   year = 2012,
   ISSN = {0001-5903},
   doi = {10.1007/s00236-012-0150-6},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9714}
}

Vaše IPv4 adresa: 34.238.189.171
Přepnout na https