Observatorio de I+D+i UPM

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

• 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)

• Creador: Grupo de Investigación: Grupo de Inteligencia Artificial (LIA)
• Departamento: Inteligencia Artificial