Space complexity of membrane systems

Speaker: Antonio E. Porreca, Ph.D. student (Università degli Studi di Milano-Bicocca)

Abstract: Several variants of membrane systems (P systems) have been investigated from a complexity-theoretic standpoint, particularly because of the possibility to solve computationally hard problems in polynomial time by trading space for time. With the goal of formalising this trade-off, a study of the space complexity of P systems has been recently initiated, leading to an almost complete characterisation of the class of problems solvable in polynomial space by P systems with active membranes. The aim of this talk is to give an overview of the results and the techniques used to prove them. We will also present some open problems that might require different approaches.

Information:

Date: Thursday, 10-02-2011.
Time: 10:30.
Place: Seminar room of the department H1.50 (Module H, First floor, E.T.S. Ingeniería Informática)
Language: English