Detail publikace

Nonterminal Complexity of One-Sided Random Context Grammars

MEDUNA Alexander a ZEMEK Petr. Nonterminal Complexity of One-Sided Random Context Grammars. Acta Informatica, roč. 49, č. 2, 2012, s. 55-68. ISSN 0001-5903. Dostupné z: http://www.springerlink.com/content/5822041380786746/
Název česky
Neterminální složitost jednostranných gramatik s nahodilým kontextem
Typ
článek v časopise
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Zemek Petr, Ing. (UIFS FIT VUT)
URL
Klíčová slova

Formální jazyky, neterminální složitost, jednostranné gramatiky s nahodilým kontextem, nahodile kontextové neterminály

Abstrakt

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.

Rok
2012
Strany
55-68
Časopis
Acta Informatica, roč. 49, č. 2, ISSN 0001-5903
Vydavatel
Springer Verlag
DOI
10.1007/s00236-012-0150-6
UT WoS
000301374500001
BibTeX 
@ARTICLE{FITPUB9714,
   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 = "https://www.fit.vut.cz/research/publication/9714"
}
Nahoru