Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
On the Power of Computing with Proteins on Membranes
Year:2009
Research Areas
  • Artificial intelligence
Information
Abstract
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.
International
Si
JCR
No
Title
Lecture notes in computer science
ISBN
0302-9743
Impact factor JCR
0
Impact info
Volume
5957
http://dx.doi.org/10.1007/978-3-642-11467-0_30
Journal number
0
From page
448
To page
460
Month
ENERO
Ranking
Participants
  • 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)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de Inteligencia Artificial (LIA)
  • Departamento: Inteligencia Artificial
S2i 2020 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)