A time-free uniform solution to subset sum problem by tissue P systems with cell division
A time-free uniform solution to subset sum problem by tissue P systems with cell division
复制标题
DOI：
10.1017/s0960129515000018
复制
发表时间：
2015-02
影响因子：
0.5
通讯作者：
Bosheng Song;Tao Song;L. Pan
中科院分区：
文献类型：
--
作者：
Bosheng Song;Tao Song;L. Pan
组织P系统是一类受生物启发的计算模型，其动机是组织样排列中细胞之间的生化相互作用。具有细胞分裂的组织P系统提供了一种理论设备来生成指数增长结构，以便有效地解决计算困难的问题，假设存在全局时钟来标记系统的时间，每个规则的执行在精确的一个时间单位内完成。实际上，细胞中不同生化反应的执行时间取决于许多不确定因素。在这项工作中，这种生物学的灵感，我们删除了每个规则的执行时间的限制，和组织P系统的细胞分裂的计算效率进行了研究。具体地说，我们解决子集和问题的组织P系统与细胞分裂的时间无关的方式，在这个意义上说，该问题的解决方案的正确性不依赖于所涉及的规则的执行时间。
Tissue P systems are a class of bio-inspired computing models motivated by biochemical interactions between cells in a tissue-like arrangement. Tissue P systems with cell division offer a theoretical device to generate an exponentially growing structure in order to solve computationally hard problems efficiently with the assumption that there exists a global clock to mark the time for the system, the execution of each rule is completed in exactly one time unit. Actually, the execution time of different biochemical reactions in cells depends on many uncertain factors. In this work, with this biological inspiration, we remove the restriction on the execution time of each rule, and the computational efficiency of tissue P systems with cell division is investigated. Specifically, we solve subset sum problem by tissue P systems with cell division in a time-free manner in the sense that the correctness of the solution to the problem does not depend on the execution time of the involved rules.