dc.creator | Gazdag, Zsolt | es |
dc.creator | Gutiérrez Naranjo, Miguel Ángel | es |
dc.date.accessioned | 2018-04-12T09:20:03Z | |
dc.date.available | 2018-04-12T09:20:03Z | |
dc.date.issued | 2014 | |
dc.identifier.citation | Gazdag, Z. y Gutiérrez Naranjo, M.Á. (2014). Solving the ST-Connectivity Problem with Pure Membrane Computing Techniques. En CMC 2014: 15th International Conference on Membrane Computing (215-228), Prague, Czech Republic: Springer. | |
dc.identifier.isbn | 978-3-319-14369-9 | es |
dc.identifier.issn | 0302-9743 | es |
dc.identifier.uri | https://hdl.handle.net/11441/72582 | |
dc.description.abstract | In Membrane Computing, the solution of a decision problem
X belonging to the complexity class P via a polynomially uniform family
of recognizer P systems is trivial, since the polynomial encoding of the
input can involve the solution of the problem. The design of such solution
has one membrane, two objects, two rules and one computation step.
Stricto sensu, it is a solution in the framework of Membrane Computing,
but it does not use Membrane Computing strategies. In this paper, we
present three designs of uniform families of P systems that solve the decision
problem STCON by using Membrane Computing strategies (pure
Membrane Computing techniques): P systems with membrane creation,
P systems with active membranes with dissolution and without polarizations
and P systems with active membranes without dissolution and
with polarizations. Since STCON is NL-complete, such designs are constructive
proofs of the inclusion of NL in PMCMC, PMCAM0
+d
and
PMCAM+
−d
. | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad TIN2012-37434 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Springer | es |
dc.relation.ispartof | CMC 2014: 15th International Conference on Membrane Computing (2014), p 215-228 | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Solving the ST-Connectivity Problem with Pure Membrane Computing Techniques | es |
dc.type | info:eu-repo/semantics/conferenceObject | 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 | TIN2012-37434 | es |
dc.relation.publisherversion | https://link.springer.com/chapter/10.1007/978-3-319-14370-5_13 | es |
dc.identifier.doi | 10.1007/978-3-319-14370-5_13 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 14 | es |
dc.publication.initialPage | 215 | es |
dc.publication.endPage | 228 | es |
dc.eventtitle | CMC 2014: 15th International Conference on Membrane Computing | es |
dc.eventinstitution | Prague, Czech Republic | es |
dc.relation.publicationplace | Berlín | es |
dc.identifier.sisius | 21266016 | es |
dc.contributor.funder | Ministerio de Economía y Competitividad (MINECO). España | |