Membrane Computing – Theory and Applications

Post date: Apr 12, 2011 2:42:45 AM

Membrane Computing – Theory and Applications

by Marian Gheorghe

Membrane computing is a new unconventional computing model that abstracts from the structure and functionality of the living cell. Developments of this computational paradigm cover both the study of the theoretical basis of the models introduced as well as applications in various fields.

It might appear that at the moment, the interaction between computer science and biology is intensifying, with positive consequences for both fields. Biology has been seen as a rich source of ideas for creating novel approaches, methods, algorithms and techniques for solving complex computational problems, for generating new concepts and theories that help specify and analyse various systems and for providing a new basis for the theory of computation itself. On the other hand, complex and sophisticated computer science approaches have been utilized in modelling various biological systems, by providing a rich set of methods and techniques to specify and analyse such systems.

Membrane computing had emerged as a branch of natural computing by the end of the 1990s. The models belonging to this computational paradigm, called membrane (or P) systems, have been conceived as hierarchically distributed devices inspired by the structure of living cells. Some of these models have also been abstracted from the structure and functionality of more complex biological entities, like tissues, organs and populations of cells. Membrane computing started off as a new unconventional computational paradigm generating a broad range of fundamental research in theoretical computer science. In recent years, membrane systems have been used as modelling vehicles for various biological systems or as specification languages in graphics or for describing a large variety of parallel and concurrent systems. For a comprehensive presentation of this research field, The Oxford Handbook of Membrane Computing (see link 1) is recommended, and for an almost exhaustive list of publications in this field, the website available at link 2 can be consulted. The above mentioned lines of research have been followed by our group at the University of Sheffield as well.

We have been working on developing various types of membrane systems inspired by phenomena from the world of biology, including: intra- and inter-cellular signalling mechanisms (captured by P systems with travelling objects); communication processes occurring in populations of cells or more complex organisms (population P systems); and concerted actions of individual entities in populations of bacteria (quorum sensing P systems). As with other types of membrane systems, researchers have investigated various aspects of these models, including their computational capabilities, complexity aspects and relationships with other classes of computational models, including various process algebras, Petri nets, cellular automata, X-machines and grammar systems. Establishing such relationships has allowed us to transfer from these models to membrane systems a rich set of methods and tools to analyse and validate the consistency of such systems.