Publication Details

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

MEDUNA Alexander and ZEMEK Petr. One-Sided Random Context Grammars with a Limited Number of Right Random Context Rules. Theoretical Computer Science, vol. 516, no. 1, 2014, pp. 127-132. ISSN 0304-3975. Available from: http://www.sciencedirect.com/science/article/pii/S030439751300827X
Czech title
Jednostranné gramatiky s nahodilým kontextem a s omezeným počtem pravě kontextových pravidel
Type
journal article
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Zemek Petr, Ing. (DIFS FIT BUT)
URL
Keywords

formal languages, one-sided random context grammars, right random context rules, reduction

Abstract

This paper deals with regulated grammars. Specifically, it studies one-sided random context grammars. It demonstrates that any recursively enumerable language can be generated by these grammars with no more than two right random context rules.

Published
2014
Pages
127-132
Journal
Theoretical Computer Science, vol. 516, no. 1, ISSN 0304-3975
Publisher
Elsevier Science
DOI
10.1016/j.tcs.2013.11.009
UT WoS
000330817700012
EID Scopus
2-s2.0-84890492849
BibTeX 
@ARTICLE{FITPUB10190,
   author = "Alexander Meduna and Petr Zemek",
   title = "One-Sided Random Context Grammars with a Limited Number of Right Random Context Rules",
   pages = "127--132",
   journal = "Theoretical Computer Science",
   volume = 516,
   number = 1,
   year = 2014,
   ISSN = "0304-3975",
   doi = "10.1016/j.tcs.2013.11.009",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10190"
}
Back to top