Repositorio de producción científica de la Universidad de Sevilla

Solving the ST-Connectivity Problem with Pure Membrane Computing Techniques

Opened Access Solving the ST-Connectivity Problem with Pure Membrane Computing Techniques
Estadísticas
Icon
Exportar a
Autor: Gazdag, Zsolt
Gutiérrez Naranjo, Miguel Ángel
Departamento: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Fecha: 2014
Publicado en: 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,
ISBN/ISSN: 978-84-940056-4-0
Tipo de documento: Ponencia
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 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+ 􀀀��d .
Tamaño: 117.2Kb
Formato: PDF

URI: http://hdl.handle.net/11441/33500

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones