Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
On the Power of Computing with Proteins on Membranes
Año:2009
Áreas de investigación
  • Inteligencia artificial
Datos
Descripción
P systems with proteins on membranes are inspired closely by switching protein channels. This model of membrane computing using membrane division has been previously shown to solve an NP-complete problem in polynomial time. In this paper we characterize the class of problems solvable by these P systems in polynomial time and we show that it equals PSPACE. Therefore, these P systems are computationally equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer. The proof technique we employ reveals also some interesting trade-offs between certain P system properties, as antiport rules, membrane labeling by polarization or the presence of proteins.
Internacional
Si
JCR del ISI
No
Título de la revista
Lecture notes in computer science
ISSN
0302-9743
Factor de impacto JCR
0
Información de impacto
Volumen
5957
DOI
http://dx.doi.org/10.1007/978-3-642-11467-0_30
Número de revista
0
Desde la página
448
Hasta la página
460
Mes
ENERO
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Participante: David Perez Perez (Departamento: Inteligencia Artificial- FI - UPM)
  • Autor: Petr Sosik (UPM)
  • Autor: Alfonso Vicente Rodriguez-Paton Aradas (UPM)
  • Autor: Paul Andrei Paun (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)