An Approach to the Degree of Parallelism in P Systems

An Approach to the Degree of Parallelism in P Systems 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 {magutier,marper,ariscosn}@us.es Summary. In the literature, several designs of P systems were used for performing the same task. The use of different techniques or even different P system models makes it very difficult to compare these designs. In this paper, we introduce a new criterion for such a comparison: the degree of parallelism of a P system. To this aim, we define the labeled dependency graph associated with a P system, and we use this new concept for proving some results concerning the maximum number of applications of rules in a single step along the computation of a P system. 1 Introduction In the last years, an extensive literature on Membrane Computing has been produced, studying multiple approaches. We can consider the following rough classification: •Generative task: from a given initial configuration several distinct computations may be developed (in a non-deterministic manner) and they may produce different outputs. We can consider that the system generates the set of all the outputs of all the computations (and this set can be interpreted as the language generated by the system). •Computing task: if we can encode any natural number, n, in the initial configuration of a given P system and we consider the cardinality of the output multiset as the result of the computation, then we can interpret that the system has “computed” a numerical function over n. •Decidability task: another option is to consider that the output alphabet consists of two special objects, yes and no, in such a way that these are the only objects that determine the answer, irrespectively of the occurrence of other possible objects from the working alphabet in the output membrane. 88 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez Several designs of P systems might be used for performing the same task. The use of different techniques or even different P systems models makes it very difficult to compare these designs. Furthermore, the intrinsic non-determinism of P systems usually yields computational trees of a very large size, which makes the comparison task especially hard. A first attempt1to give an appropriate description of the complexity of the evolution of a P system was given by G. Ciobanu, Gh. P˘aun, and Gh. S¸tef˘anescu in [1]. In this paper, a new tool for the descriptive complexity of P systems called Sevilla carpet was presented. Roughly speaking, a Sevilla carpet is a table with time and an explicit enumeration of the rules of the P system on its axes. For each pair step–rule, a piece of information is given. Additional parameters for studying Sevilla carpets were introduced in [6] and a multidimensional generalization of Sevilla carpets was presented in [8]. Sevilla carpets and their associated parameters provide very useful information to describe the evolution of a P system, but only for one computation. If we consider two deterministic P systems which perform the same task, then the use of Sevilla carpets, together with the associated parameters, gives enough information to establish a comparison. But this is not the general case. In general we have non-deterministic P systems which may have infinite computations. We wonder how to compare two different P system designs which perform the same task, possibly implemented in different models. One of the basis of the power of P systems as computational devices is the maximal parallelism in the use of rules. This maximal parallelism is twofold: all membranes process data in parallel and inside each membrane as many objects as possible evolve. Complementing this feature with the ability of producing new membranes along the computation is the basis of the design of families of P systems which solve NP-complete problems in polynomial time (see, e.g., [5, 7, 12, 13, 16, 18, 19, 17], and also [20] and references therein) In this paper we focus our attention on the parallelism in order to have a tool to compare the design of P systems which perform the same task. Intuitively, a bad design of a P system consists of a P system which does not exploit its parallelism, that is, it works as a sequential machine: in each step only one object evolve in one membrane whereas the remaining objects do not evolve. On the other hand, a good design consists on a P system in which a huge amount of objects are evolving simultaneously in all membranes. If both P systems perform the same task, it is obvious that the second one is a better design that the first one. In the general case the comparison is not so easy and, in most cases, it would be useful to have a numerical function which captures the idea of how good is the use of the parallelism in a P system. The quest for such a function is hard, since P systems are intrinsically non-deterministic and two computations can be quite 1Recently two new parameters have been introduced in [2] in order to describe the complexity of P systems. They are related to the graph of reachable configurations of a given P system, namely the outdegree as a measure of the degree of non determinism, and the indegree as a measure of the degree of confluence. An Approach to the Degree of Parallelism in P Systems 89 different even in confluent P systems. In this paper we propose a parameter based on the (potentially) maximum number of applications of rules in a step of any computation. This number depends on the initial configuration, the set of rules and the semantics of the model. The paper is organized as follows. First, some preliminaries are given, recalling some concepts related to multisets, introducing the new concept of injective mapping with respect to a multiset and fixing some ideas about graphs and P systems. In Section 3 we give an estimation of the use of parallelism in a P system from a given configuration in one step. In the following section we extend our study to the general case and provide a new parameter, β(Π, C), which is an upper bound on the maximum number of simultaneous applications of rules in one step in any computation of Πwith the initial configuration C. Finally, some conclusions and lines for future work are given. 2 Preliminaries In this section we recall some concepts which will be used along the paper. First of all, we remind some basic ideas on multisets and introduce the new concept of injective mapping with respect to a multiset. Next we present the P system model we will work with in this paper and adopt some conventions for notation. 2.1 Multisets Multisets are the basic data structure in P systems. Its use is inspired in the chemical compounds of the vesicles of living cells. First of all, we recall the definition2. Let Dbe a set. A multiset over Dis a pair hD, fiwhere f:D→Nis a mapping. If A=hA, fiis a multiset, its support,supp(A) is defined as supp(A) = {x∈A|f(x)>0}and its cardinality, denoted by #A, is defined as #A=X a∈A f(a). Suppose that A=hA, fiand B=hA, giare two multisets over the set A. •(Sub-multisets) If for all a∈Awe have f(a)≤g(a), then we say that hA, fi is a sub-multiset of hA, gi •(Union of multisets) The union of Aand B, denoted by A∪B is the multiset hA, hi, where h(a) = f(a) + g(a) for all a∈A. Next we introduce a new definition that will be useful in the following sections. It is a natural generalization of the definition of injective mapping between sets. Definition 1. Let D1and D2be sets, hD2, fia multiset over D2and g:D1→D2 a mapping. We will say that gis injective with respect to the multiset hD2, fiif ∀y∈D2¡#{x∈D1|g(x) = y} ≤ f(y)¢. 2A detailed presentation of multisets can be found, for example, in [21]. 90 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez b a c a b c x x y x y y y Fig. 1. Mappings on multisets This definition can be illustrated with the following example. Example 1. Let us consider the sets D1={a, b, c}and D2={x, y}and the multisets3over D2hD2, f1i={x2, y}and hD2, f2i={x, y3}. Then the mapping g:D1→D2with g(a) = x,g(b) = xand g(c) = yis injective w.r.t. hD2, f1iand is not injective w.r.t. hD2, f2i(see Figure 1.) Note that this definition expands the usual definition of injective mappings over sets. 2.2 Graphs In this paper we will use directed graphs as a structure for organizing information. We briefly fix some concepts which will be used later. Adirected graph Gis a pair G= (V, E) where Vis a set and E⊆V×V. The elements of Vare called nodes, and the elements of Eare called arcs. Given a directed graph G, a subgraph G0from Gis a pair G0= (V0, E0) such that V0⊆V, E0⊆E∩(V0×V0). Given a set of graphs {Gi}i∈Iwith Gi= (Vi, Ei), its union is the graph [ i∈I Gi=Ã[ i∈I Vi,[ i∈I Ei!. We will consider the paths in a directed graph as subgraphs following the next definition. Definition 2. Apath of length nfrom a vertex xto a vertex yin a directed graph G= (V, E)is a subgraph G0= (V0, E0)such that V0={v0, v1, . . . , vn}with v0=x, vn=y, and E0={(vi, vi+1)|i= 0, . . . , n −1}. If x=y, then we will say that the path is a cycle. The subgraph with a single vertex and no arcs is also considered a path. Finally, we define the subgraph generated by a source Aand a sink B. Definition 3. Given a directed graph G= (V, E)and two sets of vertices A, B ⊆V we define the subgraph generated by the source Aand the sink Bas the subgraph of Gobtained as the union of all the paths in Gfrom xto ywith x∈Aand y∈B. 3With the usual notation {xf(x)|x∈D}for the multiset hD, fi. An Approach to the Degree of Parallelism in P Systems 91 2.3 P systems We assume that the reader is familiar with the standard P system models. In this section we briefly define a simple model that we will be using along this paper. Recall that, basically, a P system consists of a cell-like membrane structure together with associated multisets of objects and a set of rules expressing how these objects can evolve (see [15]). The membrane structure of a P system is used to enclose computing cells in order to make them independent computing units. The objects can pass through membranes and, depending on the variant of the model we are dealing with, the membranes can be dissolved, divided, or created. Nevertheless, in this paper we shall work in a simplified model without division, dissolution nor creation of membranes. We do not use cooperation nor priority among rules either. Aconfiguration is the instantaneous description of the current membrane structure and the multisets of objects associated with the membranes. In each time unit (a step), a transformation of a configuration of the system takes place by applying the rules of each region in a non-deterministic maximally parallel manner. In this way, transitions between two configurations of the system are obtained. A sequence of such transitions (finite or infinite) is called a computation. More formally, a P system is a tuple Π= (Γ, H, µ, w1, . . . , wq, 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. Membranes are labeled bijectively by elements from H. •w1, . . . , wqare multisets over Γdescribing the multisets of objects initially placed in the membranes of µ. •Ris a finite set of developmental rules. These rules can be of two types: evolution rules where the object that triggers the rule do not cross any membrane and communication rules where the object which triggers the rule do cross a membrane. These communication rules can be of type send-in or send-out as described below: 1. [a→v]l, where a∈Γ,v∈Γ∗,l∈H(evolution rules). An object aevolves to a multiset vinside a membrane labeled by l. 2. [a]l→b[ ]l, where a, b ∈Γ,l∈H(send-out communication rules). An object agets out of a membrane labeled by l, possibly transformed in a new object, b. 3. a[ ]l→[b]l, where a, b ∈Γ,l∈H(send-in communication rules). An object agets into a membrane labeled by l, possibly transformed in a new object, b. 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). Rules are applied according to the following principles: •The evolution rules are applied as usual in the framework of Membrane Computing, that is, in a maximally parallel way. In one step, each object in a 92 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez membrane can only be used for one rule (non-deterministically chosen in case there are several possibilities), but any object which can evolve by a rule of any form must evolve (with the restrictions indicated below for the communication case). •All elements which are not specified in any of the operations to apply remain unchanged to the next step. In the literature we can find two different semantics concerning rules which cross membranes. •Parallel communication case: Communication rules follow the same principle of maximality as evolution rules, i.e., several objects (as many as possible, via the application of their respective rules) can cross simultaneously the same membrane. •Sequential communication case: At one step, a membrane can only be the subject of only one communication rule. This is the case for P systems with active membranes, which has been profusely used for designing solutions to NP problems (see [20] and references therein). 2.4 Notation We will adopt the notation for rules and configurations given in [4], that we briefly recall in what follows. Roughly speaking, transitions in P systems are performed by rules in which the occurrence of an element a0in a membrane m0sends the element a1into a membrane m1. In a certain sense, one can consider a dependency between the pair (a0, m0) and the pair (a1, m1). The rules in the P system model presented above fit into the following schema (with some constraints): (a0, m1)→(a1, m2)(a2, m2). . . (an, m2), which can be interpreted as follows: The occurrence of the element a0in the membrane m1triggers the rule and sends the multiset a1a2. . . aninto the membrane m2. Obviously, if m16=m2then we have a communication rule. In this case, n must be equal to 1 and both membranes must be adjacent (one membrane is contained inside the other one). If m1is contained inside m2, then we have a send-out communication rule, and if the opposite holds, then we have a send-in communication rule. On the other hand, if m1=m2, then we have an evolution rule. As usual, the pair (a0, m1) is called the left hand side (LHS) of the rule and the multiset of pairs (a1, m2)(a2, m2). . . (an, m2) is the right hand side (RHS) of the rule. In the next sections, we shall consider that a configuration is represented as a multiset of pairs (z, m) such that, for every object zof the alphabet and for every membrane m, the multiplicity of zin mis the multiplicity of the pair (z, m) in the multiset. This notion is called an L-configuration of a P system in [4]. An Approach to the Degree of Parallelism in P Systems 93 3 Applications of Rules in a Single Step A first step in order to have an estimation of the use of parallelism of a P system is to consider a single configuration. In the general case, there are several configurations C1,. . . ,Cnreachable in one step of a computation from a given configuration C. The number of applications of rules to reach each configuration Cican vary as the next example shows. Example 2. Consider the P system with the alphabet Γ={a, b}, the membrane structure [ [ ]e]s, the initial multisets we={a},ws={a}, and the set of rules: R1 : [ a]e→b[ ]e,R2 :a[ ]e→[b]e,R3 : [ a→b]s, and the sequential communication semantics. By using rules R1 and R3 we reach the configuration C1= [[ ]eb2]sfrom the initial one [[ a]ea]s. On the other hand, by using R2 we can also reach the configuration C2≡[[ ab ]e]s. Notice that C1has been obtained by two applications of rules and C2by only one application. Next let us try to determine the maximum number of applications of rules from a given configuration in one step, that will be denoted by β1(Π, C). In our study, the key is to consider the multiset of elements which can trigger a rule. Due to the massive parallelism, if an element can trigger an evolution rule, then we are certain that this element will be consumed by the application of one of the rules triggered by it. If an element only triggers communication rules, then in order to know if the object will be consumed we need to know if only one or several objects can cross a membrane, how many rules can be triggered by that object, and whether there exist or not more objects that can cross the same membrane. We will start by defining two distinguished sub-multisets, CEand CC, of a given configuration C. Let Πbe a P system and Ca configuration of Π. We define: CE={(a, m)∈ C | (a, m) is the LHS of an evolution rule}, CC={(a, m)∈ C | (a, m) is the LHS of a communication rule and it is not the LHS of any evolution rule}. 3.1 The sequential communication case Let us first consider the sequential semantics. In this context we define a crossing mapping. The intuition behind this definition is the following: we intend to map membrane labels onto objects that can cross them in the next step by the application of a communication rule. In general, it may not be possible to find such a mapping defined over all labels, so we have to consider a subset S⊆H. Besides, in order to avoid that two objects cross the same membrane, we demand that the mapping is injective in the sense of Definition 1. Definition 4. Let Πbe a P system, Hits set of labels, and Ca configuration of Π. A crossing mapping on Cis a mapping f:S→supp(CC)with S⊆H, injective w.r.t. CC, such that for every h∈Sthere exists a communication rule associated with membrane hand having f(h)on its LHS. 94 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez Notice that for a given configuration there may exist several crossing mappings, that correspond to different non-deterministic choices of communication rules to be applied over the membranes with labels in S. Finally, we give an expression of the maximum number of applications of rules in a transition step from the current configuration. Theorem 1. Let Πbe a P system and Ca configuration. Let us consider the sequential communication semantics.The maximum number β1(Π, C)of applications of rules for reaching a configuration from Cis β1(Π, C) = #CE+ max{#S| ∃ a crossing mapping f:S→supp(CC)}. Proof. Let Πbe a P system, Ca configuration and let f∗:S∗→supp(CC) be a crossing mapping such that #S∗= max{#S| ∃ a crossing mapping f:S→ supp(CC)}. Then, for every label h∈S∗there exists a communication rule that crosses membrane hwith f∗(h) on its LHS. By the definition of crossing mapping, there exists one transition step starting from Cin which all objects f∗(h) trigger their corresponding communication rules crossing the membrane labeled by h, and this causes #S∗application of rules. Let us consider now the set CE. By definition, and due to the maximal parallelism, all the objects in CEtrigger an evolution rule in any transition step starting from C. In particular, there exists a transition step where the number of application of rules is exactly #CE+ #S∗. In other words, the maximum number of applications of rules in a transition step starting from C,β1(Π, C), is at least #CE+ max{#S| ∃ a crossing mapping f:S→supp(CC)}. Next, we will prove that the maximum number of applications of rules β1(Π, C) is not greater than #CE+ max{#S| ∃ a crossing mapping f:S→supp(CC)}. Let C1be a configuration obtained from Cin one transition step and let TE (TC, resp.) be the multiset of elements of the configuration Cwhich have triggered evolution (communication, resp.) rules in order to reach C1. Obviously, the number of applications of rules in the transition step C ⇒ C1is #TC+ #TE. Now, let us split the multiset TCinto two multisets: Te C, the submultiset from TCcontaining the elements which are LHS of some evolution rule, and Tne C, the submultiset from TCcontaining the elements which are not LHS of any evolution rule. We have that #TC= #Te C+ #Tne Cand •#TE+ #Te C= #CE, since TE∪Te C=CE. •#Tne C≤max{#S| ∃ a crossing mapping f:S→supp(CC)}, since we can consider the natural crossing mapping f∗:ST→supp(CC) where STis the set of labels of membranes crossed by the objects in Tne C. Therefore, the number of applications of rules in the transition step from Cto C1 is less than or equal to #CE+max{#S| ∃ a crossing mapping f:S→supp(CC)} and this concludes the proof. ut Due to the high computational cost of computing β1(Π, C), sometimes we would rather look for an upper bound easier to compute. The next corollary gives such an upper bound for β1(Π, C). The proof is immediate. An Approach to the Degree of Parallelism in P Systems 95 Corollary 1. Let Πbe a P system working with a sequential communication semantics. Let Cbe a configuration, and Hthe set of labels of Π. Then β1(Π, C)≤#CE+ #H. We illustrate the theorem with the following example. Example 3. Let us consider a P system with set of labels H={0,1,2,3}and the following set of rules: Rule 1: [a]1→b[ ]1,Rule 5: z[ ]1→[x]1,Rule 8: [a→b]1, Rule 2: [a]2→b[ ]2,Rule 6: z[ ]2→[x]2,Rule 9: [a→b]2, Rule 3: [a]3→b[ ]3,Rule 7: z[ ]3→[x]3,Rule 10: [a→b]3, Rule 4: [x]1→b[ ]1. Consider now a configuration C= [ [ ax3]1[a2z]2[az ]3z3]0. Then, CE={(a, 1),(a, 2),(a, 2),(a, 3)}, CC={(x, 1),(x, 1),(x, 1),(z, 0),(z, 0),(z, 0)}. Therefore, we have #CE= 4 and #H= 4. From the previous corollary we deduce that β1(Π, C)≤8. Actually, a more detailed study of the example shows that max{#S| ∃ a crossing mapping f:S→ CC}= 3 (e.g., by taking S={1,2,3}and f(1) = (x, 1), f(2) = (a, 2), f(3) = (z, 0)). Thus, from Theorem 1 we obtain the maximum number of applications of rules in a transition step from the current configuration: β1(Π, C) = 7. 3.2 The parallel communication case In order to compute the number of rule applications, in this case we do not distinguish between evolution and communication rules. Theorem 2. Let Πbe a P system using a parallel communication semantics, and let Cbe a configuration of Π. Then the maximum number β1(Π, C)of applications of rules in one transition step starting from Cis β1(Π, C) = #CE+ #CC. Proof. In this case the number of applications of rules is constant regardless of the non-determinism of the P system. Indeed, because of the maximal parallel condition applied both over evolution and communication rules, no “usable” object will remain unused. Therefore, the number of applications of rules for any possible transition step starting from Ccoincides with the number of objects in the configuration that can trigger at least one rule. ut The following example illustrates this result. Example 4. Let us consider again the P system from Example 3 and the same configuration, but now considering the parallel communication semantics. In this case, the sets CEand CCdo not change, because they are independent of the semantics of the system. Therefore, β1(Π, C) = #CE+ #CC= 10. 102 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez 5 Conclusions and Further Work The comparison of two P systems which perform the same task is extremely hard. These computational devices are too complex to be evaluated only with usual parameters time and space. Sevilla Carpets and its associated parameters are useful tools for the comparison of two computations and therefore, useful for deterministic P systems, but not in the general case. In this paper we make a first step in this direction. We introduce the concept of injective mapping w.r.t. a multiset, and we extend the definition of dependency graph to labeled dependency graph by adding more information. The usefulness of this new tool should be further investigated in the future. We have proved several results concerning the estimation of the use of parallelism in P systems. We consider three main open directions for developing the ideas presented in this paper. First of all, a very natural improvement is to search for an estimation of the average number of applications of rules in each step of the computation of a P system, instead of knowing only the maximum. Secondly, the P system model studied in this paper is quite simple, only allowing pure evolution or communication rules. It is interesting to study the effect on the bounds of parallelism of other types of rules, e.g., symport/antiport, dissolution, etc. Finally, another open line is related to calculating estimations for the parallelism on families of P systems. This is motivated by the fact that in the literature solutions to decision problems are usually carried out via uniform or semi-uniform families of P systems, not by using only a single P system. It is thus very interesting to extend the results presented here to families of P systems, in order to be able to compare different solutions to the same problem. Acknowledgement Work supported by project TIN2005-09345-C04-01 of Ministerio de Educaci´on y Ciencia of Spain, cofinanced by FEDER funds. References 1. G. Ciobanu, Gh. P˘aun, Gh. S¸tef˘anescu: Sevilla carpets associated with P systems. In Proceedings of the Brainstorming Week on Membrane Computing (M. Cavaliere, C. Mart´ın-Vide, Gh. P˘aun, eds.), Tarragona, Spain, 2003, Report RGML 26/03, 135–140. 2. G. Ciobanu, Gh. P˘aun, M.J. P´erez-Jim´enez: On the branching complexity of P systems. Fundamenta Informaticae, 2006, in press. An Approach to the Degree of Parallelism in P Systems 103 3. 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 Proceedings of the Second Brainstorming Week on Membrane Computing (Gh. P˘aun, A. Riscos-N´u˜nez, A. RomeroJim´enez, F. Sancho-Caparrini, eds.), Report RGNC 01/04, University of Seville, 2004, 139–151. 4. A. Cord´on-Franco, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Exploring computation trees associated with P systems. In Membrane Computing, LNCS 3365, Springer, 2005, 278–286. 5. A. Cord´on-Franco, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, F. Sancho-Caparrini: Cellular solutions of some numerical NP-complete problems: A Prolog implementation. In Molecular Computational Models: Unconventional Approaches (M. Gheorghe, ed.), Idea Group, Inc., London, 2005. 6. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: On descriptive complexity of P systems. In Membrane Computing, LNCS 3365, Springer, 2005, 320–330. 7. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: A fast P system for finding a balanced 2-partition. Soft Computing, 9, 9 (2005), 673–678. 8. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Multidimensional descriptional complexity of P systems. In Proceedings of the 7th International Workshop on Descriptional Complexity of Formal Systems (C. Mereghetti, B. Palano, G. Pighizzini, D. Wotschke, eds.), Como, Italy, 2005, 134–145. 9. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, F. Romero-Campero: On the power of dissolution in P systems with active membranes. In Membrane Computing, LNCS 3850, Springer, 2005, 373–394. 10. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, F. Romero-Campero: P systems with active membranes, without polarizations and with dissolution: A characterization of P. In Unconventional Computation, LNCS 3699, Springer, 2005, 105–116. 11. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, F. Romero-Campero: Computational efficiency of dissolution rules in membrane systems. International Journal of Computer Mathematics, 2006, in press. 12. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, F.J. Romero-Campero: Solving SAT with membrane creation. In Computability in Europe 2005, CiE 2005: New Computational Paradigms (S. Barry Cooper, B. Lowe, L. Torenvliet, eds.), Report ILLC X-2005-01, University of Amsterdam, 82–91. 13. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, F.J. Romero-Campero: A linear solution of Subset Sum problem by using membrane creation. In Mechanisms, Symbols and Models Underlying Using Cognition, First International Work-Conference on the Interplay between Natural and Artificial Computation, IWINAC 2005 (J. Mira, J.R. Alvarez, eds.), LNCS 3561, Springer, 2005, 258–267. 14. B. Mehdi, G. Chartrand: Introduction to the Theory of Graphs. Allyn and Bacon, Inc. Boston, 1971. 15. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002. 16. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Solving the Subset-Sum problem by active membranes. New Generation Computing, 23, 4 (2005), 367–384. 17. M.J. P´erez-Jim´enez, F.J. Romero-Campero: Solving the Bin Packing problem by recognizer P systems with active membranes. In Proceedings of the Second Brainstorming Week on Membrane Computing (Gh. P˘aun, A. Riscos-N´u˜nez, A. RomeroJim´enez, F. Sancho-Caparrini, eds.), Report RGNC 01/04, University of Seville, 2004, 414–430. 104 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez 18. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini: A polynomial complexity class in P systems using membrane division. In Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, DCFS 2003 (E. Csuhaj-Varj´u, C. Kintala, D. Wotschke, Gy. Vaszyl, eds.), Budapest, 2003, 284–294. 19. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini: Solving VALIDITY problem by active membranes with input. In Proceedings of the Brainstorming Week on Membrane Computing (M. Cavaliere, C. Mart´ın-Vide, Gh. P˘aun, eds.), Tarragona, Spain, 2003, Report RGML 26/03, 279–290. 20. A. Riscos-N´u˜nez: Cellular Programming: Efficient Resolution of Numerical NPcomplete Problems. Ph.D. Thesis, University of Seville, 2004. 21. A. Syropoulos: Mathematics of multisets. In Multisets Processing, LNCS 2235, Springer, 2001, 347–358.