On Networks of Evolutionary Processors with Nodes of Two Types

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.