Book chapterMEDUNA Alexander and ZEMEK Petr. OneSided Random Context Grammars: A Survey. Computing with New Resources. Berlin: Springer Verlag, 2014, pp. 338351. ISBN 9783319133492. Available from: https://www.scopus.com/record/display.uri?eid=2s2.084916899681&origin=resultslist  Publication language:  english 

Original title:  OneSided Random Context Grammars: A Survey 

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

Pages:  338351 

Book:  Computing with New Resources 

Place:  Berlin, DE 

Year:  2014 

URL:  https://www.scopus.com/record/display.uri?eid=2s2.084916899681&origin=resultslist 

ISBN:  9783319133492 

DOI:  10.1007/9783319133508_25 

Publisher:  Springer Verlag 

URL:  http://www.springer.com/computer/theoretical+computer+science/book/9783319133492 [HTML] 

Keywords 

formal language theory, regulated rewriting, random context grammars, onesided random context grammars, generative power, normal forms, reduction, leftmost derivations, generalized versions, survey 
Annotation 

Recall that the notion of a onesided random context grammar is based upon a finite set of contextfree rules, each of which may be extended by finitely many permitting and forbidding nonterminal symbols. The set of all these rules is divided into two sets  the set of left random context rules and the set of right random context rules. When applying a left random context rule, the grammar checks the existence and absence of its permitting and forbidding symbols, respectively, in the prefix to the left of the rewritten nonterminal. Analogically, when applying a right random context rule, it checks the existence and absence of its permitting and forbidding symbols, respectively, only in the suffix to the right of the rewritten nonterminal.
This paper gives a survey of the established results concerning onesided random context grammars. These results concern their generative power, normal forms, size reduction, and conceptual modifications, which represent both restricted and generalized versions of their standard concepts. Perhaps most importantly and surprisingly, the paper points out that propagating versions of onesided random context grammars characterize the family of contextsensitive languages, and with erasing rules, they characterize the family of recursively enumerable languages; as a result, they are stronger than ordinary random context grammars. Many open problem areas are suggested.

BibTeX: 

@INBOOK{
author = {Alexander Meduna and Petr Zemek},
title = {OneSided Random Context Grammars: A Survey},
pages = {338351},
booktitle = {Computing with New Resources},
year = {2014},
location = {Berlin, DE},
publisher = {Springer Verlag},
ISBN = {9783319133492},
doi = {10.1007/9783319133508_25},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=10515}
} 
