On the power of computing with proteins on membranes
作者： Petr Sosík , Andrei Păun , Alfonso Rodríguez-Patón , David Pérez
DOI: 10.1007/978-3-642-11467-0_30
关键词:
摘要: P systems with proteins on membranes are inspired closely by switching protein channels. This model of membrane computing using division has been previously shown to solve an NP-complete problem in polynomial time. In this paper we characterize the class problems solvable these time and show that it equals PSPACE. Therefore, computationally equivalent (up a reduction) alternating Turing machine or PRAM computer. The proof technique employ reveals also some interesting trade-offs between certain system properties, as antiport rules, labeling polarization presence proteins.
unirioja.es
springer.com
us.es 
sci-hub.st 参考文章(18)
Peter van EMDE BOAS, Machine models and simulations Handbook of theoretical computer science (vol. A). pp. 1- 66 ,(1991) , 10.1016/B978-0-444-88071-0.50006-0
Pierluigi Frisco, Computing with Cells: Advances in Membrane Computing ,(2009)
Mario J. Pérez–Jiménez, A computational complexity theory in membrane computing international conference on membrane computing. pp. 125- 148 ,(2009) , 10.1007/978-3-642-11467-0_10
Petr Sosík, The computational power of cell division in P systems: Beating down parallel computers? Natural Computing. ,vol. 2, pp. 287- 298 ,(2003) , 10.1023/A:1025401325428
Mario J. Péerez Jiménez, Álvaro Romero Jiménez, Fernando Sancho Caparrini, Complexity classes in models of cellular computing with membranes Natural Computing. ,vol. 2, pp. 265- 285 ,(2003) , 10.1023/A:1025449224520
Andrei Pâun, Gheorghe Pâun, The power of communication: P systems with symport/antiport New Generation Computing. ,vol. 20, pp. 295- 305 ,(2002) , 10.1007/BF03037362
Marek Kwiatkowski, Ian Stark, The Continuous π-Calculus: A Process Algebra for Biochemical Modelling computational methods in systems biology. pp. 103- 122 ,(2008) , 10.1007/978-3-540-88562-7_11
Artiom Alhazov, Carlos Martín-Vide, Linqiang Pan, Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes Fundamenta Informaticae. ,vol. 58, pp. 67- 77 ,(2003)
Andrei Păun, Bianca Popa, P Systems with Proteins on Membranes and Membrane Division Developments in Language Theory. pp. 292- 303 ,(2006) , 10.1007/11779148_27
Andrei Păun, Bianca Popa, P Systems with Proteins on Membranes Fundamenta Informaticae. ,vol. 72, pp. 467- 483 ,(2006)