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.
Figure 1: Invariants checking with PRISM.
We have been interested in utilising P systems as specification languages for various natural, artificial or engineered systems. In this respect a specific class of membrane system has been introduced and studied for application in graphics. Another class has been introduced in connection with synchronizing the components of a system running in parallel. Special attention has been paid to systems with stochastic behaviour, especially from biology. For such systems, we have not only introduced a specification language, but have also produced simulation tools and utilized a number of state-of-the-art tools for system analysis.. The power and effectiveness of stochastic simulators have been complemented by a fine-grain analysis of various properties of the systems simulated by using a tool called Daikon (see link 3). These properties extracted from simulations have been then validated through verification techniques using PRISM, a probabilistic model checker (see link 4 and Figure 1). More details regarding these applications can be found at the link.
We are actively cooperating with many of the research groups working in membrane computing. We have been working with the group at the University of Verona (Vincenzo Manca) on the dynamical properties of P systems, with the group at the Universities of Paris XII (Sergey Verlan) and Metz (Maurice Margenstern) on synchronization problems in membrane systems, with Erzsebet Csuhaj-Varju and Gyorgy Vaszil at the Computer and Automation Institute of the Hungarian Academy of Sciences on membrane systems inspired by social networks, with Natalio Krasnogor at the University of Nottingham on using membrane systems as a modelling tool in synthetic biology, with Mario Perez-Jimenez and his group at the University of Seville on developing adequate tools for simulating membrane systems, with Giancarlo Mauri at the University of Milan-Bicocca on classes of system with stochastic behaviour. Further research plans for our group include the development of some programmability capabilities for these systems associated with sound verification and testing methods.
Department of Computer Science
University of Sheffield, United Kingdom
Tel: +44 114 222 1843 begin_of_the_skype_highlighting +44 114 222 1843 end_of_the_skype_highlighting