Theoretical Foundations and Applications of Membrane Systems

The main goal of this project is to investigate bio-inspired information systems, especially various models of membrane systems. A special focus will be put on the modelling of biological processes taking place at cell membranes. In 1998, membrane systems were introduced by Gheorghe PAUN (Computing with Membranes. Journal of Computer and System Sciences 61, 1 (2000), 108-143) as a new model of unconventional computation inspired by biochemical reactions that take place in living cells (for an overview of research in membrane computing see http://psystems.disco.unimib.it). Cells are the basic units for the structure and function of all organisms, which are structured by membranes. Membranes regulate the exchange of substances between compartments and also involve energy transformation, which altogether often is interpreted as computing process. In that sense, membrane systems can be seen as computing devices abstracted from cell function. A special model of membrane systems uses membrane channels allowing objects to cross a membrane in a collaborating manner: either they pass through in the same direction (which is called symport) or in opposite directions (antiport). We shall explore the theoretical foundations of membrane systems and their biological background; moreover, we shall go back to biology by providing biologists with software tools allowing them to get a better understanding of biological processes in cell membranes and membrane channels. Membrane systems analysing objects are called P automata. For the implementation of P automata we will restrict ourselves to models which are at least k-deterministic, which means that looking ahead at most k steps in a possibly non-deterministic system, the next configuration of the system is uniquely determined. To obtain feasible implementations of P automata, we have to explore a big variety of models of P automata in order to see whether they allow for universal computations even under the restriction of k-determinism. For classifying the computational complexity of various language classes, we shall also search for uniform classes of deterministic P automata and k-deterministic P automata. Parts of the project are carried out in co-operation with members of the EMCC (European Molecular Computing Consortium, see http://openit.disco.unimib.it/emcc/).