Computer Science – Computational Complexity
Scientific paper
2010-08-10
EPTCS 31, 2010, pp. 68-77
Computer Science
Computational Complexity
In Proceedings DCFS 2010, arXiv:1008.1270
Scientific paper
10.4204/EPTCS.31.9
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.
Dassow Jürgen
Manea Florin
No associations
LandOfFree
Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accepting Hybrid Networks of Evolutionary Processors with Special Topologies and Small Communication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-583254