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

Jürgen Dassow
(Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik)
Florin Manea
(Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik)

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.

In Ian McQuillan and Giovanni Pighizzini: Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (DCFS 2010), Saskatoon, Canada, 8-10th August 2010, Electronic Proceedings in Theoretical Computer Science 31, pp. 68–77.
Published: 7th August 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.31.9 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org