| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10328518 | Discrete Applied Mathematics | 2005 | 5 Pages |
Abstract
Evolutionary systems have been introduced by Csuhaj-Varjú and Mitrana (Acta Inform. 36 (2000) 913) who proved that two context-sensitive or three context-free components are sufficient to obtain all recursively enumerable languages. We improve these results by showing that two context-free components are sufficient to generate all recursively enumerable languages. Furthermore, we study the power of systems with one component.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Erzsébet Csuhaj-Varjú, Jürgen Dassow,