Abstract
In this paper, we consider the computational power of a new variant of networks of evolutionary processors which seems to be more suitable for a software and hardware implementation. Each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined, the data polarization is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that tag systems can be simulated by these networks with a constant number of nodes, while Turing machines can be simulated, in a time-efficient way, by these networks with a number of nodes depending linearly on the tape alphabet of the Turing machine.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alarcón, P., Arroyo, F., Mitrana, V.: Networks of polarized evolutionary processors as problem solvers. In: Advances in Knowledge-Based and Intelligent Information and Engineering Systems. Frontiers in Artificial Intelligence and Applications, pp. 807–815. IOS Press (2012)
Castellanos, J., Martín-Vide, C., Mitrana, V., Sempere, J.M.: Networks of evolutionary processors. Acta Inf. 39, 517–529 (2003)
Díaz, M.A., de Mingo, L.F., Blas, N.G., Castellanos, J.: Implementation of massive parallel networks of evolutionary processors (MPNEP): 3-colorability problem. In: Krasnogor, N., Nicosia, G., Pavone, M., Pelta, D. (eds.) Nature Inspired Cooperative Strategies for Optimization (NICSO 2007). SCI, vol. 129, pp. 399–408. Springer, Heidelberg (2008)
Diaz, M.A., de Mingo, L.F., Gómez, N.: Networks of evolutionary processors: Java Implementation of a threaded processor. International Journal of Information Theories & Applications 15, 37–43 (2008)
Drăgoi, C., Manea, F., Mitrana, V.: Accepting networks of evolutionary processors with filtered connections. J. UCS 13, 1598–1614 (2007)
Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 533–546 (1965)
Hillis, W.D.: The Connection Machine. MIT Press, Cambridge (1979)
Loos, R., Manea, F., Mitrana, V.: Small universal accepting hybrid networks of evolutionary processors. Acta Inf. 47, 133–146 (2010)
Manea, F., Martín-Vide, C., Mitrana, V.: On the size complexity of universal accepting hybrid networks of evolutionary processors. Mathematical Structures in Computer Science 17, 753–771 (2007)
Manea, F., Margenstern, M., Mitrana, V., Pérez-Jiménez, M.J.: A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors. Theory Comput. Syst. 46, 174–192 (2010)
Manea, F., Martín-Vide, C., Mitrana, V.: Accepting networks of evolutionary word and picture processors: A survey. In: Scientific Applications of Language Methods, Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory, vol. 2, pp. 523–560. World Scientific (2010)
Margenstern, M., Mitrana, V., Pérez-Jímenez, M.J.: Accepting Hybrid Networks of Evolutionary Processors. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 235–246. Springer, Heidelberg (2005)
Martín-Vide, C., Pazos, J., Păun, G., Rodríguez-Patón, A.: A new class of symbolic abstract neural nets: Tissue P systems. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 290–299. Springer, Heidelberg (2002)
Martín-Vide, C., Mitrana, V., Pérez-Jiménez, M.J., Sancho-Caparrini, F.: Hybrid networks of evolutionary processors. In: Cantú-Paz, E., et al. (eds.) GECCO 2003. LNCS, vol. 2723, pp. 401–412. Springer, Heidelberg (2003)
Minsky, M.L.: Size and structure of universal Turing machines using tag systems. In: Recursive Function Theory, Symp. in Pure Mathematics, vol. 5, pp. 229–238 (1962)
Navarrete, C.B., Echeanda, M., Anguiano, E., Ortega, A., Rojas, J.M.: Parallel simulation of NEPs on clusters. In: Proc. IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - WI-IAT, pp. 171–174. IEEE Computer Society (2011)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)
Post, E.L.: Formal reductions of the general combinatorial decision problem. Amer. J. Math. 65, 197–215 (1943)
Păun, G.: Membrane computing. An introduction. Springer, Berlin (2002)
Rogozhin, Y.: Small universal Turing machines. Theoret. Comput. Sci. 168, 215–240 (1996)
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. I-III. Springer, Berlin (1997)
Sankoff, D., et al.: Gene order comparisons for phylogenetic inference:evolution of the mitochondrial genome. Proceedings of the National Academy of Sciences of the United States of America 89, 6575–6579 (1992)
Woods, D., Neary, T.: On the time complexity of 2-tag systems and small universal Turing machines. In: 47th Annual IEEE Symposium on Foundations of Computer Science FOCS 2006, pp. 439–448 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Arroyo, F., Gómez Canaval, S., Mitrana, V., Popescu, Ş. (2014). Networks of Polarized Evolutionary Processors Are Computationally Complete. In: Dediu, AH., Martín-Vide, C., Sierra-Rodríguez, JL., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2014. Lecture Notes in Computer Science, vol 8370. Springer, Cham. https://doi.org/10.1007/978-3-319-04921-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-04921-2_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04920-5
Online ISBN: 978-3-319-04921-2
eBook Packages: Computer ScienceComputer Science (R0)