Time-free solution to SAT problem using P systems with active membranes
Time-free solution to SAT problem using P systems with active membranes
复制标题
使用带有活性膜的 P 系统快速解决 SAT 问题
DOI：
10.1016/j.tcs.2013.11.014
复制
发表时间：
2014-04
影响因子：
1.1
通讯作者：
Luis F. Macías-Ramos
中科院分区：
文献类型：
--
作者：
Tao Song;Linqing Pan;Mario J. Perez-Jimenez;Luis F. Macías-Ramos
P 系统是一类受活细胞结构和功能启发的分布式并行计算模型。 P系统已被用来解决计算难题，其中每个规则的执行在单位时间内完成（假设全局时钟用于计时和同步规则的执行）。每个规则的执行只需要一个时间单位的假设对于系统同步工作起着至关重要的作用，它也被用来表征系统的计算效率和时间复杂度。在这项工作中，我们研究了没有这种时间假设的 P 系统的计算能力。具体来说，我们使用具有活性膜的 P 系统给出了 SAT 问题的无时间解决方案，从某种意义上说，解决方案的正确性不依赖于所涉及规则的精确计时。
P systems are a class of distributed and parallel computation models inspired by the structure and the functioning of living cells. P systems have been used to solve computation hard problems, where the execution of each rule is completed in unit time (a global clock is assumed for timing and synchronizing the execution of rules). The assumption that the execution of each rule takes exactly one time unit plays an vital role to make a system working synchronously, and it has also been used to characterize the computational efficiency and time complexity of a system. In this work, we investigate the computation power of P systems without such time assumption. Specifically, we give a time-free solution toSATproblem using P systems with active membranes in the sense that the correctness of the solution does not depend on the precise timing of the involved rules.
登录
查看更多内容
DOI：
10.1007/978-3-540-24619-0_19
发表时间：
2003-07
期刊：
--
影响因子：
--
作者：
M. Pérez-Jiménez;A. Riscos-Núñez
通讯作者：
M. Pérez-Jiménez;A. Riscos-Núñez
DOI：
--
发表时间：
1997-04
期刊：
The Journal of Immunology
影响因子：
--
作者：
G. Rozenberg;A. Salomaa
通讯作者：
G. Rozenberg;A. Salomaa
DOI：
10.1007/978-3-642-54239-8
发表时间：
2013
期刊：
--
影响因子：
--
作者：
A. Alhazov;Svetlana Cojocaru;Marian Gheorghe Yurii Rogozhin;Grzegorz Rozenberg Arto Salomaa
通讯作者：
A. Alhazov;Svetlana Cojocaru;Marian Gheorghe Yurii Rogozhin;Grzegorz Rozenberg Arto Salomaa
DOI：
10.1016/j.jpdc.2006.01.003
发表时间：
2006-06
期刊：
J. Parallel Distributed Comput.
影响因子：
--
作者：
L. Pan;C. Martín-Vide
通讯作者：
L. Pan;C. Martín-Vide
影响因子：
1.1
作者：
Martín-Vide, C;Paun, G;Rodríguez-Patón, A
通讯作者：
Rodríguez-Patón, A