dc.creator | Orellana Martín, David | es |
dc.creator | Valencia Cabrera, Luis | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.date.accessioned | 2022-06-30T07:49:03Z | |
dc.date.available | 2022-06-30T07:49:03Z | |
dc.date.issued | 2022 | |
dc.identifier.citation | Orellana Martín, D., Valencia Cabrera, L. y Pérez Jiménez, M.d.J. (2022). P systems with evolutional symport and membrane creation rules solving QSAT. Theoretical Computer Science, 908 (March 2022), 56-63. | |
dc.identifier.issn | 0304-3975 | es |
dc.identifier.uri | https://hdl.handle.net/11441/134814 | |
dc.description.abstract | P systems are computing devices based on sets of rules that dictate how they work.
While some of these rules can change the objects within the system, other rules can even
change the own structure, like creation rules. They have been used in cell-like membrane
systems with active membranes to efficiently solve NP-complete problems. In this work,
we improve a previous result where a uniform family of P systems with evolutional
communication rules whose left-hand side (respectively, right-hand side) have most 2
objects (resp., 2 objects) and membrane creation solved SAT efficiently, and we obtain
an efficient solution to solve QBF-SAT or QSAT (a PSPACE-complete problem) having at
most 1 object (respectively, 1 object) in their left-hand side (resp., right-hand side) and not
making use of the environment | es |
dc.description.sponsorship | Ministerio de Ciencia e Innovación TIN2017-89842-P | 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, 908 (March 2022), 56-63. | |
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 | Membrane creation | es |
dc.subject | QBF-SAT | es |
dc.subject | Computational complexity theory | es |
dc.title | P systems with evolutional symport and membrane creation rules solving QSAT | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | 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 | TIN2017-89842-P | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0304397521006873?via%3Dihub | es |
dc.identifier.doi | 10.1016/j.tcs.2021.11.012 | es |
dc.contributor.group | Universidad de Sevilla. TIC193 : Computación Natural | es |
dc.journaltitle | Theoretical Computer Science | es |
dc.publication.volumen | 908 | es |
dc.publication.issue | March 2022 | es |
dc.publication.initialPage | 56 | es |
dc.publication.endPage | 63 | es |
dc.contributor.funder | Ministerio de Ciencia e Innovación (MICIN). España | es |