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

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