Header menu link for other important links
Network of evolutionary processors with splicing rules and forbidding context
Ashish Choudhary, Kamala Krithivasan
Published in
Volume: 3561
Issue: PART I
Pages: 300 - 309
In this paper we consider networks of evolutionary processors with splicing rules and forbidding context (NEPFS) 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. Before applying the splicing operation on words, we check for the absence of certain symbols (forbidding context) in the strings on which the rule is applied. Each node is associated with an input and output filter. When the filters are based on random context conditions, 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. © Springer-Verlag Berlin Heidelberg 2005.
About the journal
JournalLecture Notes in Computer Science
Open AccessNo
Concepts (7)
  •  related image
    Graph theory
  •  related image
    Linear systems
  •  related image
    Problem solving
  •  related image
    Computational power
  •  related image
  •  related image
  •  related image
    Computation theory