Journal articleMEDUNA Alexander and ZEMEK Petr. Workspace Theorems for RegularControlled Grammars. Theoretical Computer Science. Paris: Elsevier Science, 2011, vol. 412, no. 35, pp. 46044612. ISSN 03043975. Available from: http://www.sciencedirect.com/science/article/pii/S0304397511003513  Publication language:  english 

Original title:  Workspace Theorems for RegularControlled Grammars 

Title (cs):  Workspace věty pro gramatiky řízené regulárním jazykem 

Pages:  46044612 

Place:  FR 

Year:  2011 

URL:  http://www.sciencedirect.com/science/article/pii/S0304397511003513 

Journal:  Theoretical Computer Science, Vol. 412, No. 35, Paris, FR 

ISSN:  03043975 

DOI:  10.1016/j.tcs.2011.04.042 

Keywords 

Regularcontrolled contextfree grammars, workspace theorems, removal of erasing rules 
Annotation 

This paper establishes a workspace theorem in terms of regularcontrolled (contextfree) grammars. It proves that, if, for a regularcontrolled grammar H, there is a positive integer k such that H generates every sentence y in L(H) by a derivation in which every sentential form x contains at most (k1)x/k occurrences of nonterminals that are erased throughout the rest of the derivation, where x denotes the length of x, then the language of H is generated by a propagating regularcontrolled grammar. An analogical workspace theorem is demonstrated for regularcontrolled grammars with appearance checking. The paper provides an algorithm that removes all erasing rules from any regularcontrolled grammar (possibly with appearance checking) that satisfies the workspace condition above without affecting the generated language. In its conclusion, the paper points out a relationship of the workspace theorems to other areas of formal language theory.

BibTeX: 

@ARTICLE{
author = {Alexander Meduna and Petr Zemek},
title = {Workspace Theorems for RegularControlled Grammars},
pages = {46044612},
journal = {Theoretical Computer Science},
volume = {412},
number = {35},
year = {2011},
ISSN = {03043975},
doi = {10.1016/j.tcs.2011.04.042},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9583}
} 
