On the Power of Dissolution in P Systems with Active Membranes
作者： Miguel A. Gutiérrez–Naranjo , Mario J. Pérez–Jiménez , Agustín Riscos–Núñez , Francisco J. Romero–Campero
DOI: 10.1007/11603047_16
关键词:
摘要: In this paper we study membrane dissolution rules in the framework of P systems with active membranes but without using electrical charges. More precisely, prove that polynomial computational complexity class associated recognizer membranes, polarizations and coincides standard P. Furthermore, demonstrate if consider rules, then resulting contains NP.
springer.com
core.ac.uk
us.es
springerlink.com参考文章(12)
Álvaro Romero Jiménez, Fernando Sancho-Caparrini, Mario J. Pérez-Jiménez, A Polynomial Complexity Class in P Systems Using Membrane Division. DCFS. pp. 284- 294 ,(2003)
Artiom Alhazov, Rudolf Freund, On the Efficiency of P Systems with Active Membranes and Two Polarizations Membrane Computing. pp. 146- 160 ,(2005) , 10.1007/978-3-540-31837-8_8
Mario J. Pérez-Jiménez, Agustin Riscos-Núñez, A Linear-Time Solution to the Knapsack Problem Using P Systems with Active Membranes International Workshop on Membrane Computing. pp. 250- 268 ,(2003) , 10.1007/978-3-540-24619-0_19
Gheorghe Păun, P systems with active membranes: attacking NP-complete problems Journal of Automata, Languages and Combinatorics. ,vol. 6, pp. 75- 90 ,(2001)
Mario J. Pérez-Jiménez, An Approach to Computational Complexity in Membrane Computing Membrane Computing. pp. 85- 109 ,(2005) , 10.1007/978-3-540-31837-8_5
Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustín Riscos-Núñez, A fast P system for finding a balanced 2-partition soft computing. ,vol. 9, pp. 673- 678 ,(2005) , 10.1007/S00500-004-0397-0
Mario J. Pérez Jiménez, Agustín Riscos Núñez, Solving the Subset-Sum problem by P systems with active membranes New Generation Computing. ,vol. 23, pp. 339- 356 ,(2005) , 10.1007/BF03037637
Artiom Alhazov, Linqiang Pan, Gheorghe Păun, Trading polarizations for labels in P systems with active membranes Acta Informatica. ,vol. 41, pp. 111- 144 ,(2004) , 10.1007/S00236-004-0153-Z
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