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

R Freund, Vladimir Rogojin, S Verlan

    Research output: Contribution to journalArticleScientificpeer-review

    1 Citation (Scopus)

    Abstract

    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.
    Original languageUndefined/Unknown
    Pages (from-to)1005–1027
    Number of pages23
    JournalInternational Journal of Foundations of Computer Science
    Volume30
    DOIs
    Publication statusPublished - 2019
    MoE publication typeA1 Journal article-refereed

    Cite this