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

A Characterization of PSPACE with Antimatter and Membrane Creation

 

Advanced Search
 
Opened Access A Characterization of PSPACE with Antimatter and Membrane Creation
Cites
Show item statistics
Icon
Export to
Author: Gazdag, Zsolt
Gutiérrez Naranjo, Miguel Ángel
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2015
Published in: 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
Document type: Presentation
Abstract: 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.
Size: 415.1Kb
Format: PDF

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

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)