dc.creator | Gazdag, Zsolt | |
dc.creator | Gutiérrez Naranjo, Miguel Ángel | |
dc.date.accessioned | 2016-01-28T10:56:08Z | |
dc.date.available | 2016-01-28T10:56:08Z | |
dc.date.issued | 2014 | |
dc.identifier.isbn | 978-84-940056-4-0 | es |
dc.identifier.uri | http://hdl.handle.net/11441/33500 | |
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
belonging of NL to PMCMC, PMCAM0
+d
and PMCAM+ | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad TIN2012-37434 | |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Fénix Editora | es |
dc.relation.ispartof | Proceedings of the Twelfth Brainstorming Week on Membrane Computing, 207-220. Sevilla, E.T.S. de Ingeniería Informática, 3-7 de Febrero, 2014, | es |
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/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 | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 | |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | |
dc.identifier.idus | https://idus.us.es/xmlui/handle/11441/33500 | |
dc.contributor.funder | Ministerio de Economía y Competitividad (MINECO). España | |