Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-12T19:49:20.090Z Has data issue: false hasContentIssue false
  • English
  • Français

Complexity classes for membrane systems

Published online by Cambridge University Press:  20 July 2006

Antonio E. Porreca ,
Giancarlo Mauri  and
Claudio Zandron
Antonio E. Porreca
Affiliation:
DISCo, Università di Milano-Bicocca, Italy; {porreca; mauri; zandron}@disco.unimib.it
Giancarlo Mauri
Affiliation:
DISCo, Università di Milano-Bicocca, Italy; {porreca; mauri; zandron}@disco.unimib.it
Claudio Zandron
Affiliation:
DISCo, Università di Milano-Bicocca, Italy; {porreca; mauri; zandron}@disco.unimib.it
Get access

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.

Keywords

Membrane systemscomputational complexitymolecular computing.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 2: Alberto Bertoni: Climbing summits , April 2006 , pp. 141 - 162
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alhazov, A., Martin-Vide, C. and Pan, L., Solving a PSPACE-complete problem by P-systems with restricted active membranes. Fundamenta Informaticae 58 (2003) 67–77.
Gutierrez-Naranjo, M. and Perez-Jimenez, M.J., 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. CrossRef
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.
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).
C.H. Papadimitriou, Computational Complexity. Addison-Wesley, Reading, MA, 1994.
Păun, Gh., Computing with membranes. J. Comput. Syst. Sci. 61 (2000) 108–143 (see also TUCS Research Report No. 208, November 1998, http://www.tucs.fi). CrossRef
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).
G. Păun, Membrane Computing. An Introduction. Springer-Verlag, Berlin (2002).
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.
Perez-Jimenez, M.J., Romero-Jimenez, A. and Sancho-Caparrini, F., The P versus NP problem through cellular computing with membranes, Aspects of Molecular Computing. Lect. Notes Comput. Sci. 2950 (2004) 338–352. CrossRef
G. Rozenberg, A. Salomaa eds., Handbook of Formal Languages. Springer-Verlag, Heidelberg (1997)
Sosik, P., The computational power of cell division in P-systems: Beating down parallel computers? Nat. Comput. 2 (2003) 287–298. CrossRef
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.