Exploring Computation Trees Associated with P Systems

Exploring Computation Trees Associated with P Systems Andr´es Cord´on-Franco, Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, and 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 {acordon, magutier, marper, ariscosn}@us.es Abstract. Usually, the evolution of a P system generates a computation tree too large to be efficiently handled with present–day computers; moreover, different branches in this tree may differ significantly from a computational complexity point of view, that is, for the amount of time and storage necessary to reach a result. In this paper we propose a first approach to outline a strategy for selecting a suitable branch, in some sense, of the computation tree associated with a P system. To this end, we introduce the key notion of the dependency graph of a P system. 1 Introduction The evolution of a non-deterministic computational device usually gives rise to a computation tree with several branches, potentially infinite. Moreover, even in the case of finite computation trees, the amount of information is often too big to be efficiently handled with present-day computers. This is why it is convenient to look for good strategies for exploring such computation trees. In this paper, we address one of these non-deterministic computational devices: P systems (see [2, 3] or visit [4]). Our goal is to enrich the simulation of the evolution of a P system with a new component, usually called strategy or search plan, that controls the rules to be applied in each cellular step, in order to select a branch of the computation tree with a low (if possible, minimal) cost. The ideal situation would be to have a mapping h∗ assigning to each node n of a computation tree a number h∗(n) which measures the minimum length of a path from node n to a leaf (that is, to a halting configuration). Then, the strategy would consist on selecting at each non-deterministic step of the computation a node corresponding to the least value of h∗. However, the drawback is the high computational cost of such a mapping. In a more realistic situation, we look for a computable mapping being an efficient estimation of h∗, that will be referred to as a heuristic function or evaluation function. The paper is organized as follows. In Section 2 we describe the P system variant used in this paper. Section 3 introduces the key notion of the dependency graph of a P system. Based upon this notion, in Section 4 we present a mapping h, which helps us to search for a short branch in the computation tree of a P system. We also prove that this mapping is, indeed, a heuristic function. Finally, in Section 5 we develop an illustrative example and we finish with some final remarks. 2 P Systems with a Fixed Number of Membranes Let us now briefly introduce the P system variant we shall work with in this paper. We shall only use evolution and communication rules and we shall avoid division or dissolution rules; so, the number of membranes (indeed, the whole membrane structure) remains unchanged during the evolution of the system. P systems will be represented as tuples Π=(Γ, H, µ, w1,...,w q,R), where: –Γis a finite alphabet (the working alphabet) whose elements are called objects. –His a finite set of labels for membranes. –µis a tree-like membrane structure of degree q, one-to-one labelled by the set H. –w1,...,w qare multisets over Γdescribing the multisets of objects initially placed in membranes from µ. –Ris a finite set of developmental rules of the following forms: 1. [a→v]l, where a∈Γ,v∈Γ∗(object evolution rules). Internal rule: an object acan evolve to a multiset vinside a membrane labelled by l. 2. [a]l→[] lb, where a, b ∈Γ(send-out communication rules). An object acan get out of a membrane labelled by l, possibly transformed in a new object b. 3. a[] l→[b]l, where a, b ∈Γ(send-in communication rules). An object acan get into a membrane labelled by l, possibly transformed in a new object b. Note that cooperation is not allowed, and priority or electrical charges are not considered either. Besides, let us observe that the rules of the system are associated with labels (e.g., the rule [a→v]lis associated with the label l∈H). The rules are applied according to the following principles. Object evolution rules are applied in a maximal parallel way (that is, all objects which can evolve by such rules must do it), while communication rules are used sequentially, in the sense that one membrane can be used by at most one rule of this type at one step. Concerning the interaction with the user, we shall consider that the results of the computations are collected outside the system (note that objects can leave the system during the evolution, provided that send-out rules are applied in the skin membrane). In order to be able to handle this external output of the computations in a formal way, we add a new region to the membrane structure, called environment. In this way, the information about the contents of the environment can be included in the configurations of the system. 3 Dependency Graphs Roughly speaking, transitions in P systems are performed by rules in which the occurrence of an element a0in a membrane m0produces the apparition of the element a1in a membrane m1. In a certain sense, one can consider a dependency between the pair (a0,m 0) and the pair (a1,m 1). This dependency is not based on the initial configuration but on the set of rules of the P system. More formally, the rules in the P system model presented above can be reformulated as follows: (a0,m 1)→(a1,m 2)(a2,m 2)...(an,m 2) The occurrence of the element a0in membrane m1triggers the rule and produces the apparition of the multiset a1a2...a ninto membrane m2. Obviously, if m1=m2, then we have a communication rule. In this case, n must be equal to 1 and both membranes must be adjacent (one membrane is the father of the other one). If m1is the father of m2, then we have a send-in communication rule, and if the opposite holds, then we have a send-out communication rule. On the other hand, if m1=m2, then we have an evolution rule. The pair (a0,m 1) stands for the left side of the rule and the multiset of pairs (a1,m 2)(a2,m 2)...(an,m 2) stands for the right side of the rule. Next, we define the dependency graph of a P system based on this new representation of the rules. Definition 1. The dependency graph of a P system Πis a pair GΠ=(VΠ,E Π) such that VΠis the set of all the pairs (z, m), where zis a symbol of the alphabet of Πand mis a label of a membrane (or env for the environment), and EΠis the set of all ordered pairs (arcs) of elements of VΠ,((z1,m 1),(z2,m 2)), such that (z1,m 1)is the left side of a rule and (z2,m 2)belongs to the right side of that rule. The distance between two nodes of the dependency graph is defined as usual. Definition 2. Apath of length nfrom a vertex xto a vertex yin a directed graph G=(V,E)is a finite sequence v0,v 1,...,v nof vertices such that v0=x, vn=y, and (vi,v i+1)∈Efor i=0,...,n−1. The sequence of vertices with a single vertex is also considered a path. If there is a path γfrom xto y,wesay that yis reachable from x(via γ). The distance between two vertices v1and v2, d(v1,v 2), is the length of the shortest path from v1to v2, or infinite, if v2is not reachable from v1. We illustrate the definition of dependency graph with an example. Let us consider the next toy P system, with alphabet Γ={a, b, c, d, v, w, z, yes}, membrane structure µ=[[] e]sand set of rules: Rule 1: [ a → zb ]e Rule 6: [ a ]s → []s yes Rule 2: [a]e→[] eaRule 7: [z]e→[] ea Rule 3: [b]e→[] ecRule 8: z[] e→[d]e Rule 4: [a→z2v]sRule 9: [v→w]s Rule 5: [z]s→[] szRule 10: [w]s→[] syes In order to construct the corresponding dependency graph, we have to consider the set of regions that are determined by the membrane structure of the P system. Since the elements can be sent out of the system (rules 5,6and 10), we have to consider three regions: {e, s, env}. Then, with the new representation, the rules can be rewritten as follows: Rule 1: (a, e)→(z,e)(b, e)Rule 6: (a, s)→(yes, env) Rule 2: (a, e)→(a, s)Rule 7: (z,e)→(a, s) Rule 3: (b, e)→(c, s)Rule 8: (z,s)→(d, e) Rule 4: (a, s)→(z,s)2(v, s)Rule 9: (v, s)→(w, s) Rule 5: (z,s)→(z, env)Rule 10: (w, s)→(yes, env) Therefore, the dependency graph of Π,GΠ=(VΠ,E Π), is defined by the following sets: VΠ= ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ (a, e),(b, e),(c, e),(d, e),(v,e),(w, e),(z,e),(yes, e), (a, s),(b, s),(c, s),(d, s),(v,s),(w, s),(z,s),(yes, s), (a, env),(b, env),(c, env),(d, env), (v, env),(w, env),(z, env),(yes, env) ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ , EΠ= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ((a, e),(z,e)),((a, e),(b, e)),((a, e),(a, s)), ((a, s),(z,s)),((a, s),(v, s)),((a, s),(yes, env)), ((b, e),(c, s)), ((z,e),(a, s)),((z,s),(z, env)),((z,s),(d, e)), ((v,s),(w, s)), ((w, s),(yes, env)) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ . (d,e) (c,s) (z,env) (z,s) (b,e) (v,s) (a,s) (a,e) (w,s) (yes,env) (z,e)     - - - ? 6 6 6 Q Q Q Q Q Qk Fig. 1. The dependency graph The set VΠof vertices has 24 elements, but 13 of them are isolated: only 11 vertices occur in some arc. Figure 1 shows the connected vertices of the graph. Note that the dependency graph only depends on the membrane structure and on the set of rules of the P system, and not on the elements of the membranes at the initial configuration. This example will be further studied in Section 5. 4 Heuristics The simulation of a P system with current computers is a quite complex task. P systems are intrinsically non-deterministic computational devices and therefore their computation trees are difficult to store and handle with one-processor (or a bounded number of processors) computers. A possible way to overtake this shortcoming is to follow only one branch of the associated computation tree in each run of the simulator. Choosing which branch must be explored is not an easy decision, as different branches may differ significantly from a computational complexity point of view. In order to select the best branch of the computation tree, the ideal situation would be to have a mapping h∗assigning to every node a number which indicates the minimum length of a path from this node to a leaf. Unfortunately, such a mapping usually has a high computational cost. In a more realistic situation, we look for a mapping hbeing an efficient estimation of h∗, in the following sense: –hassigns to each node nof a computation tree a number h(n) verifying h(n)≤h∗(n); and –the value h(n) can be calculated with a low computational cost. Then, h(n) is a real-valued function over the nodes that, in some cases, provides a lower bound of the number of cellular steps needed to reach a halting configuration from node n. Such a mapping hwill be referred to as a heuristic function or evaluation function. The aim of this section is to present a heuristic function hbased on the notion of dependency graph of a P system. In general, given a configuration of a non-deterministic P system, there exist several essentially different halting configurations which can be reached. However, in this first approach to the use of heuristics, we shall only consider a family of P system that behaves well in the following sense. Despite of the nondeterminism, every computation of a P system in the family halts (i.e., there are no infinite branches in the computation tree) and, starting from a given initial configuration, all computations send out to the environment the same answer, just at the last step. Consequently, when simulating such a P system, no matter which branch of the associated computation tree we follow, we will get the same answer, but the computational cost measured as the number of steps in the computation may vary widely. Hence, it is interesting to define a heuristic function measuring, in some sense, how far a given configuration is from a halting configuration in the computation tree. In order to define such a heuristic mapping, we introduce the concept of L-configuration of a P system. As above, we codify the information as ordered pairs (element, membrane). Definition 3. An L-configuration,LC, associated with a given configuration, C, is a multiset of pairs (z,m)such that, for every object zof the alphabet and for every membrane m, the multiplicity of zin min the configuration Cis equal to the multiplicity of the pair (z,m)in LC. Next we define a mapping hwhich helps to select a good branch in each choice point of the computation tree associated with a P system. Definition 4. Let Πbe a P system. Let LC be an L-configuration of Π, and zthe object sent out to the environment at the end of the computation. The heuristic function his defined as h(LC) = min{d(v,(z, env)) |v∈LC} where dis the distance in the dependency graph. We finish this section with a theorem which states that the mapping hverifies the required property. Theorem 1. Let h∗be a function mapping a configuration Conto the number of steps of the shortest path in the computation tree from Cto a halting configuration. For each configuration C, we have h(LC)≤h∗(C), where LC is the L-configuration associated with C. Proof. The basic idea of the proof is that the transition between two adjacent vertices in the dependency graph needs at least one evolution step of the P system. Keeping this in mind, the proof is quite natural. We will reason by reductio ad absurdum. Suppose that there exists a configuration C0such that h∗(C0)<h(LC0) and let C∗be a halting configuration such that from C0to C∗there are h∗(C0) evolution steps. Let zbe the element sent out in the last step of the computation. Since C∗is a halting configuration, (z, env) belongs to the L-configuration LC∗and h∗(C0)<h(LC0) = min{d(v,(z, env)) |v∈LC0} In particular, for all v∈LC0such that (z, env) is reachable from v,h∗(C0) is less than the length of the shortest path from vto (z, env) in the dependency graph. That is, the distance from any element of the L-configuration LC0to (z, env) is larger than the number of computation steps of the P system from C0to a halting configuration. But this is impossible since, as remarked above, the transition between two adjacent vertices in the dependency graph needs at least one computation step of the P system.  5 Example To illustrate the definition of the heuristic function h, we consider again the example described in Section 3. Figure 2 shows the computation tree associated with the evolution of this P system. In the first step of the computation two new configurations are possible. We use the function hto select one of them in order to reach a halting configuration in the minimum number of steps. s e bac s eac2 s e z2vc2 s ec2 yes s ec2 yes s e c2z2v s e dc2wz s e dc2z yes s e dcz yes s e dcw z s ec yes s e cz2v s e ba s e dc2wz s e dc2z yes s e zc2 s e zb c s e ab ? ? ? ? ? ? ? ? ? ? ? XXXXXX Xz XXXXXX Xz ? ? ?? ? 3 7 4 5,8 9 10 6 3,6 7 1,3 10 5,8 9 3,4 3,6 2 10 5,8 9 3,4 Fig. 2. The computation tree The two possible configurations to proceed with are: C1≡[[zb]ec]s, by applying rules 1and 3, C2≡[[b]ea]s, by applying rule 2. The information of these configurations can be represented by their associated L-configurations: LC1={(z,e),(b, e),(c, s)}, LC2={(b, e),(a, s)}. In this example, the halting configurations are characterized by sending the object yes to the environment; that is, a configuration is a halting one if and only if (yes, env) is an element of its associated L-configuration. In order to decide which branch we must follow in the computation tree, we compute h(LCi), for i=1,2: h(LC1) = min{d(v,(yes, env)) |v∈LC1} =d((z,e),(yes, env)) =2, h(LC2) = min{d(v,(yes, env)) |v∈LC2} =d((a, s),(yes, env)) =1. We have h(LC2)<h(LC1), so, according to the heuristic h, we should follow the computation from the configuration C2to reach a halting configuration. Figure 2 shows the whole computation tree and it can be checked that, in the next evolution step, a halting configuration is reached from C2and this is the shortest path from the initial configuration to a halting one. If we consider the subtree dominated by the configuration C1≡[[zb]ec]s, that is, if we consider C1as initial configuration, the function hcan help to find the shortest computation. As Figure 2 shows, starting from C1two new configurations are possible: C11 ≡[[z]ec2]s, by applying rule 3, C12 ≡[[b]eac]s, by applying rule 7. Their associated L-configurations are: LC11 ={(z,e),(c, s),(c, s))}, LC12 ={(b, e),(a, s),(c, s)}. In order to decide which branch we must follow in the computation tree, we compute h(LC1i) for i=1,2: h(LC11) = min{d(v,(yes, env)) |v∈LC11} =d((z,e),(yes, env)) =2, h(LC12) = min{d(v,(yes, env)) |v∈LC12} =d((a, s),(yes, env)) =1. So, we should follow C12 to obtain the shortest computation. In fact, starting from C12, a halting configuration is reached in the next step. 6 Conclusions and Further Research In this paper we have presented a first approach towards an efficient strategy for searching in the computation tree associated with the evolution of a P system. Our aim is to select a branch with a low computational cost, measured as the number of steps needed to reach a halting configuration. We propose a heuristic function hbeing an estimation of this computational cost, based on the notion of dependency graph of a P system. We have illustrated the use of this heuristic function with an example belonging to a special family of P systems that, in a specific sense, “behaves well”. Nonetheless, the search plan proposed here can be generalized, in a rather natural way, to other (less restrictive) variants of P system. In particular, extending the notion of dependency graph to P systems where the number of membranes can vary during the evolution (e.g., P systems with active membranes) seems to be a very promising question. Another interesting topic is to study the transformation of configurations as a pre-computation phase, when the system itself is built. In this framework several important topics appear, such as the edit-distance between configurations, normal forms, reachability, etc. Acknowledgement The support for this research through the project TIC2002-04220-C03-01 of the Ministerio de Ciencia y Tecnolog´ıa of Spain, cofinanced by FEDER funds, is gratefully acknowledged. References 1. A. Cord´on-Franco, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, Weak metrics on configurations of a P system. In Gh. P˘aun, A. Riscos-N´u˜nez, A. Romero-Jim´enez, and F. Sancho-Caparrini, (eds.), Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, University of Sevilla, 2004, 139–151. 2. Gh. P˘aun, Computing with membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 3. Gh. P˘aun, Membrane Computing. An introduction. Springer-Verlag, 2002. 4. http://psystems.disco.unimib.it/