Complexity classes for membrane systems

Antonio E. Porreca; Giancarlo Mauri; Claudio Zandron

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 2, page 141-162
  • ISSN: 0988-3754

Abstract

top
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 PSPACE, EXP, and EXPSPACE.

How to cite

top

Porreca, Antonio E., Mauri, Giancarlo, and Zandron, Claudio. "Complexity classes for membrane systems." RAIRO - Theoretical Informatics and Applications 40.2 (2006): 141-162. <http://eudml.org/doc/249727>.

@article{Porreca2006,
abstract = { 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 PSPACE, EXP, and EXPSPACE. },
author = {Porreca, Antonio E., Mauri, Giancarlo, Zandron, Claudio},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Membrane systems; computational complexity; molecular computing.; molecular computing},
language = {eng},
month = {7},
number = {2},
pages = {141-162},
publisher = {EDP Sciences},
title = {Complexity classes for membrane systems},
url = {http://eudml.org/doc/249727},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Porreca, Antonio E.
AU - Mauri, Giancarlo
AU - Zandron, Claudio
TI - Complexity classes for membrane systems
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/7//
PB - EDP Sciences
VL - 40
IS - 2
SP - 141
EP - 162
AB - 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 PSPACE, EXP, and EXPSPACE.
LA - eng
KW - Membrane systems; computational complexity; molecular computing.; molecular computing
UR - http://eudml.org/doc/249727
ER -

References

top
  1. A. Alhazov, C. Martin-Vide and L. Pan, Solving a PSPACE-complete problem by P-systems with restricted active membranes. Fundamenta Informaticae58 (2003) 67–77.  Zbl1085.68048
  2. M. Gutierrez-Naranjo and M.J. Perez-Jimenez, 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.  Zbl1161.68456
  3. M. Gutierrez-Naranjo, M.J. Perez-Jimenez, A. Riscos-Nunez and F.J. Romero-Campero, 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.  
  4. S.N. Krishna and R. Rama, A variant of P-systems with active membranes: Solving NP-complete problems. Romanian J. Inform. Sci. Technol.2 (1999).  
  5. C.H. Papadimitriou, Computational Complexity. Addison-Wesley, Reading, MA, 1994.  
  6. Gh. Păun, Computing with membranes. J. Comput. Syst. Sci.61 (2000) 108–143 (see also TUCS Research Report No. 208, November 1998, ).  Zbl0956.68055URIhttp://www.tucs.fi
  7. Gh. Păun, 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).  
  8. G. Păun, Membrane Computing. An Introduction. Springer-Verlag, Berlin (2002).  Zbl1034.68037
  9. M.J. Perez-Jimenez, A. Romero-Jimenez and F. Sancho-Caparrini, 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.  Zbl1048.68043
  10. M.J. Perez-Jimenez, A. Romero-Jimenez and F. Sancho-Caparrini, The P versus NP problem through cellular computing with membranes, Aspects of Molecular Computing. Lect. Notes Comput. Sci.2950 (2004) 338–352.  Zbl1200.68117
  11. G. Rozenberg, A. Salomaa eds., Handbook of Formal Languages. Springer-Verlag, Heidelberg (1997)  
  12. P. Sosik, The computational power of cell division in P-systems: Beating down parallel computers? Nat. Comput.2 (2003) 287–298.  Zbl1048.68044
  13. C. Zandron, C. Ferretti and G. Mauri, 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.  Zbl0967.68074

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.