Tissue P systems
Tissue P systems
复制标题
DOI：
10.1016/s0304-3975(02)00659-x
复制
发表时间：
2003-03-08
影响因子：
1.1
通讯作者：
Rodríguez-Patón, A
中科院分区：
文献类型：
--
作者：
Martín-Vide, C;Paun, G;Rodríguez-Patón, A
从细胞间通信通过蛋白质通道发生的方式（以及关于神经元功能的标准知识）出发，我们提出了一种称为组织P系统的计算模型，该模型在细胞网络中以多集重写意义处理符号。每个细胞都有一个有限的状态记忆，处理多组符号脉冲，并可以发送脉冲（“激励”）到相邻的细胞。这样的细胞网络被证明是相当强大的：即使使用少量的细胞，它们中的每一个都有少量的状态，它们也可以模拟图灵机。此外，在每个细胞以最大方式工作并且它可以激励它可以发送脉冲的所有细胞的情况下，那么可以容易地在线性时间内解决Hamilton路径问题。在此框架下，还得到了ET0L语言的Parikh象的一个新的刻画。在此基础上，本文还对今后的研究提出了一系列建议。(C)2002 Elsevier Science B.V.保留所有权利。
Starting from the way the inter-cellular communication takes place by means of protein channels (and also from the standard knowledge about neuron, functioning), we propose a computing model called a tissue P system, which processes symbols in a multiset rewriting sense, in a net of cells. Each cell has a finite state memory, processes multisets of symbol-impulses, and can send impulses ("excitations") to the neighboring cells. Such cell nets are shown to be rather powerful: they can simulate a Turing machine even when using a small number of cells, each of them having a small number of states. Moreover, in the case when each cell works in the maximal manner and it can excite all the cells to which it can send impulses, then one can easily solve the Hamiltonian Path Problem in linear time. A new characterization of the Parikh images of ET0L languages is also obtained in this framework. Besides such basic results, the paper provides a series of suggestions for further research. (C) 2002 Elsevier Science B.V. All rights reserved.