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, 2008, 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
UT WoS
000262368900006
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