EFTA01145243.pdf

Introduction to Membrane Computing Gheorghe Pfiun Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucuresti, Romania E-mail: george .pauneimar .ro Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reins Mercedes s/n, 41012 Sevilla, Spain E-mail: gpaunflus . es Abstract. This is a comprehensive (and — supposed — friendly) introduction to mem- brane computing, meant to offer both to computer scientists and to non-computer scientists an up-dated overview of the domain. That is why the panoply of no- tions which are introduced here is rather large, but the presentation is informal, without any proof and with rigorous definitions given only for the basic types of P systems — symbol-object P systems with multiset rewriting rules, systems with sym- port/antiport rules, systems with string-objects, tissue-like P systems, and neural- like P systems. Besides a list of (biologically inspired or mathematically motivated) ingredients/features which can be used in systems of these types, we also mention a series of results — as well as a series of research trends and topics. Then, both some applications are briefly mentioned and a discussion is made about the attractiveness of this framework for (possible) applications, especially in biology. 1 (The Impossibility of) A Definition of Membrane Computing Membrane computing is an area of computer science aiming to abstract computing ideas and models from the structure and the functioning of living cells, as well as from the way the cells are organized in tissues or higher order structures. In short, it deals with distributed and parallel computing models, processing mu ltisets of symbol-objects in a localized manner (evolution rules and evolving objects are encapsulated into compartments delimited by membranes), with an essential role played by the communication among compartment s (with the environment as well). Of course, this is just a rough description of a membrane system — hereafter called P system — of the very basic type, as many different classes of such devices exist. The essential ingredient of a P system is its membrane structure, which ca n be a hierarchical arrangement of membranes, like in a cell (hence described by a tree), or a net of membranes (placed in the nodes of a graph), like in a tissue, or in a neural net. The intuition behind the 1 EFTA01145243 notion of a membr ane is that from biology, of a three—dimensional vesicle, but the concept itself is generalized/idealized to interpreting a membrane as a separator of two regions (of the Euclidean space), a finite "inside" an d an infinite "outside", also providing the possibility of a selective communication among the two regions. The variety of suggestions from biology and the range of possibilities to define the architecture and the functioning of a membrane-based-multiset-processing device are practically endless — and already the literature of membrane computing contains a very large number of models. Thus, membrane computing is not a theory related to a specific model, it is a framework for devising compart mentalized models. Both because the domain is rather young (the trigger paper is [77], circulated first on web, but related ideas were considered before, in various contexts), but also as a genuine feature, bas ed both on the biological background and the mathematical formalism used, not only there are already proposed many types of P systems, but the flexibility and the versatility of P systems seem to be, in p rinciple, unlimited. This last observation, as well as the rapid development and enlargement of the research in this area, make impossible a short and faithful presentation of membrane computing, with any good level of completeness. However, there are a series of notions, notation, models which are already "standard", which have stabilized and can be considered as basic elements of membrane computing. This paper is devoted to presenting mainly such notions and models, together with the associated notation. The presentation will be both historically and didactically organized, introducing first either notions which were investigated from the beginning in this area, or simpler notions, able to quickly offer an image of membrane computing to the reader who is not familiar with the domain. The reader has surely noticed that all the previous discussion refers mainly to computer science (goals), and much less to biology. Membrane computing was not initiated as an area aiming to provide models to biology, in particular, models of the cell. Still in this moment, after a considerable development at the theoretical level, the domain is not fully prepared to offer such models to biology — but this is a strong tendency of the recent research and considerable advances towards such achievements were reported (the topic will be discussed later in more details). 2 Membrane Computing as Part of Natural Computing Before entering into more specific elements of membrane computing, let us spend some time with the relationship of this area with, let us say, using the "local" terminology, the "outside". We have said above that membrane computing is part of computer science. However, the genus proximus is natural computing, the general attempt to learn computer science useful ideas, models, paradigms from the way nature - life especially — "computes", in various circumstances where substance and information processing can be interpreted as computations. Classic bio- inspired branches of natural computing are genetic algorithms (more generally, evolutionary computing, with well individualized sub-branches such as evolutionary programming) and neural computing. Both of them have a long history, which can be traced until unpublish ed works of Turing (see, e.g., [97]), many applications, and a huge bibliography. Both of them are a proof that "it is worth learning fr om biology", supporting the optimistic observation that many billions of year nature/life has adjusted certa in tools and processes which, correctly (luckily?) 2 EFTA01145244 abstracted and implemented in computer science terms, can p rove to be surprisingly useful in many applications. A more recent branch of natural computing, with an enthusiastic beginning and unconfirmed yet computational applicability (we do not discuss here the by-products, such as the nanotech- nology related developments), is DNA computing, whose birth certificate is related to Adleman experiment [1] of solving a (small) instance of the Hamiltonian path problem by handling DNA molecules in a laboratory. According to Hartmanis [50], (51], it was a demo that we can compute with bio-molecules, a big event for computability. However, after one decade of research, the domain is still preparing its tools for a possible future practical application and looking for a new breakthrough idea, similar to Adleman's one front 1994. However, at the theoretical level, DNA computing is beautifully developed (see, e.g., [85] and the proceedings of the yearly DNA Based Computers series of conferences). This is both due to the fact that DNA structure and processing suggest a series of new data structures (e.g., the double stranded sequence, with the pairs of corresponding symbols from the two strands being related through a complementarity relation) and operations (e.g., recombination, denaturation, hybridization), but also to the fact that the massive parallelism made possible by the efficiency of DNA as a support of information promises to be useful in solving computationally hard problems in a feasible time. Actually, at the theoretical level one can say that DNA computing started already in 1987, when T. Head [49] has proposed a language theoretic model of what he called the splicing operation (the re- combination of DNA molecules, cut by restriction enzymes in fragments pasted together when the sticky ends match). Both evolutionary computing and DNA computing are inspired from and related to handling DNA molecules. Neural computing considers the neurons are simple finite automata linked in networks of specific types. Thu s, these "neurons" are not interpreted as cells, with an internal structure and life, but as "dots on a grid", with a simple input-output function. (The same observation holds true for cellular automata, where again the "cells" are "dots on a grid", only interacting among them, in a rigid structure.) None of these domains considers the cell itself as its main object of research, in particular, none of these domains pays any attention to membranes and compartmentalization — and this is the poin t where membrane computing enters the stage. Thus, membrane computing can be seen as an extension of DNA On ore generally, molecular) computing, from the "one-processor" level to a distributed computing model. 3 Laudation to the Cell (and Its Membranes) Life (as we know it on Earth, in the traditional meaning of the term, that investigated by biology) is directly related to cells, everything alive consists of cells or has to do in a direct way with cells. The cell is the smallest "thing" unanimously considered as dive. It is very small and very intricate in its structure and functioning, has an elaborate internal activity and an exquisite interaction with the neighboring cells, and with the environment in general. It is fragile and robust at the same time, with a way to organize (control) the bio-chemical (and informational) processes which was polished during billions of years of evolution. Any cell means membranes. The cell itself is defined — separated from its environment — by a membrane, the external one. Inside the cell, several membranes enclose "protected reactors", compartments where specific biochemical processes take place. In particular, a membrane en- closes the nucleus (of eukaryotic cells), where the genetic material is placed. Through vesicles 3 EFTA01145245 enclosed by membranes one can transport packages of molecules from a part of the cell (e.g., from the Colgi apparatus) to other parts of the cell - in such a way that the transported molecules are not "aggressed" during their journey by neighboring chemicals. Then, the membranes allow a selective passage of substances among the compartmen is delimited by them. This can be a simple selection by size, in the case of small molecules, or a much mor e intricate selection, through protein channels, which not only select, but can also move molecules from a low concentration to a higher concentration, perhaps coupling molecules, through so-called symport and antiport processes. Much more: the membranes of a cell do not only delimit compartments where specif is reactions take place in solution, hence inside the compartments, but many reactions in a cell develop on the membranes, catalyzed by the many proteins bound on them. It is said that when a compartment is too large for the local biochemistry to be efficient, life creates membranes, both in order to create smaller "reactors " (small enough that, through the Brownian motion, any two of the enclosed molecules can collide frequently en ough), and in order to create further "reaction surfaces". Anyway, biology contains many fascinating facts fr om a computer science point of view, and the reader is encouraged to check the validity of this assertion browsing, e.g., through [2], [64], [8]. Life means surfaces inside surfaces, as can be learned already from the ti the of [52], while S. Marcus puts it in an equational form [69]: Life = DNA software + membrane hardware. Then, there are cells living alone (unicellular organisms, such as ciliates, bac feria, etc.), but in general the cells are organized in tissues, organs, organisms, communities of organisms. All these suppose a specific organization, starting with the direct communication/cooperation among neighboring cells, and ending with the interaction with the environment, at various levels. Together with the internal structure and org anization of the cell, all these suggest a lot of ideas, exciting from a mathematical point of view, and potentia Ily useful from a computability point of view. Part of them were already explored in membrane computing, much mo re still wait for research efforts. 4 Some General Features of Membrane Computing Models Still remaining at this general level, it is worth mentioning from the beginning some of the basic features of models investigated in this area, besides the essential use of mem- branes/compartmentalization. We have mentioned above the notion of a multiset. The compartments of a cell contains substances (ions, small molecules, macromolecules) swimming in an aqueous solution; there is no ordering there, everything is close to everything, the concentration matters, the population, the number of copies of each molecule (of course, we are abstracting/idealizing here, departing from the biological reality). Thus, the suggestion is immediate: to work with sets of objects whose multiplicities matter, hence with multisets. This is a data structure with peculiar characteristics, not new but not systematically investigated in computer science. A multiset can be represented in many ways, but the most compact one is in the f orm of a string. For instance, if the objects a, b, c are present in, respectively, 5, 2, 6 copies each, we can represent this multiset by the string a5b2c6; of course, all permutations of this string represent the same multiset. Both from the string representation of multisets and because of the bio-chemical background, 4 EFTA01145246 where standard chemical reactions are common, the suggestion comes to process the multisets fro in the compartments of our computing device by means of rewriting-like rules. This means rules of the form ti v, where w and v are multisets of objects (represented by strings). Continuing the previous example, we can consider a rule aab abcc. It indicates the fact that two copies of object a together with a copy of object b react, and, as a result of this reaction, we get back a copy of a as well as the copy of b (hence b behaves here as a catalyst), and we produce two new copies of c. If this rule is applied to the multiset a5b2c6, then, because aab are "consumed" and then abcc are "produced", we pass to the multiset a4b2cs. Similarly, by using the rule bb aac, we will get the multiset a7c7, which contains no occurrence of object b. Two important problems arise here. The first one is related to the non-determinism. Which rules should be app lied and to which objects? The copies of an object are considered identical, so we do not distinguish among them; whether to use the first rule or the second one is a significant issue, especially because they cannot be used both at the same time (for the mentioned multiset), as they compete for the "reactant" b. The standard solut ion to this problem in membrane computing is that the rules and the objects are chosen in a non-determinist ic manner (at random, with no preference; more rigorously, we can say that any possible evolution is allowed). This is also related to the idea of parallelism. Biochemistry is not only (in a certain degree) non-deterministic, but it is also (in a certain degree) parallel. If two chemicals can react, then the reaction does not take place for only two molecules of the two chemicals, but, in principle, for all molecules. This is the suggestion supporting the maximal parallelism used in many classes of P systems: in each step, all rules which can be applied have to be applied to all possible objects. We will come back to this important notion later, but now we only illustrate it with the previous multiset and pair of rules. Using these rules in the maximally parallel manner means to either use the first rule twice (thus involving four copies of a and both copies of b) or once the second rule (it consumes both copies of b, hence the first rule cannot be used at the same time). In the first case, one copy of a remains unused (and the same with all copies of c), and the resulting multiset is a3b2c10; in the second case, all copies of a and c remain unused, and the resulting multiset is a7c7. It deserves to be noted that in the latter case the maximally parallel application of rules corresponds to the sequential (one in a time) application of the second rule. There also are other types of rules used in membrane computing (e.g., symport an d antiport rules), but we will discuss them later. Here we close with the observation that membrane computing d eals with models which are intrinsically discrete (basically, working with multisets of objects, with the multiplicities being natural numbers) and evolve through rewriting-like (we can also say reacti on-like) rules. 5 Computer Science Related Areas Rewriting rules are standard rules for handling strings in formal language theory (although other types of rules are also used, both in formal lan guage theory and in P systems, such as insertion, deletion, context-adjoining, etc.). Also working with strings modulo the ordering of symbols is "old stuff': commutative languages (investigated, e.g., in (35]) are nothing else than the permutation closure of languages. In turn, the multiplicity of symbol occurrences in a string corresponds to the Parikh image of the string, which directly leads to vector addition systems, Petri nets, register machines, formal power series. 5 EFTA01145247  Then, also the parallelism is considered in many areas of formal languages, and it is the main feature of Lindenmayer systems. These systems deserve a special discussion here, as they are a well developed branch of formal language theory inspired from biology, specifically, from the development of multi-cellular organisms (which can be described by strings of symbols). However, for L systems the cells are considered as symbols, not their structure is investigated but their organization in (mainly linear) patterns. P systems can be seen as dual to L systems, as they zoom in the cell, distinguishing the internal structure and the objects evolving inside it - maybe also distinguishing (when "zooming enough") the str ucture of the objects themselves, which leads to the category of P systems with string-objects. However, a difference exists between the kind of parallelism in L systems and th at in P systems: there the parallelism is total — all symbols of a string should be processed at the same time, here we work with a maximal parallelism — we process as many objects as possible, but not necessari ly all of them. Still closer to membrane computing are the multiset processing languages, the most known of them being Gamma [9, 10]. The standard rules of Gamma are of the form u v(r), where u and v ar e multisets and x is a predicate which should be satisfied by the multiset to which the rule u v is applied. The generality of the form of rules ensures a great expressivity and, in a direct manner, computational universality . What alumna does not have (at least in the initial versions) is distributivity. Then, membrane computing restricts the form of rules, on the one hand, as imposed by the biological roots, on the other hand , in search of mathematically simple and elegant models. Also membranes appear, even in Gamma related models, and this is the case with CHAM, the Chemical Abstract Machine of Berry and Boudol, [16], the direct ancestor of membrane systems — wit h the mentioning that the membranes of CHAM ... are not membranes as in the cell biology, but they correspond to the contents of membranes, multisets and lower level membranes together, while the goals and the approach are completely different, directed to the algebraic treatment of the processes these membranes can undergo. From this point of view, of goals and tools, CHAM has a recent counterpart in the so-called brane calculus (of course, "brane" co mes front "membrane") from [22] (see also [89] for a related approach), where process alge bra is used for investigating the processes taking place on membranes and with membranes of a cell . The idea of devising a computing device based on compartmentalization through membranes was also suggested in [66]. Many related areas and many roots, with many common ideas and many differences. In some extent, membrane computing is a synthesis of part of these ideas, integrated in a framework directly inspired from the cell biology, paying the deserved attention to membranes (hence to distribution, hierarchization, communication, localization and to other related concepts), aiming — in the basic types of devices — to find computing models, as elegant (minimalistic) as possible, as powerful as possible (in comparison with Turing machines and their subclasses), and as efficient as possible (able to solve computationally hard problems in a feasible time). 6 The Cell-Like Membrane Structure We move now towards presenting in a more precise manner the computing models investigated in our area, and we start by introducing one the fundamental ingredients of a P system, namely, 6 EFTA01145248 the membrane structure. The meaning of this notion is illustrated in Figure 1, and this is wha t we can see when looking (through mathematical glasses, hence abstracting as much as necessary in order t o obtain a formal model) to a standard cell. skin elementary membrane membranes regions environment environment Figure 1: A membrane structure Thus, as suggested by Figure 1, a membrane structure is a hierarchical ly arranged set of membranes, contained in a distinguished external membrane (corresponding to the plasma membrane and usually called the skin membrane). Several membranes can be p laced inside the skin membrane (they correspond to the membranes present in a cell, around the nucleus, in Golg i apparatus, vesicles, mitochondria, etc.); a membrane without any other membrane inside it is said to be elementary. Each membrane determine s a compartment, also called region, the space delimited from above by it and from below by the membranes placed directly inside, if any exists. Clearly, the corre spondence membrane-region is one-to-one, that is why we sometimes use interchangeably the se terms. Usually, the membranes are identified by labels from a given set of labels. In Figure 1, we use numbers, starting with number 1 assigned to the skin membrane (this is the stand and labelling, but the labels can be more informative "names" associated with the membranes). Also, in the fi gure the labels are assigned in a one-to-one manner to membranes, but this is possible only in the case of membr ane structures which cannot grow (indefinitely), otherwise several membranes should have the same label (we will see later such cases). Due to the membrane— region correspondence, we identify by the same label a memb rare and its associated region. Clearly, a hierarchical structure of membranes can be represented by a rooted tree; Figure 2 gives the tree which describes the membrane structure from Figure 1. The root of the tree is associated with the skin membrane and the leaves with the elementary membranes. In this way, graph-theoretic notions are brought into the stage, such as the distance in the tree, the level of a membrane, the height/depth of the membrane structure, as well as terminology, such as parent/child membrane, ancestor, etc. 7 EFTA01145249  Figure 2: The tree describing the membrane structure from Figure 1 Directly suggested by the tree representation is the symbolic representation of a membrane structure, by strings of labelled matching parentheses. For instance, a string corresponding to the st ructure from Figure 1 is the following one: [1 [2 12 [3 13 [4 [5 15 [6 IS 13191916 [7 4 LI ]1' An important aspect should now be noted: the membranes from the same level can f bat around, that is, the tree representing the membrane structure is not oriented; in terms of paren- theses exp ressions, two sub-expressions placed at the same level represent the same membrane structure. For instance, in the previous case, the expression [313 [4 [6 615 19 19 16 [717 [5 15 14 [21211 is an equivalent representation of the same membrane structure. 7 Evolution Rules and the Way of Using Them In the basic variant of P systems, each region contains a multiset of symbol-obj ects, which correspond to the chemicals swimming in a solution in a cell compartment; these chemicals are considered here as unstructured, that is why we describe them by s ymbols from a given alphabet. The objects evolve by means of evolution rules, which are also localized, associated with the regions of the membrane structure. Actually, there are three main types of r (1) multiset- rewriting rules (one uses to call them, simply, evolution rules), (2) conununication rules, and (3) rules for handling membranes. In this section we present the first type of rules. They correspond to the chemi cal reactions possible in the compartments of a cell, hence they are of the form v, whe re u and v are multisets of objects. However, in order to make the compartments cooperate, we h ave to move objects across membranes, and to this aim we add target indications to the objects produced by a rule as above (to the objects from multiset v). These indications are: here, i n, out, with the meaning that an object having associated the indication here remains in the same r egion, one having associated the indication in goes immediately into a directly lower 8 EFTA01145250 membra ne, non-deterministically chosen, and out indicates that the object has to exit the membrane, thus b ecoming an element of the region surrounding it. An example of evolution rule is aab (a, here)(b, out)(c, here)(c, in) (this is the first of the rules considered in Section 4, with target indications associated with the objects produced by rule application ). After using this rule in a given region of a membrane structure, two copies of a and one b are con sumed (removed from the multiset of that region), and one copy of a, one of b, and two of c are pr oduced; the resulting copy of a remains in the same region, and the same happens with one copy of c (indications here), while the new copy of b exits the membrane, goin g to the surrounding region (indication out), and one of the new copies of c enters one of the child membranes, non- deterministically chosen. If no such child membrane exists, that is, the membrane with which the r ule is associated is elementary, then the indication in cannot be followed, and the rule cannot be applied. In t urn, if the rule is applied in the skin region, then b will exit into the environment of the system (and it is " lost" there, as it can never come back). In general, the indication here is not specified (an object wi thout an explicit target indication is supposed to remain in the same region where the rule is applied). It is important to note that in this initial type of systems we are going to describe we do not provide similar rules for the environment, as we do not care about the objects present there; later we will consider types of P systems where also the environment takes part in the system evolution. A rule as above, with at least two objects in its left hand side, is said to be cooperative; a particular case is that of catalytic rules, of the form ca cv, where c is an object (called catalyst) which assists the object a to evolve into the multiset v; rules of the form a —) v, where a is an object, are called non-cooperative. The rules can also have the form u vo, where (S denotes the acti on of membrane dissolving: if the rule is applied, then the corresponding membrane disappears and its contents , object and membranes alike, are left free in the surrounding membrane; the rules of the dissolved membrane d isappear at the same time with the membrane. The skin membrane is never dissolved. The communication of objects through membranes reminds the fact that the biological mem- branes contain various (protein) channels through which the molecules can pass (in a passive way, due to concentration difference, or in an active way, with a consumption of energy), in a rather selective manner. However, the fact that the communication of objects front a com- partment to a neighboring compartment is controlled by the "reaction rules" is mathematically attractive, but not quite realistic from a biological point of view, that is why there were also considered variants where the two processes are separated: the evolution is controlled by rules as above, without target indications, and the communication is controlled by specific rules (by symport/antiport rules). It is also worth noting that evolution rules are stated in terms of names o f objects, while their application/execution is done using copies of objects — remem ber the example from Section 4, where the multiset asb2c6 was processed by a rule of the form aab —) a(b, out)c(c, in), which, in the maximally parallel manner, is used twice, for the two possible sub-multisets aab. We have arrived in this way at the important feature of P systems, concerning the way of using the rules. The key phrase in this respect is: in the maximally parallel manner, non- deterministically choosing the rules and the objects. More specifically, this means that we assign objects to rules, non-deterministically choosing the objects and the rules, until no further assignment is possible. More mathematically stated, we look to the set of rules, and try to find a multiset of rules, by assigning multiplicities to rules, 9 EFTA01145251 with two properties: (i) the multiset of rules is applicable to the multiset of objects available in the respective region, that is, there are enough objects in order to apply the rules a number of times as indicated by their multiplicities, and (ii) the multiset is maximal, no further rule can be added to it (because of the lack of available objects). Thus, an evolution step in a given region consists in finding a maximal applicab le multiset of rules, removing from the region all objects specified in the left hand of the chosen rules (with the multiplicities as indicated by the rules and by the number of times each rule is used), producing the objects from the right hand sides of rules, and then distributing these objects as indicated by the targets associated with them. If at least one of the rules introduces the dissolving action 8, then the membrane is dissolved, and its contents become part of the immediately upper membrane — provided that this membrane was not dissolved at t he same time, a case where we stop in the first upper membrane which was not dissolved (at least the skin r emains intact). 8 A Formal Definition of a Transition P System Systems based on multiset-rewriting rules as above are usually called trans ition P systems, and we preserve here this terminology (although "transitions" are present in all types of systems). Of course, when presenting a P system we have to specify: the alphabet of objects (a usual finit e non-empty alphabet of abstract symbols identifying the objects), the membrane structure (it can be represented in many ways, but the most used one is by a string of labelled matching parentheses), the multisets of objects prese nt in each region of the system (represented in the most compact way by strings of symbol-o bjects), the sets of evolution rules associated with each region, as well as the indication about the way the o utput is defined — see below. Formally, a transition P system (of degree rn) is a construct of the form H= (O,C,pon -i,w2,• • • I Wrn, R15 R2, • • • fi rn,job where: 1. O is the (finite and non-empty) alphabet of objects, 2. C C O is the set of catalysts, 3. µ is a membrane structure, consisting of m membranes, labelled with 1,2, ..., m; one says that the membrane structure, and hence the system, is of degree in, 4. un, w2,..., tvo, are strings over O representing the multisets o f objects present in the regions 1,2, ... In of the membrane structure, 5. R25 . .. ,Ro, are finite sets of evolution rules associated wi th the regions 1, 2, ... , m of the membrane structure, 6. io is either one of the labels 1, 2, ... ,m, and then the respective r egion is the output region of the system, or it is 0, and then the result of a computation is collected in the environment of the system. The rules are of the form u v or u v8, with u E O+ and v E (O x Tar)', where" Tar = (here, in, out}. The rules can be cooperative (with it arbitrary), non-cooperative (with 'By V' we denote the set of a0 strings over an alphabet V, the empty string lambda included, and by V+ we denote the set V' — {A}, of all non-empty strings over V. 10 EFTA01145252  E 0 - C), or catalytic (of the form ea cv or ca coo, with a E 0 - C, c E C, v E ((0 - C) x Tar)*) ; note that the catalysts never evolve and never change the region, they only help the other objects to evolve. A possible restriction about the region it, in the case when it is an internal one is to consider only regions enclosed by elementary membranes for output (that is, it, should be th e label of an elementary membrane of µ). In general, the membrane structure and the multisets of objects from its compart ments identify a configuration of a P system. The initial configuration is given by specifying the membra ne structure and the multisets of objects available in its compartments at the beginning of a computation, hence (p, wi, During the evolution of the system, by means of applying the rules, both the multisets of o bjects and the membrane structure can change. We will see how this is done in the next section; here we conclude with an example of a P system, represented in a pictorial way in Figure 3. It is important to note that adding to the initial configuration the set of rules, placed in the corresponding regions, we have a complete and co ncise presentation of the system (the indication of the output region can also be added in a suitable manner, for instance, writing "output" inside it). 1 Figure 3: The initial configuration of a P system, rules included 9 Defining Computations and Results of Computations In their basic variant, membrane systems are synchronous devices, in the sense t hat a global clock is assumed, which marks the time for all regions of the system. In each time unit a transformation of a configuration of the system — we call it transition — takes place by applying the rules in ea ch region, in a non-deterministic and maximally parallel manner. As explained in th e previous sections, this means that the objects to evolve and the rules governing this evolution are chosen in a non-deterministic way, and this choice is "exhaustive" in the s ense 11 EFTA01145253 that, after the choice was made, no rule can be applied in the same evolution st ep to the remaining objects. A sequence of transitions constitutes a computation. A computation is successful if it halts, it reaches a configuration where no rule can be appli ed to the existing objects, and the output region it, still exists in the halting configuration ( in the case when it, is the label of a membrane, it can be dissolved during the computation). With a success ful computation we can associate a result in various ways. If we have an output region specified, and this is an internal region, then we have an internal output: we count the objects present in the output region in the halting configuration and this number is the result of the computation. When we have it, = 0, we count the objects which leave the system d wring the computation, and this is called external output. In both cases the result is a number. If we distinguish among different objects, then we can have as the result a vector of natural numb ers. The objects which leave the system can also be arranged in a sequence according to the moments when they exit the skin membrane, and in this case the result is a string (if several objects exit at the same tim e, then all their permutations are accepted as a substring of the result). Note that non-halting computations provi de no output (we cannot know when a number is "completely computed" before halting), and if the output membrane is dissolved during the computation, then the computation aborts, no result is obtained (of course, this makes sense only in the case of the internal output). A possible extension of the definition is to consider a terminal set of ob jects, T C 0, and to count only the copies of objects from T, discarding the objects from 0—T pre sent in the output region. This allows some additional leeway in constructing and "programming" a P system , because we can ignore some auxiliary objects (e.g., the catalysts). Because of the non-determinism of the application of rules, starting from an initial config- uration, we can get several successful computations, hence several results. Thus, a P sys tem computes (one also uses to say generates) a set of numbers (or a set of vectors of numbers, or a language, depending on the way the output is defined). The case when we get a la nguage is important in view of the qualitative difference between the "loose" data structure we use inside the system (vectors of numbers) and th e data structure of the result, strings, where we also have a "syntax", a positional information. For a given system H we denote by N(II) the set of numbers computed by Pi in the above way. When we consider the vector of multiplicities of objects from the output region, we w rite Ps(II). In turn, in the case when we take as (external) output the strings of objects leaving the system , then we denote the language of these strings by L(II). Let us illustrate the previous definitions by examining the computations of the system from Figure 3 — with the output region being the environment. We have objects only in the central membrane, that with label 3, hence only here we can apply rules. Specifically, we can repeatedly apply the rule a ab in parallel with f f f, and in this way the number of copies of b grows each step by o ne, while the number of copies of f is doubled in each step. If we do not apply the rule a a (again in parallel with f ff), which dissolves the membrane, then we can continue in this way forever. Thus, in order to ever h alt, we have to dissolve membrane 3. Assume that this happens after n > 0 steps of using the rules a raab and f f f. When membrane 3 is dissolved, its contents (n+ 1 copies of b, 29i}1 copi es of f, and one copy of the catalyst c) are left free in membrane 2, which now can start using its rules. In the next step, all objects b become d. Let us examine the rule s f f f and cf ca. The second rule dissolves membrane 2, hence passes the contents of this membrane to membrane 1. If among the objects which arrive in membrane 1 there is at least one copy of 12 EFTA01145254 f, then the r ule f -) f from region 1 can be used forever and the computation never stops; moreover, if the rule f f f is used at least once in parallel with the rule cf —) cdd, then at least one copy of f is present. Therefore, the rule cf cdd s hould be used only if region 2 contains only one copy of f (note that, because of the catalyst, the rule cf aid can be used only for one copy of f). This means that the rule ff f was used always fo r all pairs of f available, that is, in each step the number of copies of f is divided by 2. This is alrea dy done once in the step when all copies of b become d, and will be done from now on as long as at le ast two copies of f are present. Simultaneously, in each step each d produces one copy of e. This pr ocess can continue until we get a configuration with only one copy of f present; at that step we have t o use the rule cf cdd (the rule ff —) f is no longer applicable), hence also membrane 2 is dissolved . Because we have applied the rule d —) de, in parallel for all copies of d (there are n + 1 such copi es), during n + 1 steps, we have (n + 1)(n + 1) copies of e, n + 2 copies of d (one of them was produced by the rule cf —) aid), and one copy of c present in the skin membrane of the system (the unique membrane still present). The objects e are sent out, and the computation halts. Thereto re, we compute in this way the number (n + 1)2, for some n > 0, that is, N(II) = {n2 n > 11. 10 Using Symport and Antiport Rules The multiset rewriting rules correspond to reactions taking place in the cell, inside the compart- ments. However, an important part of the cell activity is related to the passage of sub stances through membranes, and one of the most interesting ways to handle this trans-membrane com- munication is by coup ling molecules. The process by which two molecules pass together across a membrane (through a specific prote in channel) is called symport when the two molecules pass simultaneously through a protein channel, but in opp osite directions, the process is called antiport. We can formalize these operations in an obvious way: (ab, in) or (ab, out) are symport rules, stating that a and b pass together through a membrane, entering in the former case and exiting in t he latter; similarly, (a, out; b, in) is an antiport rule, stating that a exits and at the same time b enters the membrane. Separately, neither a nor b can cross a membrane — unless we have a rule of the form (a, in) or (a, out), called, for uniformity, uniport rule. Of course, we can generalize these types of rules, by considering symport rules of the form (x, (x, out), and antiport rules of the form (z, out; w, in), where x, z, w are multisets of arbitr ary size; one uses to say that is the weight of a symport rule as above, and maxazi, Iwl) is the weight of the antiport rule2. Now, such rules can be used in a P system instead of the target indications here, in, out we consider multiset rewriting rules of the form u —. v (or 11 —) v6) without target indications associated with the objects from v, as well as symport/antiport rules for communicating the ob jects among compartments. Such systems, called evolution-communication P systems, were considered in [23] (for various restricted types of rules of the two forms). Here we do not go into this direction, but we stay closer both to the chronologi cal evolution of the domain, and to the mathematical minimalism, and we check whether we can compute using only communic ation, that is, only symport and antiport rules. This leads to considering one of the most interesting classes of P systems, which we formally introduce here. 2 By lul we denote the length of the string u E V', for any al phabet V. 13 EFTA01145255  A P system with symporl/antiport rules is a construct of the form H = (0, A, to', ...,w„„ E, Ri, R„„i„), where: 1. 0 is the alphabet of objects, 2. µ is the membrane structure (of degree m > 1, with the membranes la belled in a one-to- one manner with 1, 2, ...,m), 3. till, ..., w„, are strings over 0 representing the multisets of objects present in the m com- partments of A in the initial configuration of the system, 4. E C 0 is the set of objects supposed to appear in the environment in arbitrarily many copies, 5. R,„ are the (finite) sets of rules associated with the m mem braves of µ, 6. io E H is the label of a membrane of µ, which indicates the output region of the system. The rules from R can be of two types, symport rules and antiport rules, of the forms as specified above. The rules are used in the non-deterministic maximally parallel manner. In the usual way, we define transitions, computations, and halting computations. The number (or the vector of multiplicities) of objects present in region io in the halting configuration is said to be computed by the system along that computation; the set of all numbers (resp., vectors or num bers) computed in this way by H is denoted by N(II) (resp., by Ps(II)). We remark here a new component of the system, the set E of objects which are present in the environment in arbitrarily many copies; because we only move objects across membranes and because we start with finite multisets of objects present in the system, we cannot increase the number of objects necessary for the computation if we do not provide a supply of objects, and this can be done by considering the set E. Because the environment is supposed inexhaustible, the objects from E are supposed inexhaustible, irrespective how many of them are brought into the system, arbitrarily many remain outside. Another new feature is that this time the rules are associated with the membrane s, not with the regions, and this is related to the fact that each rule governs the communication through a specific membrane. The P systems with symport/antiport rules have a series of attractive characteri sties: they are fully based on biological types of multiset processing rules; the environment takes a direct pa rt into the evolution of the system; the computation is done only by communication, no object is changed, the objects only move across membranes; no object is created or destroyed, hence the conservation low is obse rved. (as given in the previous sections, this is not valid for multiset rewriting rules, because, for instance, rules of the forma as or f f -.fare allowed, but by using some dummy objects d available in arbitrarily many copies, we can take care of the conservation low by writing, e.g., da as and f f f d). 14 EFTA01145256 11 An Example (Like a Proof... ) Because P systems with symport/antiport rules constitute an important class of P systems, it is worth considering an example; however, instead of a simple example (actually, it is not very easy to find simple symport/antiport systems computing non-trivial sets of numbers), we give directly a general construction, for simulating a register machine. In this way, we also introduce one of the widely used proof techniques for the universality r esults in this area. (Of course, the biologist reader can safely skip this section.) Informally speaking, a register machine consists of a specified number of counters (also called registers) which can hold any natural number, and which ar e handled according to a program consisting of labelled instructions; the counters can be increased or decreased by 1 — the decreasing being possible only if a counter holds a number greater than or equal to 1 (we say that it is non-empty) —, and checked whether they are non-empty. Formally, a (non-deterministic) register machine is a device M