General Topologies and P Systems

General Topologies and P Systems Erzs´ebet Csuhaj-Varj´u1, Marian Gheorghe2,3, and Mike Stannett2 1Department of Algorithms and Their Applications Faculty of Informatics, E¨otv¨os Lor´and University, P´azm´any P´eter st. 1/c, Budapest, 1117, Hungary [email protected] 2Department of Computer Science, The University of Sheffield Regent Court, 211 Portobello, Sheffield S1 4DP, United Kingdom {M.Stannett, M.Gheorghe}@dcs.shef.ac.uk 3Department of Computer Science, University of Pite¸sti Str Targu din Vale, Pite¸sti, Romania Summary. In this paper we investigate the use of general topological spaces as control mechanisms for membrane systems. For simplicity, we illustrate our approach by showing how arbitrary topologies can be used to study the behaviour of membrane systems with rewrite and communication rules. 1 Introduction Membrane computing has emerged in the last more than ten years as a vigorous research field as part of natural computing or unconventional computing. It is a nature-inspired computational paradigm including a large variety of models, called membrane systems, well-investigated from a computational perspective, especially with respect to their computational power and complexity aspects [9]. A number of promising applications, mainly in biology, but also in distributed computing, linguistics and graphics [1], have been identified and described. The key features of a membrane system are a set of compartments (called regions) delimited by membranes,multisets of objects contained in these regions, transformation and communication rules describing interactions between objects, and a strategy for evolving the system. This basic model is inspired by standard models of the structure and functions of a typical eukaryotic cell, comprising multiple compartments containing localised biochemical materials and reactions: various chemical entities with different levels of complexity react under specified circumstances to produce new biochemicals supporting the cell’s life and metabolism, and these may or may not be transported to other compartments depending on context. Many variants of membrane system have been considered, some using different types of biochemical agent and interaction, others using various types of structural organisation for the compartments and their connections [9]. 80 E. Csuhaj-Varju, M. Gheorghe, M. Stannett Membrane systems introduce in a very natural way a specific topology on the system described, in which membranes delimit compartments containing local objects and interaction rules, together with specific links between compartments. These links describe communication channels allowing adjacent compartments to exchange chemicals. Although this topology is flexible enough to cope with the challenge of modelling various natural or engineering systems, there are cases when a finer grain topological structure is required. In a series of papers, J.-L. Giavitto and his collaborators have investigated the use of topological transformations applied to various data structures, where algebraic topology helps in defining the appropriate data sets selected to be transformed [2]. The use of this approach to model various elements and transformations occurring in membrane computing has been investigated in [4], while concepts related to a spatial computing programming paradigm, which permit the definition and handling of a sort of geometry, have been described in the context of the unconventional programming language, MGS [7]. In this paper we investigate the use of topological spaces as control mechanisms for membrane systems. While the algebraic topological approach shows how the membrane structure and its basic operations with multisets can be represented, here we use a topological space as a framework to control the evolution of the system with respect to a family of open sets that is associated with each compartment. This approach produces a fine grain description of local operations occurring in each compartment by restricting the interactions between objects to those from a given neighbourhood. This initial study shows the influence of an arbitrary topology on the way basic membrane systems compute. In future work (cf. Sect. 5) we aim to investigate the role of more specific topologies, their impact on other types of membrane system, and their applications in solving/approaching various problems. 2 Basic notations and definitions We briefly recall basic notions concerning P systems. For more details on these systems and on P systems in general, we refer to [8, 9]. A basic evolutioncommunication P system (P system for short) of degree nis a construct Π= (O, µ, w1,...,wn, R1,...,Rn, i0) where 1. Ois a finite alphabet of symbols called objects; 2. µis a membrane structure consisting of nmembranes that are labelled (in a one-one manner) with elements from a given alphabet A; these membranes are organised in a hierarchical way, like a tree, with the top membrane (root) called the skin membrane, and the bottom ones (leaves) called elementary membranes; General Topologies and P Systems 81 3. for each 1 ≤i≤n,wi∈O∗is a multiset of objects associated with the region i(this is the region delimited by membrane i, but not including the subregions delimited by i’s children); 4. for each 1 ≤i≤n,Riis a finite set of rules associated with the region i, of the form u→(v1, tar1)...(vm, tarm), where u∈O+,vj∈Oand tarj∈ {in, out, here}(1 ≤j≤m); when tarjis here, we write simply vjin place of (vj, tarj); 5. i0is the label of an elementary membrane of µthat identifies the corresponding output region. A P system is interpreted dynamically as a computational device comprising a set of nhierarchically nested membranes that identify ndistinct regions (the membrane structure µ), where each region i= 1,...,n contains a multiset of objects (wi) and a finite set of evolution rules (Ri) of the form u→(v1, tar1)...(vm, tarm). This rule removes multiset ufrom region i, and then adds each multiset vj (1 ≤j≤m) to the multiset of objects in the corresponding target region tarj. •If tarjdoes not appear in the notation (by convention this occurs when the target is here), then vjremains in membrane i; •If tarjis out, then vjis sent to the parent membrane of i; if iis the skin membrane then vjis sent out of the system; •If tarjis in, then vjis sent to one of the inner membranes of i(if there is more than one child, the target is chosen non-deterministically); •The in target can be replaced by a precisely defined destination region. If region kis a child of iand tarjis k, then vjis sent to k. A computation of the system is obtained by applying the available rewrite rules in a non-deterministic maximally parallel manner4, where each region iinitially contains the corresponding finite multiset wi. A computation is considered successful when it starts from the initial configuration and reaches a configuration where no further rules can be applied. Its result, a natural number, is obtained by counting the objects present in region i0on completion (other ways of interpreting the result of a P system computation are also considered in the literature [9]). Given the non-deterministic nature of P system computation, different runs of a given system may generate different results. For a given P system Πthe set of numbers that can be computed is denoted N(Π). Recall that rewrite rules are of the form u→(v1, tar1)...(vm, tarm), where uis a multiset. If in each of the rules in Πthe multiset ucontains only a single object, then Πis called a P system with non-cooperative rules; otherwise it is a P system with cooperative rules. When tarj=in the rule is said to have arbitrary target, and when tarj=inkfor a specific region k, it has a selected target. 4A simultaneous application of rewrite rules is non-deterministic maximally parallel provided the applied rules are chosen non-deterministically (possibly with repetition), and there are insufficient resources to trigger the simultaneous application of any additional rule. 82 E. Csuhaj-Varju, M. Gheorghe, M. Stannett 2.1 Topological conventions Our notation will generally follow that of [10]. Given any non-empty set X, its power set will be denoted ℘X. We write ∅for the empty set. A topology on Xis any subset of ℘X containing both ∅and X, which is closed under arbitrary unions and finite intersections; the members of Tare open (or T-open where ambiguity might otherwise arise). The topology {∅, X}is the indiscrete topology on X; the topology in which every singleton {x} ∈ ℘X is open is the discrete topology. An open cover of A⊆Xis a subset of Twhose union contains A. The complement of an open set is closed. The closure A= ClsX(A) of a set A⊆Xis the intersection of all closed sets containing A; it is the smallest such set. The interior A◦= IntX(A) of Ais the union of all open sets contained in A; it is the largest such set. The difference between the closure and interior of a set is its boundary,∂A =A\A◦. Any topology Tcan also be regarded as a partially ordered set (poset) ordered by set inclusion. If (Y, ≤) is a poset, an order embedding of Yin Tis an injection ı:Y→ T such that y1≤y2if and only if ı(y1)≤ı(y2). 3 Control structures For the purposes of this paper, a P system can be regarded structurally as a tree whose nodes are the membranes, together with a function mapping each node p in Πto a corresponding multiset over A. This multiset tells us how many copies of each object lie in the region situated between the membrane and its internal sub-membranes; see Fig. 1. abbd bb abb bcccb aab abc 1 2 3 4 5 6 (a) tree bb aab abc bcccb abb abbd 4 12 3 5 6 (b) nested membranes Fig. 1. A generic P system structure represented as (a) a tree; (b) a set of nested membranes. In each membrane and in any computation step it is assumed that all the objects present in the corresponding region can freely interact according to the General Topologies and P Systems 83 set of rules available in that region. Maximal parallelism also implies that all the objects that might take part in various interactions must interact (each object takes part in at most one interaction). While this scheme is easy to implement, it distorts to some extent the biological intuition that interactions are local. It is not enough that two chemicals are present in a cell, they must also be located close to one another, but the regions of a P system are not inherently associated with any notion of separation distance. We will therefore order-embed the membranes of the P system as open sets within an essentially arbitrary topology, and use (finite) open covers to provide an indication of the distance between two objects. We then consider how the choice of topology affects the computations that can be implemented. In general the members of an open cover need not be disjoint. Region 4 of Fig. 1 contains the multiset bcccb. Figure 2 illustrates a covering of this region by three open sets: A4,1,A4,2and A4,3. The open set A4,2contains cc, and each of the others contains bc. Initially we only consider open covers of regions; subregions of the enclosing membrane will be equipped with covers in their own right. bb aab abc bcccb abb abbd 4 12 3 5 6 (a) Nested membranes (region 4 highlighted) A4,2 A4,3 A4,1 bc b c c (b) Open covering of region 4 Fig. 2. Covering of region 4 by open sets. The topologically controlled computation that takes place with respect to these open sets is defined as follows: rules associated with membrane iare enabled if and only if there is a member of the open cover which contains all of the participating objects. If any target of an enabled rule is here, the associated products should then be placed back into the same open set (if the initial objects lie in more than one member of the cover, we choose one at random and place the associated results there; they need not be injected back into the intersection). Otherwise if the target is tar (where tar is assumed to carry its own open cover), the output will be placed in an arbitrary member of tar’s cover. 84 E. Csuhaj-Varju, M. Gheorghe, M. Stannett Despite the intrinsically local nature of controlled computation, the locus of computation can migrate from one compartment to another one via non-empty overlap regions, as the following example illustrates. Figure 3 shows the disjoint parts, B4,1–B4,7, of region 4’s cover. These are all of the form U\Vwhere Uand V are open; for example B4,3= (A4,1∩A4,2∩A4,3)\∅, and B4,1=A4,1\(A4,2∪A4,3). A4,2 A4,3 A4,1 bc b c c (a) Open cover B4,5 B4,6 B4,7 B4,4 B4,3 B4,2 B4,1 (b) Overlap regions A4,1 A4,2 A4,3 (c) Key to boundaries Fig. 3. The finite covering of region 4 and its disjoint overlap regions. Suppose, then, that region 4 has the following rules associated with it: r1:bc →b;r2:bcc →c;r3:cc →c. If we consider the system as a P system with no topological control in place, the following computations can take place: 1. bc c cb r1,r1 ===⇒bcb r1 ==⇒bb 2. bc cc b r1,r3 ===⇒bcb r1 ==⇒bb 3. bc ccb r1,r2 ===⇒bc r1 ==⇒b But when the open sets are in place computation path 3 is blocked, because none of the open sets ever contains bcc, whence r2cannot be triggered. We have the following two cases instead: 1’ r1is applied in both A4,1and A4,3resulting in a copy of bin each of these open sets; if b∈A4,3is not in A4,2∩A4,3the computation stops here with bbc scattered across different open sets. If, on the other hand, b∈A4,2∩A4,3then the computation can continue; after applying r1in A4,2a copy of bis obtained in each of A4,1and A4,2. In this case the result is the same as that obtained in (1); General Topologies and P Systems 85 2’. r3, r1result in copies of b∈A4,1and c∈A4,2; as in (1’) this ccan reside either in the intersection or outside it; in the first case r1can be applied again and b is computed (so that the result from (2) is obtained). Otherwise bbc will remain in the membrane unchanged. Consider in particular the second case of the first step of (1’). After r1is applied in A4,3the result bcan be considered to lie in A4,2, whence (as suggested above) the locus of computation can migrate from A4,3to A4,2via their intersection. A similar situation occurs in (2’) as well. More generally, suppose that region ihas a rule whose target is region j. We will allow the rule to be triggered only when the two regions are sufficiently close to one another (their boundaries must intersect: ∂i ∩∂j 6=∅). In this case, and provided all of the required components are available within a single member of i’s cover, the rule can fire with the resulting multiset vjbeing injected into an arbitrarily selected member of j’s cover. In future work we plan to investigate what happens when this restriction is weakened, so that interactions can occur between non-neighbouring regions. Definition 1 (Output of a controlled computation). For a P system Πand associated topology Tthe set of numbers computed by Πwhen controlled by Twill be denoted NT(Π).⊓⊔ Having now defined controlled computation, we will address the following problems. In Sect. 4 we discuss the role of a control mechanism based on an associated topology and show how a general topology influences the computation for a basic class of P systems. In Sect. 5 we summarise our findings and discuss future research topics related to various topologies associated with classes of P systems. 4 Basic Results We will first consider P systems with non-cooperative rules. Lemma 1. For any P system with non-cooperative rules and either arbitrary targets or selected targets, Π, and any associated topology T,N(Π) = NT(Π). Proof. In a P system with non-cooperative rules the left hand side of any rule has only one single object, hence no interactions are involved. In this case it is obvious the the topology Tdoes not influence the computation for either P systems with arbitrary targets or selected targets, hence the result stated holds. ⊓⊔ For P systems with cooperative rules the situation is totally different and the topologies associated with them may lead to different computations and distinct results. Lemma 2. There is a P system with cooperative rules and either arbitrary or selected targets, Π, such that for any associated topology Twhere for at least one region not all the objects belong to the same open set, it follows that N(Π)6= NT(Π). 86 E. Csuhaj-Varju, M. Gheorghe, M. Stannett Proof. Let us consider Π= (O, µ, w1, w2, R1, R2, i0), where O={a, b, c},µ= [[]2]1,w1=ab,w2=λ,R1={ab →c, c →(c, in)},R2=∅,i0= 2. This system uses an arbitrary target, which, in this case, is the same as selected target, in2. This P system computes cin two steps in the output region, 2. Any topology, T, associated with Πthat provides a cover for region 1 with more than an open set, must have an open set for aand another one for band their intersection does not contain any of these two objects; otherwise, aand bwill stay in the same open set. In this case the rule ab →ccan not be applied and consequently cis never obtained in the output region, hence N(Π)6=NT(Π). ⊓⊔ Theorem 1. For any P system with either arbitrary or selected targets, the computation and the topologically controlled computation are the same when noncooperative rules are used and are not in general the same for cooperative rules. Proof. The proof is an immediate consequence of Lemmas 1 and 2. ⊓⊔ There are P systems with cooperative rules where the content of the regions can be matched against the open sets in such a way that the computation is equivalent to the computation of the original system. Indeed let us consider the problem of checking that a positive integer mis divided by another positive integer k. We propose a P system below which is an adaptation of the P system presented in [9]. Example 1. Let us consider Π= (O, µ, w1, w2, R1, R2, i0), where O={a, b, c, y, n}, µ= [[]2]1,w1=ambk,w2=y,R1={r1:ab →c, r2:ac →b, r3:bc →(n, in)}, R2={yn →n},i0= 2. In the first step at most kobjects ab are replaced by the same number of objects c(using r1at most ktimes) and then objects ac are replaced by objects b(using r2). If kdivides mthen the process will stop after hsteps, where m=kh, and in membrane 2 will remain y; otherwise in membrane 1 the process of alternatively applying rules r1and r2will stop with some objects band objects cand the rule r3can be used. In this case nis sent into region 2 and finally nis obtained in this region. Now, if we aim to obtain the same results in region 2, i.e., y, when kdivides m, or notherwise, then we have to build the topology, T, associated with Πin a certain way which is subsequently described. Region 2 is covered by only one single open set and region 1 will have an arbitrary number of open sets, q > 1, associated with. Any two such open sets are disjoint. The objects will be distributed as follows: the k b′s will be randomly distributed in q−1 of the qopen sets, bk1,...,bkq−1, ki≥0 and k1+· · · +kq−1=k. If m=kh +r, then in each of the q−1 open sets containing kib′s, the number of a′s is hkia′s. If r > 0 then one more awill be consider in one of the q−1 open sets with b′s and the rest will be associated with the qth open set. Clearly, in each of the q−1 open sets the computation will go for hsteps. In q−2 of them it will be obtained either only b′s or only c′s; the open set with an additional ain it will end up after one more step with a mixture of b′s and c′s and the rule r3will push an ninto membrane 2 and finally will get nin this membrane. Objects a′s occurring in the qth open set will remain there forever. It follows that N(Π) = NT(Π). ⊓⊔ General Topologies and P Systems 87 The question of whether the control structure introduced by a topology can be ignored, perhaps by using a more complex P system, is answered by the following result. This takes into account the interpretation of the outcome of the computation as being the number of objects, given by the size of the multiset, present in the output region. Theorem 2. For any P system, Π, and any associated topology, T, there is a P system, Π′, of the same degree with Π, such that NT(Π) = N(Π′). Proof. The idea of the proof is to construct a new P system such that objects belonging to a region adequately refer to objects of the open sets in the corresponding regions of the initial P system. Let Πbe a P system of degree n,Π= (O, µ, w1,...,wn, R1, . . . , Rn, i0), and Ta topology associated with it. In order to build a new P system, Π′, of degree n, a few preliminary notations are made. First, please observe that for each region i, 1≤i≤n, there exists a family of open sets Ai,1,...,Ai,kicovering it. In general these open sets are not disjoint and we describe the finest disjoint parts of the cover by considering either some intersections of open sets or the complement of an open set with respect to the rest of the open sets; it follows that there exists a finite set, denoted Bi, containing the sets Bi,1,...,Bi,mi, such that Bi,j denotes either Ai,l1∩· · ·∩Ai,lj, 1 ≤lj≤kior Ai,j \(Ai,1∪ · · ·∪Ai,j−1∪Ai,j+1 ∪ · · ·∪Ai,ki). The set of indexes of the above sets Bi,j is denoted by Ci, i.e., Ci={(i, j)|Bi,j ∈Bi}. Each object, a∈O, of the multiset from region ibelongs to a certain Bi,j. For each afrom Bi,j, the following objects are considered, aα, α ∈Ci. The P system Π′, of degree n, is built as follows: Π′= (O′, µ, w′ 1,...,w′ n, R′ 1,...,R′ ni0), where: 1. O′={aα|a∈O, α ∈Ci,1≤i≤n}; 2. µis the membrane structure of Π; 3. w′ i=a(i,r1) i,1. . . a(i,rpi) i,pi, where ai,j ∈Bi,rj, 1 ≤j≤pi, for wi=ai,1. . . ai,pi, initial multiset of Π; 4. for each rule ai,1. . . ai,qi→bi,1. . . bi,si∈Ri,R′ icontains a(i,r1) i,1. . . a(i,rqi) i,qi→ b(i,s1) i,1. . . b(i,spi) i,pi, (i, rj)∈Ci,1≤j≤qi, (i, sj)∈Ci, 1 ≤j≤piwhen a target, t, appears on the right hand side of the rule from Ri, associated with an object bi,j, then the target will point to any of the open sets At,j of the target region t; 5. Πand Π′have the same output membrane, i0. The codification provided by Π′allocates, in a unique way, in every region, i, each object, a, to a specific open set, by “stamping” it with the corresponding index, (i, j)∈Ci, of the set Bi,j. Whenever a rule is applied, the resulted multiset is also composed of objects uniquely associated with certain open sets, either from the current region or from the target ones.