A research group at the Alexandru Ioan Cuza University of Iași, Romania, affiliated to the Romanian Academy of Sciences, conducts research in the area of membrane computing on topics such as operational semantics of the membrane systems, causality, object-based and rule-based event structures, as well as several aspects of mobile membranes including computability, complexity and links to other existing formalisms.
Membrane computing is a well-established and successful research field which belongs to the more general area of natural computing. Membrane computing was initially developed by Gh. Păun in 1998, and in 2003 was identified by Thomson Institute for Scientific Information as a “fast emerging research front in computer science”. Membrane computing deals with parallel and nondeterministic computing models inspired by cell biology. Membrane systems are complex hierarchical structures with a flow of materials and information which underlies their functioning, involving parallel application of rules, communication between membranes and membrane dissolution. A “computation” is performed in the following way: starting from an initial structure, the system evolves by applying the rules in a nondeterministic and maximally parallel manner. The maximally parallel way of using the rules means that in each step we apply a maximal multiset of rules, namely a multiset of rules such that no further rule can be added to the multiset. A halting configuration is reached when no rule is applicable.
Operational Semantics
We define the operational semantics for membrane systems, and prove that the semantics for both static and dynamic resource allocation are equivalent. We consider some alternative modes of evolution, based on either minimal parallelism, maximizing the quantities of consumed resources or maximizing the number of applied rules. For systems with a complex hierarchical structure, we present a reduction to a system with a single membrane (and additional rules). Such a reduction is achieved by encoding the semantic constraints of the hierarchical system within rule using promoters and inhibitors in the system consisting of just one membrane. This reduction is subsequently used as a technical tool to solve problems for complex systems by reducing them to simpler cases.
Causality
We construct systems with evolution running in reverse by inverting the direction of the rules themselves. We underline the similarity between the two modes of evolution (direct and reverse), and propose how both of them can be used during computations. We relate membrane systems to event structures by considering events to be related to rule applications (in one case), and to resources (in another case). The corresponding event structures represent formal tools underlying causal relations in the evolution of a parallel and nondeterministic system. We prove that the causal relation given by the resource based event structure is directly related to the way membrane rules can be linked together by a newly introduced causal relation.
Mobility
Mobile Membranes represent a parallel and nondeterministic computing model inspired by cells and their movements in which mobility is given by specific endocytosis and exocytosis rules. We studied the computability power and complexity of mobile membranes, and established some links to process algebra. We have introduced various membrane systems in which mobility is the key issue. The main mobility rules describing the evolution of the structure are endocytosis (moving an elementary membrane inside a neighbouring membrane), and exocytosis (moving an elementary membrane outside the membrane where it is placed); other mobility rules are given by pinocytosis and phagocytosis. We related systems of mobile membranes to some existing process calculi (mobile ambients, pi-calculus, brane calculi) and to Petri nets. We define some concepts inspired from process calculi in the framework of (mobile) membrane computing. To obtain more interesting and accurate models, we add timers inspired by cell lifetime to membranes. We relate these membrane systems with timers to timed mobile ambients. By describing biological systems using mobile membranes, we can provide precise answers to many interesting biological questions. Using software tools and process calculi bisimulations, (potentially infinite) system behaviour can be investigated, and this information could be interesting from a biological viewpoint.
A standard approach in membrane computing is to look for membrane systems with a minimal set of ingredients which are powerful enough to achieve the full computability power of Turing machines. We have investigated the computability power and efficiency of our formalisms by using formal languages, register machines and other ingredients of computability theory. For certain systems of mobile membranes, we prove that it is enough to have three membranes to get the same computational power as a Turing machine. Moreover, using systems of mobile membranes, we got polynomial solutions of two NP-complete problems. More details can be found on our web pages.
This book presents new ideas and results in membrane computing. The table of contents is avavailble at http://profs.info.uaic.ro/ ~gabriel/contents.pdf
For more information, please contact the author.
Link: http://iit.iit.tuiasi.ro/TR/
Please contact:
Gabriel Ciobanu
A.I. Cuza University of Iași, Romania
E-mail:
http://profs.info.uaic.ro/~gabriel/
