Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Membrane computing and complexity theory: A characterization of PSPACE
Año:2007
Áreas de investigación
  • Inteligencia artificial
Datos
Descripción
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.
Internacional
Si
JCR del ISI
Si
Título de la revista
J COMPUT SYST SCI
ISSN
0022-0000
Factor de impacto JCR
1,185
Información de impacto
Volumen
73
DOI
Número de revista
1
Desde la página
137
Hasta la página
152
Mes
FEBRERO
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Alfonso Vicente Rodriguez-Paton Aradas (UPM)
  • Autor: Petr Sosik (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Inteligencia Artificial (LIA)
  • Departamento: Inteligencia Artificial
S2i 2021 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)