Descriptional complexity of multi-parallel grammars
This paper studies the descriptional complexity of multi-parallel grammars with respect to the number of nonterminals and selectors, and the length of these selectors. As a result, it proves that every recursively enumerable language is generated by a multi-parallel grammar with no more than seven nonterminals and four selectors of length five. (c) 2008 Elsevier B.V. All rights reserved.
descriptional complexity multi-parallel grammars formal languages