Journal article

MASOPUST Tomáš. On the Descriptional Complexity of Scattered Context Grammars. Theoretical Computer Science. Paris: Elsevier Science, 2009, vol. 410, no. 1, pp. 108-112. ISSN 0304-3975.
Publication language:english
Original title:On the Descriptional Complexity of Scattered Context Grammars
Title (cs):O popisné složitosti gramatik s rozptýleným kontextem
Pages:108-112
Year:2009
Journal:Theoretical Computer Science, Vol. 410, No. 1, Paris, FR
ISSN:0304-3975
URL:http://dx.doi.org/10.1016/j.tcs.2008.10.017 [HTML]
Keywords
scattered context grammar; descriptional complexity.
Annotation
This paper proves that every recursively enumerable language is generated by a scattered context grammar with no more than four nonterminals and three non-context-free productions. In its conclusion, it gives an overview of the results and open problems concerning scattered context grammars and languages.
BibTeX:
@ARTICLE{
   author = {Tom{\'{a}}{\v{s}} Masopust},
   title = {On the Descriptional Complexity of Scattered Context
	Grammars},
   pages = {108--112},
   journal = {Theoretical Computer Science},
   volume = {410},
   number = {1},
   year = {2009},
   ISSN = {0304-3975},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8778}
}

Your IPv4 address: 54.227.127.109
Switch to IPv6 connection

DNSSEC [dnssec]