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 two insertion nodes. 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 contextsensitive languages, and (up to an intersection with a monoid) every contextsensitive language can be generated by a network with one substitution node and one insertion node. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74593-8_14 | MCU |
Keywords | Field | DocType |
insertion node,recursively enumerable language,arbitrary number,deletion node,finite language,substitution node,contextsensitive language,evolutionary processor | Discrete mathematics,Combinatorics,Computer science,Recursively enumerable language,Monoid,Regular language | Conference |
Volume | ISSN | ISBN |
4664 | 0302-9743 | 3-540-74592-0 |
Citations | PageRank | References |
7 | 0.55 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jürgen Dassow | 1 | 530 | 118.27 |
| Bianca Truthe | 2 | 159 | 28.57 |