Ponencia
Solving the ST-Connectivity Problem with Pure Membrane Computing Techniques
Autor/es | Gazdag, Zsolt
Gutiérrez Naranjo, Miguel Ángel |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2014 |
Fecha de depósito | 2018-04-12 |
Publicado en |
|
ISBN/ISSN | 978-3-319-14369-9 0302-9743 |
Resumen | 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 ... 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 . |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | TIN2012-37434 |
Cita | 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Solving the ST-Connectivity.pdf | 263.4Kb | [PDF] | Ver/ | |