Jürgen Dassow

  1. Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication.

    Authors: Jürgen Dassow, Florin Manea
    Subjects: Computational Complexity
    Abstract

    Starting from the fact that complete Accepting Hybrid Networks of
    Evolutionary Processors allow much communication between the nodes and are far
    from network structures used in practice, we propose in this paper three
    network topologies that restrict the communication: star networks, ring
    networks, and grid networks. We show that ring-AHNEPs can simulate 2-tag
    systems, thus we deduce the existence of a universal ring-AHNEP. For star
    networks or grid networks, we show a more general result; that is, each
    recursively enumerable language can be accepted efficiently by a star- or
    grid-AHNEP.

Syndicate content