Publication details
On the Descriptional Complexity of Scattered Context Grammars
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Periodical |
| Magazine / Source | Theoretical Computer Science |
| MU Faculty or unit | |
| Citation | |
| web | http://dx.doi.org/10.1016/j.tcs.2008.10.017 |
| Keywords | scattered context grammar; descriptional complexity |
| Description | This paper proves that every recursively enumerable language is generated by a scattered context grammar with no more than four nonterminals and three non-context-free productions. In its conclusion, it gives an overview of the results and open problems concerning scattered context grammars and languages. |