We compare various computational complexity classes defined within the framework of membrane systems, a distributed parallel computing device which is inspired from the functioning of the cell, with usual computational complexity classes for Turing machines. In particular, we focus our attention on the comparison among complexity classes for membrane systems with active membranes (where new membranes can be created by division of existing membranes) and the classes , , and .
Mots clés : membrane systems, computational complexity, molecular computing
@article{ITA_2006__40_2_141_0, author = {Porreca, Antonio E. and Mauri, Giancarlo and Zandron, Claudio}, title = {Complexity classes for membrane systems}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {141--162}, publisher = {EDP-Sciences}, volume = {40}, number = {2}, year = {2006}, doi = {10.1051/ita:2006001}, mrnumber = {2252633}, zbl = {1112.68065}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2006001/} }
TY - JOUR AU - Porreca, Antonio E. AU - Mauri, Giancarlo AU - Zandron, Claudio TI - Complexity classes for membrane systems JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 141 EP - 162 VL - 40 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006001/ DO - 10.1051/ita:2006001 LA - en ID - ITA_2006__40_2_141_0 ER -
%0 Journal Article %A Porreca, Antonio E. %A Mauri, Giancarlo %A Zandron, Claudio %T Complexity classes for membrane systems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 141-162 %V 40 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006001/ %R 10.1051/ita:2006001 %G en %F ITA_2006__40_2_141_0
Porreca, Antonio E.; Mauri, Giancarlo; Zandron, Claudio. Complexity classes for membrane systems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 141-162. doi : 10.1051/ita:2006001. http://www.numdam.org/articles/10.1051/ita:2006001/
[1] Solving a PSPACE-complete problem by P-systems with restricted active membranes. Fundamenta Informaticae 58 (2003) 67-77. | Zbl
, and ,[2] P-systems with active membranes, without polarizations and without dissolution: a characterization of P, in Unconventional Computation, 4th International Conference, UC 2005, edited by C.S. Calude, M.J. Dinneen, Gh. Paun, M.J. Perez-Jimenez and G. Rozenberg. Springer-Verlag, Berlin-Heidelberg. Lect. Notes Comput. Sci. 3699 (2005) 105-116.
and ,[3] Characterizing Tractability with Membrane Creation, in Proc. of First International Workshop on Theory and Application of P Systems, Timisoara, Romania, September 26-27, edited by G. Ciobanu, Gh. Paun. (2005) 61-68.
, , and ,[4] A variant of P-systems with active membranes: Solving NP-complete problems. Romanian J. Inform. Sci. Technol. 2 (1999).
and ,[5] Computational Complexity. Addison-Wesley, Reading, MA, 1994. | MR | Zbl
,[6] Computing with membranes. J. Comput. Syst. Sci. 61 (2000) 108-143 (see also TUCS Research Report No. 208, November 1998, http://www.tucs.fi). | Zbl
,[7] P-systems with active membranes: attacking NP complete problems, in Unconventional Models of Computation, edited by I. Antoniou, C.S. Calude, M.J. Dinneen. Springer-Verlag, London (2000) 94-115 (see also CDMTCS Research report No. 102, 1999, Auckland Univ., New Zeland, www.cs.auckland.ac.nz/CDMTCS). | Zbl
,[8] Membrane Computing. An Introduction. Springer-Verlag, Berlin (2002). | MR | Zbl
,[9] Complexity Classes in Cellular Computing with Membranes, Rovira i Virgili Univ., Tech. Rep. No. 26, edited by M. Cavaliere, C. Martin-Vide, Gh. Păun. Brainstorming Week on Membrane Computing; Tarragona, Feb. 5-11 (2003) 270-278 and Nat. Comput. 2 (2003) 265-285. | Zbl
, and ,[10] The P versus NP problem through cellular computing with membranes, Aspects of Molecular Computing. Lect. Notes Comput. Sci. 2950 (2004) 338-352.
, and ,[11] Zbl
, eds., Handbook of Formal Languages. Springer-Verlag, Heidelberg (1997) |[12] The computational power of cell division in P-systems: Beating down parallel computers? Nat. Comput. 2 (2003) 287-298. | Zbl
,[13] Solving NP-Complete Problems Using P-systems with Active Membranes, in Unconventional Models of Computation, edited by I. Antoniou, C.S. Calude, M.J. Dinneen. Springer-Verlag, London (2000) 289-301. | Zbl
, and ,Cité par Sources :