dc.creator | Ciobanu, Gabriel | es |
dc.creator | Pan, Linqiang | es |
dc.creator | Paun, Gheorghe | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.date.accessioned | 2017-12-22T08:13:32Z | |
dc.date.available | 2017-12-22T08:13:32Z | |
dc.date.issued | 2007 | |
dc.identifier.citation | Ciobanu, G., Pan, L., Paun, G. y Pérez Jiménez, M.d.J. (2007). P systems with minimal parallelism. Theoretical Computer Science, 378 (1), 117-130. | |
dc.identifier.issn | 0304-3975 | es |
dc.identifier.uri | http://hdl.handle.net/11441/67973 | |
dc.description.abstract | A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one
target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this
issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or
a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more
rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first
prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter
case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results
are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time). | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Theoretical Computer Science, 378 (1), 117-130. | |
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 | SAT problem | es |
dc.title | P systems with minimal parallelism | 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.publisherversion | http://www.sciencedirect.com/science/article/pii/S0304397507002459 | es |
dc.identifier.doi | 10.1016/j.tcs.2007.03.044 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 14 | es |
dc.journaltitle | Theoretical Computer Science | es |
dc.publication.volumen | 378 | es |
dc.publication.issue | 1 | es |
dc.publication.initialPage | 117 | es |
dc.publication.endPage | 130 | es |
dc.identifier.sisius | 6651355 | es |