Affiliations: Faculty of Information Technology, Brno University of
Technology, Božetěchova 2, Brno 61266, Czech
Republic. masopust@fit.vutbr.cz | Faculty of Information Technology, Brno University of
Technology, Božetěchova 2, Brno 61266, Czech
Republic. meduna@fit.vutbr.cz
Note: [] Address for correspondence: Faculty of Information Technology,
Brno University of Technology, Božetěchova 2,
Brno 61266, Czech Republic
Abstract: This paper presents some new results concerning the descriptional
complexity of partially parallel grammars. Specifically, it proves that every
recursively enumerable language is generated (i) by a four-nonterminal
scattered context grammar with no more than four non-context-free productions,
(ii) by a two-nonterminal multisequential grammar with no more than two
selectors, or (iii) by a three-nonterminalmulticontinuous grammar with no more
than two selectors.
