Publication details
Descriptional Complexity of Multi-Parallel Grammars
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Periodical |
| Magazine / Source | Information Processing Letters |
| MU Faculty or unit | |
| Citation | |
| web | http://dx.doi.org/10.1016/j.ipl.2008.04.002 |
| Keywords | formal languages, multi-parallel grammars, descriptional complexity |
| Description | 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. |