TY - JOUR
T1 - Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors
AU - Alhazov, Artiom
AU - Freund, Rudolf
AU - Rogozhin, Vladimir
AU - Rogojin, Vladimir
PY - 2016
Y1 - 2016
N2 - A hybrid network of evolutionary processors (HNEP) is a graph where each node is associated with a special rewriting system called an evolutionary processor, an input filter, and an output filter. Each evolutionary processor is given a finite set of one type of point mutations (insertion, deletion or a substitution of a symbol) which can be applied to certain positions in a string. An HNEP rewrites the strings in the nodes and then re-distributes them according to a filter-based communication protocol; the filters are defined by certain variants of random-context conditions. HNEPs can be considered both as languages generating devices (GHNEPs) and language accepting devices (AHNEPs); most previous approaches treated the accepting and generating cases separately. For both cases, in this paper we show that five nodes are sufficient to accept (AHNEPs) or generate (GHNEPs) any recursively enumerable language by showing the more general result that any partial recursive relation can be computed by an HNEP with (at most) five nodes with the underlying graph structure for the communication between the evolutionary processors being the complete or the linear graph with five nodes, whereas with a star-like communication graph we need six nodes. If the final results are defined by only taking the terminal strings out of the designated output node, then for these extended HNEPs we can prove that only four nodes are needed in all cases-for computing any partial recursive relation as well as for generating and accepting any recursively enumerable language-and the underlying communication structure can be a complete or a linear graph, but now even a star-like graph, too.
AB - A hybrid network of evolutionary processors (HNEP) is a graph where each node is associated with a special rewriting system called an evolutionary processor, an input filter, and an output filter. Each evolutionary processor is given a finite set of one type of point mutations (insertion, deletion or a substitution of a symbol) which can be applied to certain positions in a string. An HNEP rewrites the strings in the nodes and then re-distributes them according to a filter-based communication protocol; the filters are defined by certain variants of random-context conditions. HNEPs can be considered both as languages generating devices (GHNEPs) and language accepting devices (AHNEPs); most previous approaches treated the accepting and generating cases separately. For both cases, in this paper we show that five nodes are sufficient to accept (AHNEPs) or generate (GHNEPs) any recursively enumerable language by showing the more general result that any partial recursive relation can be computed by an HNEP with (at most) five nodes with the underlying graph structure for the communication between the evolutionary processors being the complete or the linear graph with five nodes, whereas with a star-like communication graph we need six nodes. If the final results are defined by only taking the terminal strings out of the designated output node, then for these extended HNEPs we can prove that only four nodes are needed in all cases-for computing any partial recursive relation as well as for generating and accepting any recursively enumerable language-and the underlying communication structure can be a complete or a linear graph, but now even a star-like graph, too.
KW - Circular Post machines
KW - Communication graph
KW - Computational completeness
KW - Hybrid networks of evolutionary processors
KW - Circular Post machines
KW - Communication graph
KW - Computational completeness
KW - Hybrid networks of evolutionary processors
KW - Circular Post machines
KW - Communication graph
KW - Computational completeness
KW - Hybrid networks of evolutionary processors
U2 - 10.1007/s11047-015-9534-1
DO - 10.1007/s11047-015-9534-1
M3 - Artikel
SN - 1567-7818
VL - 15
SP - 51
EP - 68
JO - Natural Computing
JF - Natural Computing
IS - 1
ER -