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

R Freund, Vladimir Rogojin, S Verlan

    Tutkimustuotos: LehtiartikkeliArtikkeliTieteellinenvertaisarvioitu

    1 Sitaatiot (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.
    AlkuperäiskieliEi tiedossa
    JulkaisuInternational Journal of Foundations of Computer Science
    DOI - pysyväislinkit
    TilaJulkaistu - 2019
    OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu