Ponencia
A Characterization of PSPACE with Antimatter and Membrane Creation
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 | 2015 |
Fecha de depósito | 2016-01-21 |
Publicado en |
|
ISBN/ISSN | 978-84-944366-2-8 |
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 ... 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. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
159_zsolt_miguel_QSAT_7.pdf | 415.1Kb | [PDF] | Ver/ | |