Detail publikace

Nonterminal Complexity of One-Sided Random Context Grammars

MEDUNA, A.; ZEMEK, P. Nonterminal Complexity of One-Sided Random Context Grammars. Acta Informatica, 2012, vol. 49, no. 2, p. 55-68. ISSN: 0001-5903.
Název česky
Neterminální složitost jednostranných gramatik s nahodilým kontextem
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Zemek Petr, Ing., Ph.D.
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
DOI
10.1007/s00236-012-0150-6
UT WoS
000301374500001
BibTeX 
@article{BUT91445,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Nonterminal Complexity of One-Sided Random Context Grammars",
  journal="Acta Informatica",
  year="2012",
  volume="49",
  number="2",
  pages="55--68",
  doi="10.1007/s00236-012-0150-6",
  issn="0001-5903",
  url="http://www.springerlink.com/content/5822041380786746/"
}
Nahoru