Journal article

MASOPUST Tomáš and MEDUNA Alexander. On Descriptional Complexity of Partially Parallel Grammars. Fundamenta Informaticae. Amsterdam: IOS Press, 2008, vol. 87, no. 3, pp. 407-415. ISSN 0169-2968.
Publication language:english
Original title:On Descriptional Complexity of Partially Parallel Grammars
Title (cs):O popisné složitosti částečně paralelních gramatik
Pages:407-415
Year:2008
Journal:Fundamenta Informaticae, Vol. 87, No. 3, Amsterdam, NL
ISSN:0169-2968
URL:http://fi.mimuw.edu.pl/vol87.html [HTML]
Keywords
formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity
Annotation
In this paper, we improve some well-known results concerning descriptional complexity of partially parallel grammars. Specifically, we prove that every recursively enumerable language is generated by a four-nonterminal scattered context grammar with no more than four non-context-free productions, by a two-nonterminal multisequential grammar with no more than two selectors, or by a three-nonterminal multicontinuous grammar with no more than two selectors.
BibTeX:
@ARTICLE{
   author = {Tom{\'{a}}{\v{s}} Masopust and Alexander Meduna},
   title = {On Descriptional Complexity of Partially Parallel Grammars},
   pages = {407--415},
   journal = {Fundamenta Informaticae},
   volume = {87},
   number = {3},
   year = {2008},
   ISSN = {0169-2968},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8605}
}

Your IPv4 address: 54.198.31.213
Switch to IPv6 connection

DNSSEC [dnssec]