Accepting hybrid networks of evolutionary processors with splicing rules and forbidding context

An accepting hybrid network of evolutionary processors (AH- NEP in short) consists of several language processors which are located in the nodes of a virtual graph and able to perform only one type of point mutations (insertion, deletion and substitution) on the words found in that node, according to some predefined rules. Each node is associated with an input and an output filter, defined by some random conditions. After applying in parallel a point mutation to all the words existing in every node, the new words which are able to pass the output filter of the respective node navigate simultaneously through the network and enter those nodes whose input filter they are able to pass. In this paper, we replace the point mutations in every node with splicing operation, which is a biologically inspired operation. Forbidding context is also added to the splicing rules, where we check for the absence of certain symbols before applying the splicing rules. The new model is called accepting hybrid networks of evolutionary processors with splicing rules and forbidding context (AHNEPSF in short). Algorithms are proposed to two much celebrated NP-complete problems, namely the 3CNF-SAT and the directed Hamiltonian Path Problem (HPP). These algorithms working parallely on AHNEPSF takes linear time. All other resources (size, number of rules and symbols) are also linearly bounded by the size of the given instance of the problem. It is shown that the time for solving HPP does not depend on the number of edges of the given graph. Also, the algorithm that is given here for solving 3CNF-SAT provide all solutions, if any of the given instance of 3CNF-SAT. Copyright © IICAI 2005.