Abstract
In this paper we consider networks of evolutionary processors with splicing rules (NEPS) as language generating and computational devices. Such a network consists of several processors placed on the nodes of a virtual graph and are able to perform splicing (which is a biologically motivated operation) on the words present in that node, according to the splicing rules present there. Each node is associated with an input and output filter. When the filters are regular languages one gets the computational power of Turing machines with networks of size two. We also show how these networks can be used to solve NP–complete problems in linear time.
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
Castellanos, J., Martin-Vide, C., Mitrana, V., Sempere, J.: Networks of evolutionary processors. Acta Informatica 39, 517–529 (2003)
Csuhaj-Varju, E., Dassow, J., Keleman, J., Păun, G.: Grammar Systems: A Grammatical Approach to Distribution and Cooperation. Gordon and Breach, London (1994)
Csuhaj-Varju, E., Kari, L., Păun, G.: Test tube distributed systems based on splicing. Computers and AI 15(2-3), 211–232 (1996)
Csuhaj-Varju, E., Salomaa, A.: Networks of parallel language processors. In: New Trends in Formal Languages, pp. 299–318 (1997)
Errico, L., Jesshope, C.: Towards a new architecture for symbolic processing. In: Artificial Intelligence and Information Control Systems of Robots 1994, pp. 31–40 (1994)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Gibbons, A.M.: Algorithmic Graph Theory. Cambridge University Press, Cambridge (1985)
Hillis, W.D.: The Connection Machine. MIT Press, Cambridge (1985)
Krithivasan, K., Sakthi Balan, M., Harsha, P.: Distributed processing in automata. International Journal of Foundation of Computer Science 10(4), 443–464 (1999)
Păun, G.: Computing with membranes. Journal of Computer and System Sciencea 61(1), 108–143 (2000)
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Choudhary, A., Krithivasan, K. (2005). Network of Evolutionary Processors with Splicing Rules. In: Mira, J., Álvarez, J.R. (eds) Mechanisms, Symbols, and Models Underlying Cognition. IWINAC 2005. Lecture Notes in Computer Science, vol 3561. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11499220_30
Download citation
DOI: https://doi.org/10.1007/11499220_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26298-5
Online ISBN: 978-3-540-31672-5
eBook Packages: Computer ScienceComputer Science (R0)