Membrane Computing [and Graph Transformation] Electronic Communications of the EASST Volume 6 (2007) Proceedings of the Sixth International Workshop on Graph Transformation and Visual Modeling Techniques (GT-VMT 2007) Membrane Computing [and Graph Transformation] Gheorghe Păun 1 pages Guest Editors: Karsten Ehrig, Holger Giese Managing Editors: Tiziana Margaria, Julia Padberg, Gabriele Taentzer ECEASST Home Page: http://www.easst.org/eceasst/ ISSN 1863-2122 http://www.easst.org/eceasst/ ECEASST Membrane Computing [and Graph Transformation] Gheorghe Păun Institute of Mathematics of the Romanian Academy, Bucharest, Romania, and Research Group on Natural Computing, Sevilla University, Spain george.paun@imar.ro, gpaun@us.es Abstract: Introduction to membrane computing, with an eye on graph theory issues. Keywords: Natural computing, membrane computing, P system, Turing com- putability Membrane computing is a branch of natural computing initiated in [5] which abstracts comput- ing models from the organization and the functioning of the living cell and from the cooperation of cells in tissues, organs (brain included) or other higher order structures. The resulting models, called P systems, can be briefly described as devices which process multisets of abstract objects in the compartments delimited by membranes. According to the arrangement of membranes, there are cell-like P systems (with the membranes embedded hierarchically), tissue-like (with the membranes placed in the nodes of an arbitrary graph), and neural-like P systems (with a special case, of spiking neural P systems). A P system can be used as a computing device, generating/acccepting sets of numbers, of vec- tors of numbers, languages, sets of trees or graphs, arrays, etc. Many variants were considered, with biological, mathematical, or computer science motivation, and most of them were proved to be Turing complete. When an enhanced parallelism is available, e.g., by means of mem- brane division, computationally hard problems (typically, NP-complete problems) were solved in polynomial time – by a space-time trade-off. Recently, membrane computing was much used as a framework for devising models in biol- ogy, economics, linguistics, computer science, optimization. The talk is intended to be a general introduction to membrane computing, starting by placing it in natural computing, presenting the basic ideas and main types of results and applications, and pointing whenever necessary the interplay with graph theory and graph transformation (graph theory provides ideas/tools for studying P systems, while P systems can be used for handling graphs, e.g., as objects in membranes, or indirectly, as graphs describing membrane structures). Research topics are mentioned. No biological background is necessary. For further (introductory) details in membrane computing, the reader is referred to the mono- graph [6], the volume [1], the papers [7], [3], as well as to the web page [10] (a complete bibliog- raphy of the domain can be found at this site, many downloadable papers, software, applications, etc.). Bibliography [1] G. Ciobanu, Gh. Păun, M.J. Pérez-Jiménez, eds.: Applications of Membrane Computing, Springer, Berlin, 2006. 1 / 1 Volume 6 (2007) mailto:george.paun@imar.ro, gpaun@us.es Membrane Computing [and Graph Transformation] [2] R. Freund, M. Oswald, A. Păun: P systems generating trees. In G. Mauri et al., eds., Mem- brane Computing, International Workshop, WMC5, Milano, Italy, 2004, Selected Papers, LNCS 3365, Springer-Verlag, Berlin, 2005, 221–232. [3] M. Ionescu, Gh. Păun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. [4] N. Jonoska, M. Margenstern: Tree operations in P systems and λ -calculus. Fundamenta Informaticae, 59, 1 (2004), 67–90. [5] Gh. Păun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143 (and TUCS Report 208, November 1998, www.tucs.fi). [6] Gh. Păun: Membrane Computing. An Introduction. Springer, Berlin, 2002. [7] Gh. Păun, G. Rozenberg: A guide to membrane computing, Theoretical Computer Sci., 287, 1 (2002), 73–100. [8] Gh. Păun, Y. Sakakibara, T. Yokomori: P Systems on graphs of restricted forms. Publ. Math. Debrecen, 60 (2002), 635–660. [9] R. Rama, H. Ramesh: On generating trees by P systems. In Proc. SYNASC 05, Timişoara, Romania, IEEE Press, 2005, 462–466. [10] The P Systems Web Page: http://psystems.disco.unimib.it. Proc. GT-VMT 2007 2 / 1