Complexity classes for membrane systems
作者： Antonio E. Porreca , Giancarlo Mauri , Claudio Zandron
DOI: 10.1051/ITA:2006001
关键词:
摘要: We compare various computational complexity classes defined within the framework of membrane systems, a distributed parallel computing device which is inspired from functioning cell, with usual for Turing machines. In particular, we focus our attention on comparison among systems active membranes (where new can be created by division existing membranes) and PSPACE , EXP EXPSPACE .
sci-hub.se 参考文章(12)
Fred Joseph Gruenberger, Computing: An Introduction ,(1969)
Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustín Riscos-Núñez, Francisco J. Romero-Campero, P Systems with Active Membranes, Without Polarizations and Without Dissolution: A Characterization of P Lecture Notes in Computer Science. pp. 105- 116 ,(2005) , 10.1007/11560319_11
Mario J. Pérez-Jiménez, Alvaro Romero-Jiménez, Fernando Sancho-Caparrini, The P Versus NP Problem Through Cellular Computing with Membranes Lecture Notes in Computer Science. pp. 338- 352 ,(2003) , 10.1007/978-3-540-24635-0_26
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
Handbook of Formal Languages Springer-Verlag. ,(1997) , 10.1007/978-3-642-59126-6
Gheorghe Păun, P systems with active membranes: attacking NP-complete problems Journal of Automata, Languages and Combinatorics. ,vol. 6, pp. 75- 90 ,(2001)
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)
M.A. Gutierrez-Naranjo, M.J. Perez-Jimenez, A. Riscos-Nunez, F.J. Romero-Campero, Characterizing tractability with membrane creation symbolic and numeric algorithms for scientific computing. pp. 448- 457 ,(2005) , 10.1109/SYNASC.2005.24
Gheorghe Păun, Computing with Membranes: Attacking NP-Complete Problems Unconventional Models of Computation, UMC’2K. pp. 94- 115 ,(2001) , 10.1007/978-1-4471-0313-4_7
Claudio Zandron, Claudio Ferretti, Giancarlo Mauri, Solving NP-Complete Problems Using P Systems with Active Membranes Unconventional Models of Computation, UMC’2K. pp. 289- 301 ,(2001) , 10.1007/978-1-4471-0313-4_21