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

R Freund, Vladimir Rogojin, S Verlan

    Forskningsoutput: TidskriftsbidragArtikelVetenskapligPeer review

    1 Citeringar (Scopus)


    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.
    Sidor (från-till)1005–1027
    Antal sidor23
    TidskriftInternational Journal of Foundations of Computer Science
    StatusPublicerad - 2019
    MoE-publikationstypA1 Tidskriftsartikel-refererad

    Citera det här