Publication details
On Descriptional Complexity of Partially Parallel Grammars
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Periodical |
| Magazine / Source | Fundamenta Informaticae |
| MU Faculty or unit | |
| Citation | |
| Web | http://fi.mimuw.edu.pl/vol87.html |
| Keywords | formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity |
| Description | 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. |