Choudhary Ashish, Krithivasan Kamala
Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai 600036, India.
Biosystems. 2007 Feb;87(2-3):111-6. doi: 10.1016/j.biosystems.2006.09.003. Epub 2006 Sep 7.
In this paper we consider networks of evolutionary processors with splicing rules and permitting context (NEPPS) 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 presence of certain symbols (permitting 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.
在本文中，我们将具有剪接规则和允许上下文的进化处理器网络（NEPPS）视为语言生成和计算设备。这样的网络由放置在虚拟图节点上的多个处理器组成，并且能够根据该节点中存在的剪接规则对该节点中存在的单词执行剪接（这是一种受生物学启发的操作）。在对单词应用剪接操作之前，我们会检查应用该规则的字符串中是否存在某些符号（允许上下文）。每个节点都与一个输入和输出过滤器相关联。当过滤器基于随机上下文条件时，使用大小为二的网络可获得图灵机的计算能力。我们还展示了如何使用这些网络在线性时间内解决NP完全问题。
