Detail publikace

One-Sided Random Context Grammars with a Limited Number of Right Random Context Rules

MEDUNA, A.; ZEMEK, P. One-Sided Random Context Grammars with a Limited Number of Right Random Context Rules. Theoretical Computer Science, 2014, vol. 516, no. 1, p. 127-132. ISSN: 0304-3975.
Název česky
Jednostranné gramatiky s nahodilým kontextem a s omezeným počtem pravě kontextových pravidel
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, jednostranné gramatiky s nahodilým kontextem, pravě kontextová pravidla, redukce

Abstrakt

Tento článek se zabývá řízenými gramatikami. Konkrétně studuje jednostranné gramatiky s nahodilým kontextem. Demonstruje, že každý rekurzivně spočetný jazyk lze generovat těmito gramatikami majícími ne více než dvě pravě kontextová pravidla.

Rok
2014
Strany
127–132
Časopis
Theoretical Computer Science, roč. 516, č. 1, ISSN 0304-3975
DOI
10.1016/j.tcs.2013.11.009
UT WoS
000330817700012
EID Scopus
2-s2.0-84890492849
BibTeX 
@article{BUT111481,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="One-Sided Random Context Grammars with a Limited Number of Right Random Context Rules",
  journal="Theoretical Computer Science",
  year="2014",
  volume="516",
  number="1",
  pages="127--132",
  doi="10.1016/j.tcs.2013.11.009",
  issn="0304-3975",
  url="http://www.sciencedirect.com/science/article/pii/S030439751300827X"
}
Nahoru