Journal articleMEDUNA Alexander and ZEMEK Petr. OneSided Random Context Grammars. Acta Informatica. 2011, vol. 48, no. 3, pp. 149163. ISSN 00015903. Available from: http://www.springerlink.com/content/c70163w7764u8660/  Publication language:  english 

Original title:  OneSided Random Context Grammars 

Title (cs):  Jednostranné gramatiky s nahodilým kontextem 

Pages:  149163 

Place:  DE 

Year:  2011 

URL:  http://www.springerlink.com/content/c70163w7764u8660/ 

Journal:  Acta Informatica, Vol. 48, No. 3, DE 

ISSN:  00015903 

DOI:  10.1007/s002360110134y 

Keywords 

Regulated rewriting, random context grammars, onesided variants, generative power, language families 
Annotation 

The notion of a onesided random context grammar is defined as a contextfreebased regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules. A left random context rule can rewrite a nonterminal if each of its permitting symbols occurs to the left of the rewritten symbol in the current sentential form while each of its forbidding symbols does not occur there. A right random context rule is applied analogically except that the symbols are examined to the right of the rewritten symbol.
The paper demonstrates that without erasing rules, onesided random context grammars characterize the family of contextsensitive languages, and with erasing rules, these grammars characterize the family of recursively enumerable languages. In fact, these characterization results hold even if the set of left random context rules coincides with the set of right random context rules. Several special cases of these grammars are considered, and their generative power is established. In its conclusion, some important open problems are suggested to study in the future. 
BibTeX: 

@ARTICLE{
author = {Alexander Meduna and Petr Zemek},
title = {OneSided Random Context Grammars},
pages = {149163},
journal = {Acta Informatica},
volume = {48},
number = {3},
year = {2011},
ISSN = {00015903},
doi = {10.1007/s002360110134y},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9472}
} 
