Membrane Computing (Tutorial)

摘要

The aim of the tutorial is to give a general overview of the Membrane Computing paradigm [2,5]. Membrane Computing is a quite active research field, initiated by Gh. Paun in 1998 [3]. It is a theoretical machine-oriented model, where the computational devices (known as P systems) are in some sense an abstraction of a living cell. There exist a large number of different definitions of P systems, but most of them share some common features: a membrane structure (defining in a natural way a number of regions or compartments), and an alphabet of objects that are able to evolve and/or move within the membrane structure according to a set of rules (emulating the way substances undergo biochemical reactions in a cell). Many of the first P systems specifications that were investigated proved to be universal or computationally complete (i.e. equivalent to Turing Machines). Besides, the quest for efficiency has been another research direction, yielding in many cases cellular solutions to NP-complete problems working in polynomial time (making a space-time trade-off and using the inherent massive parallelism of P systems). The first session of the tutorial will formalize these concepts, presenting a computational complexity theory for Membrane Computing.