Journal articleMEDUNA Alexander and ZEMEK Petr. Left Random Context ET0L Grammars. Fundamenta Informaticae. Amsterdam: IOS Press, 2013, vol. 123, no. 3, pp. 289304. ISSN 01692968. Available from: http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2  Publication language:  english 

Original title:  Left Random Context ET0L Grammars 

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

Pages:  289304 

Place:  NL 

Year:  2013 

URL:  http://iospress.metapress.com/content/b3h6456215g6754p/?p=e7359885e380461c96f9663f43ae8b09&pi=2 

Journal:  Fundamenta Informaticae, Vol. 123, No. 3, Amsterdam, NL 

ISSN:  01692968 

DOI:  10.3233/FI2013811 

Keywords 

Regulated rewriting; ET0L grammars; random context; left variants; generative power; language families 
Annotation 

Consider ET0L grammars. Modify them such that a set of permitting
symbols and a set of forbidding symbols are attached to each of their
rules, just like in random context grammars. A rule like this can
rewrite a symbol if each of its permitting symbols occurs to the left of
the symbol to be rewritten in the current sentential form while each of
its forbidding symbols does not occur there. ET0L grammars modified in
this way are referred to as left random context ET0L grammars, and they
represent the principal subject of the investigation in this paper.
We
prove that these grammars characterize the family of recursively
enumerable languages, and without erasing rules, they characterize the
family of contextsensitive languages. We also introduce a variety of
special cases of these grammars and establish their generative power. In
the conclusion, we put all the achieved results into the context of
formal language theory as a whole and formulate several open questions.

BibTeX: 

@ARTICLE{
author = {Alexander Meduna and Petr Zemek},
title = {Left Random Context ET0L Grammars},
pages = {289304},
journal = {Fundamenta Informaticae},
volume = {123},
number = {3},
year = {2013},
ISSN = {01692968},
doi = {10.3233/FI2013811},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en.iso88592?id=9741}
} 
