Memorias de investigación
Research Publications in journals:
Membrane computing and complexity theory: A characterization of PSPACE
Year:2007

Research Areas
  • Artificial intelligence

Information
Abstract
A P system is a natural computing model inspired by information processing in cells and cellular membranes. We show that confluent P systems with active membranes solve in polynomial time exactly the class of problems PSPACE. Consequently, these P systems prove to be equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer. Similar results were achieved also with other models of natural computation, such as DNA computing or genetic algorithms. Our result, together with the previous observations, suggests that the class PSPACE provides a tight upper bound on the computational potential of biological information processing models.
International
Si
JCR
Si
Title
J COMPUT SYST SCI
ISBN
0022-0000
Impact factor JCR
1,185
Impact info
Volume
73
Journal number
1
From page
137
To page
152
Month
FEBRERO
Ranking
Participants

Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de Inteligencia Artificial (LIA)
  • Departamento: Inteligencia Artificial