Weak Metrics on Configurations of a P System

Weak Metrics on Configurations of a P System Andr´es CORD ´ ON-FRANCO, Miguel A. GUTI´ ERREZ-NARANJO, Mario J. P´ EREZ-JIM´ ENEZ, Agust´ın RISCOS-N ´ U˜ NEZ Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {acordon,magutier,marper, ariscosn}@us.es Abstract. The evolution of a P system generates a tree of computation potentially infinite where it is very difficult to set the degree of closeness between two configurations. The problem is specially hard if we want to quantify that proximity in order to make useful comparisons. In this paper we propose some weak metrics on configurations of a P system with a fixed structure of membranes and briefly discuss their advantages and drawbacks. 1 Introduction In [2], a new model of computation within the framework of Natural Computing was introduced, called P Systems1. It starts from the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations. Roughly speaking, a P system consists of a cell-like membrane structure, in the compartments of which one places multisets of objects which evolve according to given rules in a synchronous, parallel, and non-deterministic manner. The membrane structure of a P system is a hierarchical arrangement of membranes embedded in a skin membrane, the one which separates the system from its environment. A membrane without any membrane inside is called elementary. Each membrane defines aregion (the closed space delimited by a membrane and by the membranes immediately inside it). The membrane structure of a P system is used to enclose computing cells in order to make them independent computing units. Also, a membrane serves as a communication channel between a given cell and other cells adjacent to it. The objects can pass through membranes and the membranes can be dissolved, divided, or created. Aconfiguration is the instantaneous description of the current membrane structure and the multisets of objects associated with the membranes. In each time unit a transformation of a configuration of the system takes place by applying the rules of each region in a nondeterministic and maximally parallel manner. In this way, one gets transitions between the configurations of the system and a sequence of transitions is called a computation. In certain circumstances, we need to know how different two configurations of a P system are. They can be different in many senses and the problem turns extremely hard 1A layman-oriented introduction can be found in [3] and further bibliography at [5]. 139 when the configurations do not correspond to the same P system. If we have three configurations C1,C2and C3, is C1more different from C2than from C3? Is it possible to quantify this degree of similarity and give it an algebraic treatment? In this paper we study the differences among configurations and we propose a way to quantify the degree of difference. We offer some solutions to the problem of finding appropriate metrics for P systems. We focus our attention only on finding metrics on the configurations of a P system with a fixed membrane structure. This involves a fixed alphabet and a fixed set of rules. In this case, two configurations may only differ in the multisets associated with the membranes. This difference can be measured between configurations not necessarily in the same branch of a computation or in the same step. We propose two models of defining metrics. The first one is based on the distance between regions. This gives us a very natural way of defining the distance according to the difference between multisets, but it does not consider the set of rules of the P system. The second model is based on the dependency graph associated with the rules of a P system and is based on the shortest paths in this directed graph. The paper is organized as follows. Section 2 recalls some ideas about metrics and weak metrics in a general setup. In Section 3 two metrics on configurations of P systems based on the different multisets of regions are presented. In Section 4 a new concept in P system theory is defined: the dependency graph of a P system. This dependency graph is used in Section 5 to define a weak metric on configurations. The paper finish with an example (Section 6) and some final remarks. 2 Metrics Sometimes it is necessary to reduce the relation between two objects to a number in order to make comparisons and also perform algebraic operations with them. This number is used to be called a distance and it allows us to differentiate between pairs of objects in a simple way. So, for instance, we say that two towns Aand Bare closer than the towns C and Dif the length of the shortest path from Ato B(i.e., the distance which separates them) is less than the length of the shortest path from Cto D. Analogously, that distance can measure the time elapsed between two events, the amount of necessary combustible to cover a route, or the number of pieces which are left to complete a puzzle. In this way, if the distance from Ato Bis less than the distance from Ato C, we think that the relation between Aand Bis narrower than the relation between Aand C. Given a set X, if we associate to every pair of elements (x, y)∈X×Xits distance, we get a mapping d:X×X→R. But, obviously, not every mapping d:X×X→Ris a distance. What properties does a mapping d:X×X→Rhave to satisfy in order to be a distance? It is clear that the criterion has to be weak enough to be common to the different distances of geometric intuition and strong enough to settle a solid theory which allows us to deal with the concept of distance in abstract situations. It was M. Fr´echet in his Ph.D. dissertation [1] who stated that it was sufficient that the mapping satisfied •(∀x, y ∈X)d(x, y)=0⇔x=y, •(∀x, y ∈X)d(x, y) = d(y, x)(the condition of symmetry), 140 ◦ ◦ ◦ ◦ ◦ ◦ dedmdr ©©© © Figure 1: Several metrics •(∀x, y, z ∈X)d(x, z)≤d(x, y) + d(y, z)(the triangle inequality), to develop a theory of metric spaces and, since then, they have been considered the basic pillars of the theory. As examples of distances based on the geometric intuition, we can cite three well-known distances in R2. Let A= (x1, y1) and B= (x2, y2) be two points of the plane. •Euclidean distance (de):Given two points Aand Bin R2, the distance demeasures the length of the segment which joins Aand B, i.e., of the shortest path from Ato B, assuming that there are no obstacles in the plane d(A, B) = p(x1−x2)2+ (y1−y2)2. •Manhattan distance (dm):In this case, we also measure the shortest path from A to B, but in contrast to the Euclidean distance, in the Manhattan distance we suppose that the moves can only be horizontal or vertical ones, simulating the movement of a vehicle through streets with a grid form. dm(A, B) = |x1−x2|+|y1−y2|. •Distance of the rainforest (dr):An example, perhaps less known, of distance in R2is this distance of the rainforest which also measures the length of the shortest path between two points. It receives this name because it stands in R2for the situation of a tribe in a rainforest with a river in y= 0. The people of the tribe, to reach the water, have done breaches perpendicular to the river. Due to the thick rainforest, if someone wants to go from Ato B, the only path is by the breaches or on the bank. dr(A, B) = ½|y1−y2|if x1=x2, |y1|+|y2|+|x1−x2|if x16=x2. At this point, it makes sense to wonder why it is necessary to define several distances on the same set. The answer is clear. Every distance is adapted to an earlier structure in the set. If we are only interested in endowing the set with a mapping which satisfies the Fr´echet’s conditions and we do not consider any other previous relation among the members of the set, we can always consider the discrete distance dd(A, B) = ½0 if A=B 1 if A6=B 141 which satisfies the Fr´echet’s conditions to be a distance, but it would hardly have a practical usefulness. A different situation is settled when the pre–existing relation between the objects is not symmetric. The number of kilometers which separate a town Aon the coast from a another at the top of a mountain is independent of the direction of the journey. But if our idea of distance is the number of calories spent by a cyclist from a town to the other, then the condition of symmetry is lost in our definition of distance. A more extreme case is the passage of time. When January 1st 2005 arrives, we will have to wait for 365 days to January 1st 2006, but when January 1st 2005 arrives, it will not make sense to wait for the arrival of the year 2004. Another real life situation in which Fr´echet’s conditions must be weakened occurs when we go shopping. A good pointer to estimate the difference between two items can be the price, but this is not exactly a distance: We can find two distinct items with the same price. 3 Metrics on Regions In this section we propose two metrics on configurations based on the different multiset of the regions in each configuration. For that, we consider a P system with alphabet L and a fixed membrane structure, i.e., dissolution or duplication of membranes are not allowed. Since the membrane structure does not change along different configurations, we also consider that we can identify the same membranes in different configurations2. The metrics are based on the difference between the multisets. Firstly, we define the distance between two regions as the cardinality of the symmetrical difference of their associated multisets. We will use this definition to measure the distance between two occurrences of the same membrane in two different configurations. Definition 3.1 Let us consider a region Rand Lthe alphabet of the P system. The multiset associated with the region R,MR, can be characterized as the mapping MR: L → N. The distance dRbetween the regions R1and R2is defined as dR(R1, R2) = X x∈L |MR1(x)− MR2(x)|, where |.|is the function absolute value. Theorem 3.1 dRis a (weak) metric between regions. 3.1 Plain Metric With the help of the distance dRbetween regions, the definition of the distance between configurations is pretty natural. As set of regions, the difference between configurations is the sum of the differences between their regions. Let Π be a P system in which the structure of membranes does not change during the computation. In this P system, two configurations C1and C2only differ on the multisets associated to the regions, and therefore, if Ri jis the region delimited by the membrane 2This can be done by considering labels, positions or some type of enumeration. 142 mjin the configuration Ci(with j∈ {1, . . . , k}and i∈ {1,2}), then we can consider the additive distance based on the distance between regions d+(C1, C2) = X 1≤j≤k dR(R1 j, R2 j). Theorem 3.2 d+is a (weak) metric between configurations. 3.2 Biased Metric The (weak) metric defined above does not consider the tree structure of the set of membranes. We assume that every membrane has the same importance to measure the closeness between two configurations, so every element has the same weight regardless in which membrane it occurs. Nevertheless, sometimes we can have another point of view. Sometimes, we design P systems where the inner membranes work as parallel devices, sending out to the skin the output of each computation. From this point of view, the objects in the skin, i.e., the result of the parallel computation, are more important than the objects in each inner membrane, since these objects only have a local function. The (weak) metric defined below follows this idea. Firstly we define a recursive distance dBamong regions: If {mj1, . . . , mjsj}are the children of the membrane mj, then we define dB(R1 j, R2 j) = dR(R1 j, R2 j) + Cj· sj X i=1 dR(R1 ji, R2 ji), where Cjis a constant of bias associated with the membrane mj. As a particular case of this definition, we have the situation in which mjis a leave, i.e., mjhas no children; then dB(R1 j, R2 j) = d+(R1 j, R2 j). Finally, to define a mapping in order to quantify the closeness between configurations, we only have to consider the distance between their skins3. If msis the skin membrane, then dB(C1, C2) = dB(R1 s, R2 s). Note that if all the constants of bias are equal to 1, then dr(C1, C2) = d+(C1, C2). Theorem 3.3 dBis a (weak) metric between configurations. 4 Dependency Graphs In this section we explore a new variant of metrics between configurations based on the dependence among elements of the alphabet with respect to the set of rules of the P system. To this aim, we consider the rules of a P system with a new representation and we define the concept of confluence of computations in a more general way than the standard one. The rules of a non-cooperative P system, without dissolution nor division fit into the following schema (e0, µ1)→(e1, µ2),(e2, µ2), . . . , (en, µ2) 3For the sake of simplicity, we keep the same notation dBalso for configurations. 143 which can be interpreted as follows: The occurrence of the element e0in the membrane µ1 triggers the rule and provokes the apparition of the multiset e1e2. . . eninto the membrane µ2.Obviously, if µ1=µ2, then we have an evolution rule, if n= 1 and µ1is a father of µ2, then we have a send-in communication rule, and if µ1is a child of µ2, then we have a send-out communication rule. The pair (e0, µ1) is the left side of the rule and the multiset of pairs (e1, µ2),(e2, µ2), . . . , (en, µ2) is the right side of the rule. Next, we define the graph of dependence of a P system based on this new representation of the rules. Definition 4.1 The dependency graph of a P system Πis a pair GΠ=hVΠ, EΠisuch that VΠis the set of all the pairs (e, µ)where eis an element of the language and µis a membrane and EΠis the set of all the ordered pairs of elements of VΠ,h(e1, µ1),(e2, µ2)i such that (e1, µ1)is the left side of a rule and (e2, µ2) belongs to the right side of a rule. We illustrate this definition with an example. Let us consider the next toy P system Π, with alphabet Γ = {a, b, c, d, z}, membrane structure [s[e]e]sand set of rules: Rule 1: [ea]e→a[e]e Rule 2: [sa]s→a[s]s Rule 3: [ea]e→[ebz]e Rule 4: [eb]e→c[e]e Rule 5: [sc]s→[sdz]s Rule 6: [sd]s→a[s]s In order to define the dependency graph, we have to consider the set of membranes {e, s}, and since the elements can be sent out of the system (rules 2and 6), we will consider a new region outside as a place where the elements can stand, so the set of regions becomes {e, s, outside}. Finally, with the new representation, the rules can be written as follows: Rule 1: (a, e)→(a, s) Rule 2: (a, s)→(a, outside) Rule 3: (a, e)→(b, e),(z, e) Rule 4: (b, e)→(c, s) Rule 5: (c, s)→(d, s),(z, s) Rule 6: (d, s)→(a, outside) Therefore, the dependency graph of Π, GΠ=hVΠ, EΠiis defined by the following sets: VΠ=   (a, e) (b, e) (c, e) (d, e) (z, e) (a, s) (b, s) (c, s) (d, s) (z, s) (a, outside) (b, outside) (c, outside) (d, outside) (z, outside)    The set of vertices VΠhas 15 elements, but 7 of them are isolated vertices: only 8 vertices occur in some edge (see Figure 2). EΠ=            h(a, e),(b, e)i,h(a, e),(z, e)i,h(a, e),(a, s)i, h(a, s),(a, outside)i, h(b, e),(c, s)i, h(c, s),(d, s)i,h(c, s),(z, s)i, h(d, s),(a, outside)i            144 (z,e) (a,e) (b,e) (a,s) (c,s) (z,s) (a,outside) (d,s) ¾ - - - - ? 6 ? (c,outside) (b,outside) (z,outside) (d,outside) (d,e) (c,e) (b,s) Figure 2: The dependency graph Note that the dependency graph only depends on the membrane structure and the set of rules of the P system and not on the elements of the membranes at the initial moment. The example will help us to introduce a new definition of confluence, more general than the usual one. We know the structure of membranes and the set of rules of our toy P system. At the beginning we will consider the skin empty and the inner membrane containing only copies of the element a. The intended computation sends out of the system, in several steps, as many copies of aas introduced at the beginning in the membrane e. Figure 3 shows the computation tree of the P system when two copies of aare introduced in the membrane e. The system is non-deterministic. In the first step the rules 1and 3 can be triggered. This produces three different branches. The three branches end and the final configuration is different in all the cases, but always in the end of the computation the P system sends out as many copies of aas introduced in the inner membrane. As a computational device, we can think that the P system works, as every branch returns the correct number of a. This leads us to define a more general definition of confluence than the classical one4: the confluence with respect to a property. Definition 4.2 A P system is called confluent with respect to a property if all the branches of the computation tree end, and all the final configurations satisfy the property. With this definition, we can say that the P system in the example (with a2in the membrane eat the beginning) is confluent with respect to the property: The number of objects ain the environment in the final configuration is two. Note that the three branches in the example end with a correct configuration, but the number of steps is not the same in all them. This suggests us a way to compute how far from each other two configurations are. Before giving the definition of the weak metric on configurations, we need some previous definitions. Definition 4.3 Given a P system, an L-configuration of the P system is a multiset of pairs (s, m)where sis an element of the alphabet and mis a membrane of the P system. We will say that an L-configuration is total when for all symbol sof the alphabet and for all membrane m, the multiplicity of sin mis the same as the multiplicity of the pair 4See, for example, [4]. 145 s e a2 s ea2 s ea2 s e bz a s e z c a s e b2z2 s e z2c2 s e zdz a s e z z a2 s e z2d2z2 s e z2z2a2 ? ?? ? ? ? ? ? ? ? 6 5 2,4 1,3 6,6 5,5 4,4 3,3 2,2 1,1 Figure 3: The computation tree (s, m)in the configuration. Any proper submultiset of a total L-configuration is a partial L-configuration. The distance between two nodes of the dependency graph is defined in the natural way: Definition 4.4 Given a directed graph (as a dependency graph), a path from two vertices aand bis a finite sequence v0, v1, . . . , vnof vertices such that v0=a,vn=band for all i∈ {0, . . . , n −1},(vi, vi+1)is an edge of the graph. The sequence of vertices with an unique vertex is also considered a path. The length of a path is the number of vertices of the sequence minus one. Given a vertex v, we define the set of initial vertices of v,Ivas the set of all the vertex aof the graph such that there exists a path from ato v. Given a set of vertices S, we define the set of initial vertices of S,ISas the set of all the vertex aof the graph such that there exists a vertex vin Sand a path from ato v. Definition 4.5 Given a P system Πand its dependency graph GΠ, the distance between two nodes v1and v2of GΠis the length of the shortest path that connect v1and v2and infinite if there is no path from v1to v2. 146 5 Weak Metrics Based on the Dependency Graph 5.1 First Approach In non-deterministic P systems, given a configurations there (potentially) exist several configurations which can be reached. If the P system is confluentin the classical sense, from the point of view of correctness, it is not important the branch we follow, because the final result is the same, but from a computational point of view, the cost measured as the number of steps in the computation can be different, so it can be interesting to define some kind of measure of how far a configuration is from the final configuration. Next, let us consider a total L-configuration C, which represents an intermediate step of the computation, and a partial L-configuration F, which represents the property of a possible final L-configuration. How can we measure the closeness between them? One way is by using the minimum number of steps of computation between them in the natural way. Firstly, we consider an element b∈ F. The element bhas to be reachable from the elements in C, and we are interested in the shortest path, so we consider min a∈C∩Ib d(a, b), where C ∩ IFis the intersection of the L-configuration Cwith the set of initial vertices of F, in other words, is the multiset of all the elements aof Csuch that such that there exists a path from ato b. If this set is empty, the minimum is infinite. Finally, to compute the distance, we have to consider the longest of these shortest paths. Definition 5.1 Given two L-configurations Cand F, the quasi-metric from Cto Fis defined as d(C,F) = max b∈F {min a∈C∩Ib d(a, b)}. Theorem 5.1 dis a (weak) metric between L-configurations. The metric dhinduced by this quasi-metric, dh(C1,C2) = max{d(C1,C2), d(C2,C1)}, is the Hausdorff metric on the L-configurations. 6 Example In our example, in the first step of the computation three new configurations are possible (see Figure 3). They can be represented as the following multisets C1={(a, s),(a, s)}, C2={(b, e),(z, e),(a, s)}, C3={(b, e),(b, e),(z, e),(z, e)}, and the partial L-configuration which characterizes all the final configurations is F={(a, outside),(a, outside)}; 147