Affiliations: Åbo Akademi University, Dept. of Information
Technologies, Turku Center for Comp.Sc., FIN-20520 Turku, Finland. [email protected], [email protected] | Rovira i Virgili University, Research Group on
Mathematical Linguistics, Pl.Imperial Tàrraco 1, E-43005 Tarragona, Spain.
[email protected] | Otto-von-Guericke-Universität Magdeburg,
Fakultät für Informatik, PSF 4120, D-39016 Magdeburg,
Germany. [email protected] | Otto-von-Guericke-Universität Magdeburg,
Fakultät für Informatik, PSF 4120, D-39016 Magdeburg,
Germany. [email protected] | Academy of Sciences of Moldova, Institute of
Mathematics and Comp.Sc., Academiei 5, MD-2028, Chişinău, Moldova.
[email protected]
Note: [] Address for correspondence: Åbo Akademi
University, Dept. of Information Technologies, Turku Center for Comp.Sc., FIN-
20520 Turku, Finland
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.
