期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2010
卷号：31
页码：68-77
DOI：10.4204/EPTCS.31.9
出版社：Open Publishing Association
摘要：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. We also present bounds for the size of these star and grid networks. As a consequence we get that each recursively enumerable can be accepted by networks with at most 13 communication channels and by networks where each node communicates with at most three other nodes.
