Variants of Networks of Evolutionary Processors with Polarizations and a Small Number of Processors

A1 Originalartikel i en vetenskaplig tidskrift (referentgranskad)


Interna författare/redaktörer


Publikationens författare: Freund R, Rogojin V, Verlan S
Förläggare: WORLD SCIENTIFIC PUBL CO PTE LTD
Publiceringsår: 2019
Tidskrift: International Journal of Foundations of Computer Science
Tidskriftsakronym: INT J FOUND COMPUT S
Volym: 30
Artikelns första sida, sidnummer: 1005
Artikelns sista sida, sidnummer: 1027
Antal sidor: 23
ISSN: 0129-0541


Abstrakt

We improve previous results obtained for networks of evolutionary processors-using the operations insertion, deletion, and substitution on strings - with elementary polarizations -0, 1 by showing that only seven processors are needed to obtain computational completeness. In the case of not requiring a special output node, only five processors are shown to be sufficient. We also prove that if the communication structure is allowed to be a directed graph without self-loops, then two polarizations are sufficient (with 12 or 17 nodes, depending on the definition). Moreover, we consider the case of not restricting the number of polarizations, thus obtaining the minimal number of three nodes for hybrid systems and even only one node where all three operations can be carried out.

Senast uppdaterad 2020-10-04 vid 05:20