Artículo
Time-free solution to SAT problem using P systems with active membranes
Autor/es | Song, Tao
Macías Ramos, Luis Felipe Pan, Linqiang Pérez Jiménez, Mario de Jesús |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2014 |
Fecha de depósito | 2021-07-22 |
Publicado en |
|
Resumen | 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 ... 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 to SAT problem 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. |
Agencias financiadoras | National Natural Science Foundation of China Ministry of Education of China Natural Science Foundation of Hubei Province |
Identificador del proyecto | No. 61033003
No. 91130034 No. 61100145 No. 61272071 No 61320106005 20100142110072 2012014213008 2011CDA027 |
Cita | Song, T., Macías Ramos, L.F., Pan, L. y Pérez Jiménez, M.d.J. (2014). Time-free solution to SAT problem using P systems with active membranes. Theoretical Computer Science, 529 (April 2014), 61-68. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Time-free solution to SAT problem ... | 315.2Kb | [PDF] | Ver/ | |