Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.dam.2004.06.011 | Discrete Applied Mathematics |
Keywords | Field | DocType |
recursively enumerable language,context-free component,evolutionary system,acta inform,formal language | Discrete mathematics,Context-free language,Combinatorics,Formal language,Maximal set,Recursively enumerable set,Recursively enumerable language,Evolutionary systems,Cone (formal languages),Unrestricted grammar,Mathematics | Journal |
Volume | Issue | ISSN |
146 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erzsébet Csuhaj-Varjú | 1 | 593 | 87.27 |
| Jürgen Dassow | 2 | 530 | 118.27 |