dc.creator | Song, Tao | es |
dc.creator | Macías Ramos, Luis Felipe | es |
dc.creator | Pan, Linqiang | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.date.accessioned | 2021-07-22T10:31:02Z | |
dc.date.available | 2021-07-22T10:31:02Z | |
dc.date.issued | 2014 | |
dc.identifier.citation | 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. | |
dc.identifier.issn | 0304-3975 | es |
dc.identifier.uri | https://hdl.handle.net/11441/116364 | |
dc.description.abstract | 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. | es |
dc.description.sponsorship | National Natural Science Foundation of China No. 61033003 | es |
dc.description.sponsorship | National Natural Science Foundation of China No. 91130034 | es |
dc.description.sponsorship | National Natural Science Foundation of China No. 61100145 | es |
dc.description.sponsorship | National Natural Science Foundation of China No. 61272071 | es |
dc.description.sponsorship | National Natural Science Foundation of China No 61320106005 | es |
dc.description.sponsorship | Ministry of Education of China 20100142110072 | es |
dc.description.sponsorship | Ministry of Education of China 2012014213008 | es |
dc.description.sponsorship | Natural Science Foundation of Hubei Province 2011CDA027 | es |
dc.format | application/pdf | es |
dc.format.extent | 8 | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Theoretical Computer Science, 529 (April 2014), 61-68. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Membrane Computing | es |
dc.subject | P System | es |
dc.subject | Time-free solution | es |
dc.subject | Semi-uniform solution | es |
dc.subject | NP-complete problem | es |
dc.title | Time-free solution to SAT problem using P systems with active membranes | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.relation.projectID | No. 61033003 | es |
dc.relation.projectID | No. 91130034 | es |
dc.relation.projectID | No. 61100145 | es |
dc.relation.projectID | No. 61272071 | es |
dc.relation.projectID | No 61320106005 | es |
dc.relation.projectID | 20100142110072 | es |
dc.relation.projectID | 2012014213008 | es |
dc.relation.projectID | 2011CDA027 | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0304397513008451 | es |
dc.identifier.doi | 10.1016/j.tcs.2013.11.014 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
dc.journaltitle | Theoretical Computer Science | es |
dc.publication.volumen | 529 | es |
dc.publication.issue | April 2014 | es |
dc.publication.initialPage | 61 | es |
dc.publication.endPage | 68 | es |
dc.identifier.sisius | 20575818 | es |
dc.contributor.funder | National Natural Science Foundation of China | es |
dc.contributor.funder | Ministry of Education of China | es |
dc.contributor.funder | Natural Science Foundation of Hubei Province | es |