We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Hybrid networks of evolutionary processors are computationally complete.
- Authors
Csuhaj-Varjú, Erzsébet; Martín-Vide, Carlos; Mitrana, Victor
- Abstract
A hybrid network of evolutionary processors (an HNEP) consists of several language processors which are located in the nodes of a virtual graph and able to perform only one type of point mutations (insertion, deletion, substitution) on the words found in that node, according to some predefined rules. Each node is associated with an input and an output filter, defined by some random-context conditions. After applying in parallel a point mutation to all the words existing in every node, the new words which are able to pass the output filter of the respective node navigate simultaneously through the network and enter those nodes whose input filter they are able to pass. We show that even the so-called elementary HNEPs are computationally complete. In this case every node is able to perform only one instance of the specified operation: either an insertion, or a deletion, or a substitution of a certain symbol. We also prove that in the case of non-elementary networks, any recursively enumerable language over a common alphabet can be obtained with an HNEP whose underlying structure is a fixed graph depending on the common alphabet only.
- Subjects
EVOLUTIONARY computation; COMPUTER programming; COMPUTER software; COMPUTER networks; ARTIFICIAL languages
- Publication
Acta Informatica, 2005, Vol 41, Issue 4/5, p257
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-004-0158-7