The computational power of membrane systems, in their different variants, can be studied by defining classes of problems that can be solved within given bounds on computation time or space, and comparing them with usual computational complexity classes related to the Turing Machine model. Here we will consider in particular membrane systems with active membranes (where new membranes can be created by division of existing membranes). The problems related to the definition of time/space complexity classes for membrane systems will be discussed, and the resulting hierarchy will be compared with the usual hierarchy of complexity classes, mainly through simulations of Turing Machines by (uniform families of) membrane systems with active membranes.

Mauri, G., Leporati, A., Manzoni, L., Porreca, A., Zandron, C. (2015). Complexity classes for membrane systems: A survey. In 9th International Conference on Language and Automata Theory and Applications, LATA 2015; Nice; France; 2-6 March 2015 (pp.56-69). Springer Verlag [10.1007/978-3-319-15579-1_4].

Complexity classes for membrane systems: A survey

MAURI, GIANCARLO
;
LEPORATI, ALBERTO OTTAVIO
Secondo
;
MANZONI, LUCA;PORRECA, ANTONIO ENRICO
Penultimo
;
ZANDRON, CLAUDIO
Ultimo
2015

Abstract

The computational power of membrane systems, in their different variants, can be studied by defining classes of problems that can be solved within given bounds on computation time or space, and comparing them with usual computational complexity classes related to the Turing Machine model. Here we will consider in particular membrane systems with active membranes (where new membranes can be created by division of existing membranes). The problems related to the definition of time/space complexity classes for membrane systems will be discussed, and the resulting hierarchy will be compared with the usual hierarchy of complexity classes, mainly through simulations of Turing Machines by (uniform families of) membrane systems with active membranes.
slide + paper
Computer Science (all); Theoretical Computer Science
English
9th International Conference on Language and Automata Theory and Applications, LATA 2015
2015
9th International Conference on Language and Automata Theory and Applications, LATA 2015; Nice; France; 2-6 March 2015
9783319155784
2015
8977
56
69
http://springerlink.com/content/0302-9743/copyright/2005/
reserved
Mauri, G., Leporati, A., Manzoni, L., Porreca, A., Zandron, C. (2015). Complexity classes for membrane systems: A survey. In 9th International Conference on Language and Automata Theory and Applications, LATA 2015; Nice; France; 2-6 March 2015 (pp.56-69). Springer Verlag [10.1007/978-3-319-15579-1_4].
File in questo prodotto:
File Dimensione Formato  
invited_paper_3.pdf

Solo gestori archivio

Dimensione 422.34 kB
Formato Adobe PDF
422.34 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/107094
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
Social impact