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

Antimatter as a Frontier of Tractability in Membrane Computing

Opened Access Antimatter as a Frontier of Tractability in Membrane Computing
Estadísticas
Icon
Exportar a
Autor: Díaz Pernil, Daniel
Peña Cantillana, Francisco
Gutiérrez Naranjo, Miguel Ángel
Departamento: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Fecha: 2014
Publicado en: Proceedings of the Twelfth Brainstorming Week on Membrane Computing, 155-168. 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: It is well known that the polynomial complexity class of recognizer polarizationless P systems with active membranes, without dissolution and with division for elementary and non-elementary membranes is exactly the complexity class P (see [6], Th. 2). In this paper, we prove that if such P system model is endowed with antimatter and annihilation rules, then NP problems can be solved. In this way, antimatter is a frontier of tractability in Membrane Computing.
Tamaño: 104.2Kb
Formato: PDF

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

Mostrar el registro completo del ítem


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

Este registro aparece en las siguientes colecciones