Name
Abstract | ||
|---|---|---|
We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.3233/FI-2009-0030 | Fundam. Inform. |
Keywords | Field | DocType |
insertion node,recursively enumerable language,arbitrary number,deletion node,finite language,context-sensitive language,substitution node,evolutionary processors,evolutionary processor,insertion,network,networks,substitution,recursively enumerable languages | Discrete mathematics,Combinatorics,Computer science,Recursively enumerable language,Monoid | Journal |
Volume | Issue | ISSN |
91 | 1 | 0169-2968 |
Citations | PageRank | References |
22 | 1.11 | 9 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Artiom Alhazov | 1 | 642 | 68.17 |
| Carlos Martín-Vide | 2 | 1079 | 129.06 |
| Bianca Truthe | 3 | 159 | 28.57 |
| Jürgen Dassow | 4 | 530 | 118.27 |
| Yurii Rogozhin | 5 | 517 | 49.01 |