Faculty of Information Technology, BUT

Publication Details

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST Tomáš and MEDUNA Alexander. On Descriptional Complexity of Partially Parallel Grammars. Fundamenta Informaticae, vol. 87, no. 3, pp. 407-415. ISSN 0169-2968.
Czech title
O popisné složitosti částečně paralelních gramatik
Type
journal article
Language
english
Authors
URL
Keywords
formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity
Abstract
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.
Published
2008
Pages
407-415
Journal
Fundamenta Informaticae, vol. 87, no. 3, ISSN 0169-2968
Publisher
IOS Press
BibTeX
@ARTICLE{FITPUB8605,
   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 = "https://www.fit.vut.cz/research/publication/8605"
}
Back to top