Journal article

MEDUNA Alexander and ZEMEK Petr. Workspace Theorems for Regular-Controlled Grammars. Theoretical Computer Science. Paris: Elsevier Science, 2011, vol. 412, no. 35, pp. 4604-4612. ISSN 0304-3975. Available from: http://www.sciencedirect.com/science/article/pii/S0304397511003513
Publication language:english
Original title:Workspace Theorems for Regular-Controlled Grammars
Title (cs):Workspace věty pro gramatiky řízené regulárním jazykem
Pages:4604-4612
Place:FR
Year:2011
URL:http://www.sciencedirect.com/science/article/pii/S0304397511003513
Journal:Theoretical Computer Science, Vol. 412, No. 35, Paris, FR
ISSN:0304-3975
Keywords
Regular-controlled context-free grammars, workspace theorems, removal of erasing rules
Annotation
This paper establishes a workspace theorem in terms of regular-controlled (context-free) grammars. It proves that, if, for a regular-controlled 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 (k-1)|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 regular-controlled grammar. An analogical workspace theorem is demonstrated for regular-controlled grammars with appearance checking. The paper provides an algorithm that removes all erasing rules from any regular-controlled 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 Regular-Controlled Grammars},
   pages = {4604--4612},
   journal = {Theoretical Computer Science},
   volume = {412},
   number = {35},
   year = {2011},
   ISSN = {0304-3975},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9583}
}

Your IPv4 address: 23.23.8.131
Switch to IPv6 connection

DNSSEC [dnssec]