View Related Documents

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.
Received: 19 July 2004, Published online: 19 January 2005
Erzsébet Csuhaj-Varjú: Work supported in part by a grant from the NATO Scientific Committee in Spain and the Hungarian Scientific Research Fund ldquoOTKArdquo Grant No. T 042529
Victor Mitrana: Work supported by the Centre of Excellence in Information Technology, Computer Science and Control, ICA1-CT-2000-70025, HUN-TING project, WP5.

Fulltext Preview

Image of the first page of the fulltext document