dc.creator | Orellana Martín, David | es |
dc.creator | Martínez del Amor, Miguel Ángel | es |
dc.creator | Valencia Cabrera, Luis | es |
dc.creator | Song, Bosheng | es |
dc.creator | Pan, Linqiang | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.date.accessioned | 2018-06-13T10:48:42Z | |
dc.date.available | 2018-06-13T10:48:42Z | |
dc.date.issued | 2018-05-01 | |
dc.identifier.citation | Orellana Martín, D., Martínez del Amor, M.Á., Valencia Cabrera, L., Song, B., Pan, L. y Pérez Jiménez, M.d.J. (2018). P systems with symport/antiport rules: When do the surroundings matter?. Theoretical Computer Science | |
dc.identifier.issn | 0304-3975 | es |
dc.identifier.uri | https://hdl.handle.net/11441/76120 | |
dc.description.abstract | Cell-like P systems where communication between the regions are carried out by rules of type symport/antiport are considered. These systems compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves. The environment plays an active role in the sense that it not only can receive objects from the system, but also send objects into it. There is an alphabet associated with the environment whose elements appear in an arbitrary large number of copies at the initial configuration. This property seems too strong from a complexity view, but it has been widely exploited in the design of efficient solutions to computationally hard problems when some mechanisms (inspired by mitosis and membrane fission) allowing to construct an exponential workspace in linear time, are considered. In this paper, complexity aspects of P systems with symport/antiport rules and membrane division are considered when the set associated with the environment is the emptyset. It is shown that the role of the environment is irrelevant for such kind of P systems, in contrast with the well known results concerning to its relevance when membrane separation is used instead of membrane division. | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad TIN2017-89842-P | es |
dc.description.sponsorship | National Natural Science Foundation of China 61320106005 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Theoretical Computer Science | |
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 with Symport/Antiport | es |
dc.subject | Membrane Division | es |
dc.subject | Computational Complexity | es |
dc.title | P systems with symport/antiport rules: When do the surroundings matter? | 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 | TIN2017-89842-P | es |
dc.relation.projectID | 61320106005 | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0304397518303062 | es |
dc.identifier.doi | 10.1016/j.tcs.2018.04.052 | es |
dc.contributor.group | Universidad de Sevilla TIC193: Computacion Natural | es |
idus.format.extent | 26 | es |
dc.journaltitle | Theoretical Computer Science | es |
dc.contributor.funder | Ministerio de Economía y Competitividad (MINECO). España | |
dc.contributor.funder | National Natural Science Foundation of China | |