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

A Characterization of PSPACE with Antimatter and Membrane Creation

Opened Access A Characterization of PSPACE with Antimatter and Membrane Creation
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: 2015
Publicado en: Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 159-178. Sevilla, E.T.S. de Ingeniería Informática, 2-6 de Febrero, 2015,
ISBN/ISSN: 978-84-944366-2-8
Tipo de documento: Ponencia
Resumen: The use of negative information provides a new tool for exploring the limits of P systems as computational devices. In this paper we prove that the combination of antimatter and annihilation rules (based on the annihilation of physical particles and antiparticles) and membrane creation (based on autopoiesis) provides a P system model able to solve PSPACE-complete problems. Namely, we provide a uniform family of P system in such P system model which solves the satis ability problem for quanti ed Boolean formulas (QSAT). In the second part of the paper, we prove that all the decision problems which can be solved with this P system model belong to the complexity class PSPACE, so this P system model characterises PSPACE.
Tamaño: 415.1Kb
Formato: PDF

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

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