JUCS - Journal of Universal Computer Science 13(11): 1598-1614, doi: 10.3217/jucs-013-11-1598
Accepting Networks of Evolutionary Processors with Filtered Connections
Cezara Drăgoi‡, Florin Manea‡, Victor Mitrana‡‡ University of Bucharest, Bucharest, Romania
Corresponding author: Cezara Drăgoi ( dragoi.cezara@gmail.com ) © Cezara Drăgoi, Florin Manea, Victor Mitrana. This article is freely available under the J.UCS Open Content License. Citation:
Drăgoi C, Manea F, Mitrana V (2007) Accepting Networks of Evolutionary Processors with Filtered Connections. JUCS - Journal of Universal Computer Science 13(11): 1598-1614. https://doi.org/10.3217/jucs-013-11-1598 |  |
Abstract
In this paper we simplify a recent model of computation considered in [Margenstern et al. 2005], namely accepting network of evolutionary processors, by moving the filters from the nodes to the edges. Each edge is viewed as a two-way channel such that input and output filters, respectively, of the two nodes connected by the edge coincide. Thus, the possibility of controlling the computation in such networks seems to be diminished. In spite of this observation these simplified networks have the same computational power as accepting networks of evolutionary processors, that is they are computationally complete. As a consequence, we propose characterizations of two complexity classes, namely NP and PSPACE, in terms of accepting networks of evolutionary processors with filtered connections.
Keywords
evolutionary processor, network of evolutionary processors, Turing machine, complexity class