Editing Configurations of P Systems

Editing Configurations of P Systems Erzs´ebet Csuhaj-Varj´u1, Antonio Di Nola2, Gheorghe P˘aun3,4, Mario J. P´erez–Jim´enez4, Gy¨orgy Vaszil1 1Computer and Automation Institute Hungarian Academy of Sciences Kende utca 13–17, H-1111 Budapest, Hungary E-mail: {csuhaj, vaszil}@sztaki.hu 2Department of Mathematics and Computer Science University of Salerno 84081 Baronissi, Salerno, Italy E-mail: [email protected] 3Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania E-mail: [email protected] 4Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {gpaun, marper}@us.es Summary. This paper proposes and preliminarily investigates the possibility of transforming a configuration (membrane structure and multisets of symbol-objects present in the compartments of this membrane structure) of a P system into another configuration, by means of a given set of rules acting both on the membranes and on the multisets of objects. Although such a transformation can be obtained during a computation of a P system, we consider it as a goal per se, 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 (with respect to a given set of editing rules; actually, this is a weak metric, because it is not necessarily symmetric), normal forms, reachability, existence of single configurations from which a given family of configurations can be constructed, etc. We investigate here only a few of these questions; the paper is mainly devoted to formulating problems in the new framework, calling attention to the possible extensions and usefulness of the present approach. 1 Introduction Membrane computing aims to abstract computing models from the cell structure and functioning, [14], [15]. With such a goal, the main research topics of the domain concern the computing power (comparing the power of the models obtained with 132 E. Csuhaj–Varj´u et al. inspiration from the cell biology with the power of Turing machines and of their restrictions) and the computing efficiency (solving computationally hard problems in a feasible time, by making use of a time-space trade-off which is made possible by various ways of producing an exponential working space in a linear time). The investigations were rather successful from these points of view – see details in [15] and in the web page from http://psystems.disco.unimib.it. Roughly speaking, a cell-like P system consists of a membrane structure (a hierarchical arrangement of membranes), in the compartments of which one places multisets of symbol-objects; these two elements, the membrane structure and the multisets of objects present in its compartments, form a configuration of a system at a given time. In the compartments or associated with the membranes there also are sets of rules, according to which the objects and the membrane structure evolve; otherwise stated, by using these rules we obtain transitions among configurations. A sequence of transitions is called a computation. A computation is successful only if it halts, and with a halting computation we associate a result, e.g., in the form of the vector describing the multiplicity of objects from a given compartment of the halting configuration. Here we switch the focus from computations to configurations, and we consider the problem of passing from a configuration to another configuration with the help of a given set of rules. This is similar to looking for transitions which link the two configurations, but the interest is different: we do not care about the computation itself (halting/non-halting) or about its result, while the rules we consider are mainly devoted to handling membrane structures. In some sense, our approach is directed to founding a “membrane calculus”, as attempted also in [4], in another context. Actually, there are several motivations for this kind of investigation. For instance, as already mentioned in [6] (the present paper can also be considered as a continuation of [6]), if a good (weak) metric related to the time of passing from a configuration to another configuration, with respect to the rules of a given P system, can be found, then it can be useful in a heuristic strategy to solving hard problems, based on the A∗algorithm from [13]. Then, taking into account that a P system is nothing else than an initial configuration and given sets of rules associated with membranes, constructing the initial configuration is a way to construct the system itself; otherwise stated, we can consider a specific set of rules for the pre-computing case, when the computing model itself is build, and other rules for the computation. This can have interesting consequences, for instance, in building a family of P systems associated with a decidability problem, in order to solve it (the particular systems from the family solve particular instances of the problem – see details, e.g., in [16]); in the standard computational complexity theory, this construction is done in polynomial time by a Turing machine, but the problem was formulated several times to have the P systems solving a problem constructed by another P system, so that the whole procedure is “uniformly bio-inspired”. Links with other areas (such as the theory of abstract families of languages, graph theory, or evolutionary computing) will be mentioned below. Editing Configurations of P Systems 133 However, as already said, the present paper is only a preliminary exploration of the “membrane calculus” we propose, with several results and much more research topics formulated. 2 Preliminary Definitions We start by fixing some notation and terminology. For related/further details (from membrane computing), we refer to [15] and to the papers available in the web page mentioned above. An alphabet is a finite and non-empty set of abstract symbols. For an alphabet Awe denote by A∗the set of all strings of symbols from A, including the empty string, denoted by λ; the set A∗− {λ}, of non-empty strings over A, is denoted by A+. The length of a string w∈A∗is denoted by |w|. Amultiset over an alphabet Ais a mapping from Ato N, the set of natural numbers. We represent the multisets by strings from A∗; the number of occurrences of a symbol a∈Ain a string w, denoted by |w|a, represents the multiplicity of a in the multiset represented by w(hence all strings obtained by permuting symbols in a string wrepresent the same multiset). Because of this direct correspondence between multisets over Aand strings over A, we will use the terms “multiset” and “string” interchangeably (for instance, we speak about the “length” of a multiset, with the obvious meaning that this is the total multiplicity of elements in the multiset, equal with the length of the string which represents the multiset). In one of the following sections we need the notion of a (non–deterministic) register machine. Such a device consists of a given number of registers each of which can hold an arbitrarily large non-negative integer number, and a set of labelled instructions which specify how the numbers stored in registers can change and which instruction should follow after any used instruction. Definition 1. A(non–deterministic)register machine is a construct M= (m, Lab, l0, lh, P ), where m≥1is the number of registers, Lab is a nonempty finite set (whose elements are called instruction labels),l0∈Lab is the start label, lh∈Lab − {l0}is the halt label (assigned to instruction HALT), and Pis a finite set of (labelled) instructions of one of the following three forms: •l1: (ADD(r), l2, l3), for l1, l2, l3∈Lab, 1≤r≤m, •l1: (SUB(r), l2, l3), for l1, l2, l3∈Lab, 1≤r≤m, •lh:HALT (the halt instruction). Each label from Lab labels at most one instruction of P, and l0labels one instruction of P. Astate of a register machine M= (m, Lab, l0, lh, P ) is an m-tuple (a1, . . . , am) of natural numbers. We interpret the number aias the content of register i. A snapshot or instantaneous description of a register machine M= (m, Lab, l0, lh, P ) 134 E. Csuhaj–Varj´u et al. is a pair (l, s), where l∈Lab is a label, and sis a state of M. Intuitively, the label lindicates what is the instruction which is about to be executed. A snapshot σ= (l, s) of a register machine Mis called initial if l=l0and s= (0,0, . . . , 0), and it is called halting if l=lh. Definition 2. Let M= (m, Lab, l0, lh, P )be a register machine, and σ= (l, s) with s= (a1, . . . , am)a non–halting snapshot of M. A successor of σis a snapshot σ0= (l0, s0)defined as follows: 1. If llabels an instruction (ADD(r), l2, l3), then s0= (a1, . . . , ar+1, . . . , am), and l0=l2or l0=l3. 2. If llabels an instruction (SUB(r), l2, l3), then s0= (a1, . . . , ar−1, . . . , am)and l0=l2if ar>0, and s0=sand l0=l3if ar= 0. That is, the execution of an instruction (ADD(r), l2, l3) adds 1 to register rand then go to one of the instructions with labels l2and l3, non-deterministically chosen. In the execution of an instruction (SUB(r), l2, l3), if register ris non-empty, then we subtract 1 from it and continue with the instruction labelled with l2, otherwise we continue with the instruction labelled with l3. Acomputation of a register machine M= (m, Lab, l0, lh, P ) is a (finite or infinite) sequence σ0, σ1, . . . , σkof snapshots of Msuch that: (a) σ0is the initial snapshot, (b) σi+1 is a successor snapshot of σi, for i= 0, . . . , k −1, and (c) if k∈Nthen σkis halting (in this case, we say that the computation is halting). The set N(M) of natural numbers computed by a register machine Mis the set of numbers x∈Nsuch that there exists a halting computation such that if σ= (lh,(a1, . . . , am)) is its halting snapshot, then a1=x. That is, a register machine Mcomputes a set N(M) of numbers in the following way: we start with all registers empty (hence storing the number zero) with the instruction with label l0and we proceed to apply instructions as indicated by the labels (and made possible by the contents of registers); if we reach the halt instruction, then the number stored at that time in register 1 is said to be computed by Mand hence it is introduced in N(M) (because of the non-determinism in choosing the continuation of the computation in the case of ADD instructions, N(M) can be an infinite set.) It is known (see, e.g., [12]) that in this way we can compute all sets of numbers which are Turing computable (even with machines with a small number of registers, but this detail is not of interest here). Theorem 1. If Qis a Turing computable set, then there exists a register machine M, such that N(M) = Q. Without loss of generality, we may assume that when halting, all registers are empty, with the exception of register 1, which contains the generated/computed number. Editing Configurations of P Systems 135 3 Configurations Informally speaking, a membrane structure is a 3D arrangement of vesicles, placed in a unique external membrane, called the skin membrane, without other relations taken into consideration than the inclusion (child-parent) relation. Mathematically, this corresponds to a rooted tree structure, with the root associated with the skin. As usual in membrane computing, we represent the membrane structures by strings of labelled parentheses (the labels are associated with the membranes, hence also with the nodes of the underlying tree) or, graphically, as Euler-Venn diagrams (of a particular type: no intersection is allowed and there is a unique external membrane, the skin). Figure 1 contains both the graphical and the tree representation of the following membrane structure [1[2[4[7]7[8[10 ]10]8[9]9]4]2[3[5]5[6]6]3]1. ' & $ % ' & $ % ' & $ % ¶ µ³ ´ ¶ µ³ ´ ¾ ½» ¼ ² ±¯ ° ' & $ %  Á¿ À  Á¿ À 1 23 45 6 7 8 9 10 ¡ ¡ ¡ ¡ ¡ ¡ ¡ @@ @ @@@ @ ¢ ¢ ¢ ¢ TTT T t ttt t t t t tt 1 23 4 56 79 8 10 Fig. 1. Example of a membrane structure. The number of membranes from a membrane structure µis called the degree of µ, and the number of levels of the associated tree (with the root in level 1) is called the depth of µ. Sometimes, we denote the degree with deg(µ) and the depth with dep(µ). In the case of the membrane structure from Figure 1, we have the degree equal to 10 and the depth equal to 5. In the example above, the labels are associated in a one-to-one way to membranes. In the case of membrane structures which evolve during a (pre)computation, e.g., by membrane division, we allow multiple membranes to be labelled with the same label. In such a case, the identification of membranes through labels will be no longer possible, that is why we use a double labelling for membranes, by means of pairs (i, j), where iis the “real” label, and jidentifies 136 E. Csuhaj–Varj´u et al. the copy of membrane iin the membrane structure. Thus, if we use labels from a set H, then the actual labels are from H∪(H×N), with elements of Hused alone when they label unique membranes and in couples when they label several membranes at the same time. This extended set of labels, H∪(H×N), is denoted by He. The set of labels from Hewhich actually appear in a membrane structure µis denoted by He(µ); clearly, this set is finite, as we work here only with finite membrane structures. A systematic, recursive procedure for constructing the extended labels can be based on an encoding hi1, j2iof numbers j1, j2, for instance, using Cantor pair function: we start with labels hinterpreted as (h, 0); when dividing such a membrane, we label the resulting membranes by (h, h0,1i) and (h, h0,2i); the membranes obtained by dividing the first of these membranes are labelled by (h, hh0,1i,1i) and (h, hh0,1i,2i), while the membranes obtained by dividing the second membrane are labelled by (h, hh0,2i,1i) and (h, hh0,2i,2i), and so on and so forth. Because also his a number, we can encode also h(it can be uniquely recovered from a code), but we prefer to keep it “visible”, in pair-labels as above. However, the following convention is made: we use natural numbers as labels of membranes, the skin membrane is always labelled with 1, and no other membrane has this label (hence the skin membrane does not need a double labelling). The unique directly upper membrane of each membrane i, except the case of the skin (i= 1), which has no membrane above it, is called the parent of iin µand denoted by parµ(i); conversely, the directly inner membranes placed in membrane i are called the children of iand their set is denoted by chdµ(i). Of course, the labels mentioned here are either from Hor from He, depending on the circumstances. For an elementary membrane hwe have chdµ(h) = ∅. If in each compartment (we also say region) iof a membrane structure µ we place a multiset wi, of objects from a given alphabet O, then we obtain a configuration. Note that a multiset can be empty (and then it is represented by λ). Definition 3. A configuration Cover a set of objects Oand with membranes labelled with elements of some set His a pair C= (µ, M), where µis a membrane structure with labels from Heand M:He(µ)−→ O∗is a mapping which associates multisets over Owith the regions of µ. 4 Rules for Processing Configurations Because a configuration means both a membrane structure and the associated multisets, we need rules for processing membranes and multisets of objects. The types of rules we consider here are indicated in Table 1 (in all cases, a, b, c, d are objects from an alphabet O(in rules of type (10), cplays the role of a catalyst), h, h0, h00 are labels from a set H, and u, v are multisets of objects over the alphabet O). Editing Configurations of P Systems 137 Table 1. Types of rules for configuration editing Nr. Identification Form of the rule Action 1 div [ha]h→[h0b]h0[h00 c]h00 divide 2 mer [ha]h[h0b]h0→[h00 c]h00 merge 3 endo [ha]h[h0b]h0→[h[h0d]h0c]hendocytosis 4 exo [ha[h0b]h0]h→[hc]h[h0d]d0exocytosis 5 cre a→[hb]hcreate 6 dis [ha]h→bdissolve 7 in a[h]h→[hb]hmove in 8 out [ha]h→[h]hbmove out 9 ncoo [ha→v]hnon-cooperative objects evolution 10 cat [hca →cv]hcatalytic objects evolution 11 coo [hu→v]hcooperative objects evolution Note that the first four pairs of rules are one the inverse of the other: the operation of merging two membranes is the inverse of the operation of dividing a membrane, endocytosis is the inverse of exocytosis, creating a membrane is the inverse of dissolving a membrane, moving an object inside a membrane is the inverse of moving it outside a membrane. The cooperative rules for objects evolution can be considered as their own inverse. When applying a rule [ha]h→[h0b]h0[h00 c]h00 , the contents of membrane h, objects and membranes alike, are replicated and introduced in both membranes h0 and h00, with the exception of object a, which is replaced by bin the first membrane and by cin the second membrane. Conversely, when merging the membranes h0, h00, by using the rule [h0b]h0[h00 c]h00 →[ha]h, then the contents of both membranes is accumulated (in the multiset sense) in membrane h, with the objects b, c replaced by a. Similarly, in the exocytosis/endocytosis rules, the whole contents of the moved membrane is moved together with the membrane, with the objects a, b replaced by c, d, respectively. We stress the important fact that the labels appearing in these rules are from H, not from He−H; that is, a rule associated with a membrane with label his applied to all copies of this membrane. Then, because Oand Hare finite sets, the number of rules of types (1) – (8) is finite; imposing a bound on the total multiplicity of multisets uand v(on the length of strings uand v) from rules of types (9), (10), (11), we can also ensure that the number of rules of these types is finite. Rules for membrane division, dissolution and creation, for sending objects inside or outside a membrane are currently used in P systems with active membranes; non-cooperative and catalytic rules for objects evolution are also customary. Rules for merging membranes and for moving a whole membrane (together with its con- 138 E. Csuhaj–Varj´u et al. tents) inside or outside another membrane were also occasionally used – e.g., in [3], [1], [11]. In many cases, variants of rules of these types are considered, for instance, in what concerns the labels of the involved membranes. In the case of division rules, the basic variant does not allow the change of the labels (which is allowed for division rules in Table 1 above); then, we can also allow the change of the label for in/out rules, and this extension was used, e.g., in [2]. These rules are used as standard in membrane computing, choosing the membranes and the objects in a non-deterministic manner, in such a way that the application of rules is maximally parallel. Each object and each membrane can be involved in the application of only one rule, with the mentioning that a rule of the types (9), (10), (11) is not considered as using the membrane h, but only the objects a, c and those from the multiset u, respectively. Thus, any membrane can be involved in only one rule of types (1) – (8), but the number of rules of types (9), (10), (11) which refer to a membrane hdoes not matter. In all rules of types (1) – (8) there are involved objects (the rules themselves indicate how the membrane structure is changed, under the influence of objects); these objects cannot be used at the same time also by rules of types (9), (10), (11). The use of rules of any type in a membrane structure is done in a bottom-up manner. For instance, if an elementary membrane his divided (by a rule of type (1)), or moved into another membrane (by a rule of type (3)), then first all its objects different from the object involved in the division or in the move should evolve through object evolution rules, and, when divided or moved, the membrane will replicate or move the objects obtained by the maximally parallel use of rules for object evolution. Similarly, if a membrane contains inside other membranes, then first all lower level membranes evolve and then the upper level membranes evolve, in the same step. It is important to note that we have not restricted here the use of rules of any type to elementary membranes, although this might be an interesting restriction to investigate. The previous list contains those rules which we consider as basic, both biologically motivated and mathematically elegant, but, of course, other rules can be considered. This research topic, related to the set of rules to use, is left to the reader, and this is an attractive direction of investigation. Here we have mentioned these eleven types, but we will examine in some details only some combinations of rules, as an illustration of the type of problems which we want to raise in this paper. We close this section by mentioning that by creating membranes and by endocytosis we can increase the depth of a membrane structure, while by means of the converse operations (by dissolving membranes and exocytosis) we can decrease the depth of a membrane structure. In turn, the membrane division increases the “width” of a membrane structure (hence it can increase the out-degree of the tree describing it). Rules of types (7) – (11) do not modify the membrane structure, they only move objects across membranes or handle objects inside compartments. Editing Configurations of P Systems 139 5 The Edit-Distance Among Configurations We now introduce one of the basic notions of our approach, the edit-distance among two configurations with respect to a given set of rules. Let us fix an alphabet of objects, O, and a set of labels, H. Let kbe a natural number. The family of all configurations C= (µ, M), with the membrane structure of degree at most nand depth at most d, with labels in Heand multisets of objects over O, such that each multiset wpresent in a region of µhas |w| ≤ k, is denoted by CF Gn,d(O, H, k). Because both the degree of the membrane structure and the total multiplicity of elements in the multisets are bounded, the family CFGn,d(O, H, k) is finite for all n, d, k ≥1. Then, we define CF G(O, H, k) = [ n≥1,d≥1 CF Gn,d(O, H, k). This is the family of all configurations with membranes labelled with elements of Heand multisets (each of them of total multiplicity at most k) over O. Because we allow membranes with the same label from H, this family is infinite. Let us now consider a set Rof rules, for instance, of some of the types (1) – (11). This can be a set of specific rules, which are listed explicitly, or can be a set of types of rules (that is, the set of all rules of the given types). If we use all possible rules of given types, then we write the list of rule identifications after R; for instance, R(div, in, cook) (resp., R(div, in, catk)) is the set of all rules over a given alphabet and a given set of labels, of types (div), (in), (coo) (resp., (div), (in), (cat)), with the left-hand and the right-hand member of cooperating rules of length at most k(resp., using at most kcatalysts); the alphabet and the set of labels follow from the context where the rules are used. If the size of object processing rules is not relevant (or not known), then we omit mentioning it, and we write coo instead of cook. Sometimes we also write ncook, indicating the fact that we use non-cooperating rules a→uwith |u| ≤ k. If for each rule of type (1), (3), (5), (7) we also use the reverse rule of types (2), (4), (6), (8), respectively, and for each object evolution rule (of types (9), (10), (11)) [hu→v]hwe also have the rule [hv→u]hin the set R, then the set Ris said to be reversible. If to a set Rof rules we add all rules reverse to the rules from R, then we obtain a reversible set of rules, denoted by cR and called the reversible completion of R. (Clearly, if Rcontains rules of a type (1), (3), (5), (7), then cR also contains rules of types (2), (4), (6), (8), respectively, and, if Rcontain rules of any type (ncoo), (cat), then cR may contain rules of type (coo). For instance, cR(div, in, cat) = R(div, mer, in, out, coo), and cR(cre, ncoo) = R(cre, dis, coo).) For two configurations C1, C2∈CFG(O, H, k) we write C1=⇒RC2if we can pass from C1to C2by using rules from R(this is a transition, in the customary meaning in membrane computing, with the rules used in the maximally parallel manner). We denote by =⇒∗ Rthe reflexive and transitive closure of the relation =⇒R. 146 E. Csuhaj–Varj´u et al. after introducing a multiset M(g) in a membrane g, the rules associated with g can start working, although the membranes from lower levels are not yet present. This leads to the de-synchronization of the system, which is not correct. Still, this difficulty can be overcome, by introducing the multisets only in the last moment of the construction. Because this is a rather important aspect, we give here the full details, modifying the construction from the proof of Theorem 5 for this case. Theorem 7. For every configuration C= (µ, M)∈CF Gn,d(O, H, k), there is a finite set Rof rules of types (cre)and (ncoo), over an alphabet O0⊃O, such that editR(C0, C)≤2d−1and the multisets of Care available only in the last step of the passage from C0to C. That is, there exist configurations C1, . . . , Cp∈ CF Gn,d(O, H, k)such that p≤2d−1,C0=⇒RC1=⇒RC2=⇒R. . . =⇒RCp= C, and for all i∈He(µ),M(i)∈C−(C0∪C1∪. . . ∪Cp−1). Proof. This time, for each label g∈He(µ) of a membrane in µwe consider the objects hgi,hgi0indexed with the step when such symbols are supposed to evolve. We proceed in the same way with the multisets M(i). Specifically, we take O0=O∪ {hgis,hgi0 s|g∈He(µ),2≤s≤2d−1} ∪ {hM(g)is|g∈He(µ),2≤s≤2d−1}, and the following rules in R: 1. [1a→ hM(1)i2hj1i2hj2i2...hjr1i2]1, where {j1, j2, . . . , jr1}=chdµ(1). 2. hgi2s→[ghgi0 2s+1]g, [ghgi0 2s+1 → hM(g)i2s+2hh1i2s+2hh2i2s+2 ...hhrgi2s+2]g, where {h1, h2, . . . , hrg}=chdµ(g) and g∈He(µ) labels a membrane in a level sof µwith s < d. 3. hgi2d−2→[ghgi0 2d−1]g, [ghgi0 2d−1→M(g)]g, where gis a membrane in level dof µ. 4. [ghM(g)ij→ hM(g)ij+1]g, for all g∈He(µ) and 1 ≤j≤2d−2, [ghM(g)i2d−1→M(g)]g, for all g∈He(µ). This time, each multiset M(g) is introduced in the “protected” form hM(g)is, with sindicating the step of the computation (pre-computation, if we take into account the fact that we want to construct the initial configuration of a P system); only in the last step the symbols hM(g)i2d−1are replaced with the actual multisets M(g), all of them at the same time, hence from now on the computation can start, synchronously, in all compartments of µ.2 The remark made after Theorem 5, about the possibility of bounding the multiset vfrom rules [ga→v]g, is valid also for the construction from the proof of Theorem 7, but this time we have to be careful with the synchronization, hence every symbol from a multiset should be “protected”, such that it becomes active only in the last step of the pre-computation. This can be again achieved by indexing Editing Configurations of P Systems 147 each object from Owith counters which increase with the steps of the computation. Because the length of the pre-computation depends on the out-degree of the tree of µ, we have to count in the indices of symbols hM(i)isfor each level exactly r+ 1 steps, where ris the maximal out-degree of µ, even if the out-degree of the node where we work might be smaller than r. Thus, after (r+ 1)d−1 steps, we pass to producing the symbols of multisets M(i), one by one, during k−1 steps, where kis the maximal length of a multiset. That is, we un-protect the symbols, passing from objects of type haisto aonly after (r+ 1)d−1+(k−1) steps. The technical details, although clear from the previous discussion, are cumbersome, hence we omit them. We illustrate the construction from the proof of Theorem 7 (without restrictions on the size of rules of type (ncoo)) with the case of the configuration Cwith the membrane structure as in Figure 1 and multisets M(i),1≤i≤10, which we do not specify. The set Rcontains the rules given in Table 2 (we present the rules in the order they are used in the 9 steps of the passage from C0to C). The reader is asked to follow the work of these rules, on the way from C0to C. Table 2. Rules of types (cre), (ncoo) for obtaining the configuration from Figure 1 Step Rules 1 [1a→ hM(1)i2h2i2h3i2]1 2h2i2→[2h2i0 3]2,h3i2→[3h3i0 3]3, [1hM(1)i2→ hM(1)i3]1 3 [2h2i0 3→ hM(2)i4h4i4]2, [3h3i0 3→ hM(3)i4h5i4h6i4]3, [1hM(1)i3→ hM(1)i4]1 4h4i4→[4h4i0 5]4,h5i4→[5h5i0 5]5,h6i4→[6h6i0 5]6, [1hM(1)i4→ hM(1)i5]1, [2hM(2)i4→ hM(2)i5]2, [3hM(3)i4→ hM(3)i5]3 5 [4h4i0 5→ hM(4)i6h7i6h8i6h9i6]4, [5h5i0 5→ hM(5)i6]5, [6h6i0 5→ hM(6)i6]6, [1hM(1)i5→ hM(1)i6]1, [2hM(2)i5→ hM(2)i6]2, [3hM(3)i5→ hM(3)i6]3 6h7i6→[7h7i0 7]7,h8i6→[8h8i0 7]8,h9i6→[9h9i0 7]9, [ihM(i)i6→ hM(i)i7]i, for i= 1,2,3,4,5,6 7 [7h7i0 7→ hM(7)i8]7, [8h8i0 7→ hM(8)i8h10i8]8, [9h9i0 7→ hM(9)i8]9, [ihM(i)i7→ hM(i)i8]i, for i= 1,2,3,4,5,6 8h10i8→[10h10i0 9]10,[ihM(i)i8→ hM(i)i9]i, for i= 1,2,3,4,5,6,7,8,9 9 [10h10i0 9→M(10)]10,[ihM(i)i9→M(i)]i, for i= 1,2,3,4,5,6,7,8,9 Theorem 6 has a series of interesting consequences. For an alphabet Oand a set Hof labels, let OHbe the alphabet defined in the proof of Theorem 5. Let R(cre, ncoo2) be the set of all rules of types (cre) and (ncoo) with objects in O∪OHand labels in H. Clearly, this is a finite set. Corollary 1. If C1∈CF Gn1,d1(O, H, k1)and C2∈CF Gn2,d2(O, H, k2), then editcR(cre,ncoo2)(C1, C2)< d1·(n1+k1) + d2·(n2+k2)−2. 148 E. Csuhaj–Varj´u et al. Proof. We just write the triangle inequality for C1, C2, C0and we use the result from Theorem 6. Because we work with the reversible completion of the set R(cre, ncoo2), we can pass both from C0to C1,and C2, and conversely, thus having a path from C1to C2.2 This means that any two configurations from CF G(O, H, k) can be reached from each other, they are at a finite distance with respect to the set cR(cre, ncoo2) of rules. The previous corollary gives only an upper bound on the distance among the considered configurations. Can this estimation be improved? This seems to be always possible, at least with a (small) constant: when passing directly from C1 to C2we can “save” that part of the membrane structure of C1which can be found also in C2(for instance, the skin membrane). The question which is the largest improvement in general, or for two configurations with certain “similarities” remains as a research topic. 7 Generators for Families of Configurations Another interesting consequence of Theorem 6 is the fact that the configuration C0 can be seen as a generator of the whole family CFG(O, H, k), with respect to rules from R(cre, ncoo2), or, in terms of P systems, as a normal form for all systems which can use rules for membrane creation (the “minimality” of the configuration C0is somewhat surprising and, of course, pleasant: any recursively enumerable set of numbers can be generated by a system with the initial configuration equal to C0). We place this idea in a more general framework, resembling the one of AFL (abstract family of languages) theory, see [8]. Definition 5. Let C ⊆ CF G(O, H, k)be a family of configurations and Ra set of rules. We define genR(C) = {C∈CF G(O, H, k)|editR(C0, C)<∞for some C0∈ C}. That is, genR(C) is the family of configurations which can be reached, in a finite number of steps, when starting from configurations from C, by using rules from R. Definition 6. For C1,C2⊆CF G(O, H, k)and a set Rof rules, we say that: 1. C1is an R-generator for C2if genR(C1) = C2; 2. C1is an R-cover for C2if C2⊆genR(C1). Of course, any set of configurations is an R-cover for itself with respect to any set of rules, hence of interest are minimal generators and covers, in particular, singleton generators and covers. Definition 7. A family C ⊆ CF G(O, H, k)of configurations is said to be principal with respect to a set Rof rules if there is a configuration C∈CF G(O, H, k)such that genR({C}) = C. In such a case we say that Cis an R-generator for C. Editing Configurations of P Systems 149 In this framework, Theorem 6 directly implies the following interesting result: Theorem 8. The family CF G(O, H, k)is principal with respect to the set of rules R(cre, ncoo2), and C0is an R(cre, ncoo2)-generator for CF G(O, H, k). Because in a principal family each configuration can be reached from any given generator, if the respective set of rules is reversible, then it also follows that any configuration can be reached from any other configuration (passing through the given generator), hence we have: Corollary 2. In the family CF G(O, H, k), any configuration is a generator with respect to cR(cre, ncoo2) = R(cre, dis, coo2). 8 Using Rules of Types (div), (endo), and (ncoo) The rules of type (cre) and (ncoo) are not the only ones for which we can obtain results as above. The use of rules of type (ncoo) (or (cat), (coo)) cannot be avoided, because these rules are the only ones (in the basic set considered here) which can increase the number of objects in the configurations, but membranes can be created also by division. However, as we have noticed already, by division we cannot increase the depth of the membrane structure. This can be done by endocytosis rules, hence a combination of rules of type (div) and (endo) can simulate rules of type (cre). For instance, if we want to create a new membrane, with label g, inside an existing membrane h, we can first pass from [ha]hto [hb]h[gc]g(the object ais supposed to exist in membrane h), by using a division rule, then to [h[gc0]gb0]h, by an endocytosis rule. Still, one more difficulty arises: we cannot divide the skin membrane, hence we cannot start from the configuration C0used in the previous sections, we need at least two membranes in the beginning. On the other hand, by using endocytosis/exocytosis rules (as well as rules of type (coo)), any configuration with nmembranes can be transformed into any configuration with the same number of membranes. Then, if exocytosis is allowed also with respect to the skin membrane, then we can expel membranes from the configurations, thus decreasing the degree of the membrane structures. Of course, by using membrane dissolving rules (but not membrane creation rules) we can again decrease the degree of configurations. Therefore, several combinations of rules can be considered which leads to results like those from Sections 6 and 7 (of course, with edit-distances among configurations different from those in sections above). In what follows we consider only the case when we use rules of types (div), (endo), and (ncoo), again with a bound on the length of rules of type (ncoo), without permitting the exocytosis for the skin membrane (consequently, the number of membranes cannot be decreased). That is, we use 150 E. Csuhaj–Varj´u et al. the set R(div, endo, ncoo2) of rules. Consider also the configurations Cm 0= ([1[2. . . [m]m. . . ]2]1, a1, a2, . . . , am), for all m≥1, where a1, a2, . . . , amare new symbols, not in the alphabet O, with each object aipresent in region i, 1 ≤i≤m. We mention here, without a proof, only the result corresponding to Theorem 8. For m≥1, let us denote CF G≥m(O, H, k) = [ n≥d≥m CF Gn,d(O, H, k), hence this is the family of all configurations C= (µ, M) with membrane structures of degree at least m. Theorem 9. The family CF G≥m(O, H, k)is principal with respect to the set of rules R(div, endo, ncoo2), and Cm 0is an R(div, endo, ncoo2)-generator for this family. It is also worth noting the result corresponding to Theorem 7, which provides a further normal form for systems which are allowed to use rules for the division of membranes and endocytosis, and non-cooperative rules for object evolution: any system of this type of degree at least mis equivalent with a system having the initial configuration equal to Cm 0. If we consider a set of rules containing rules of types (div), (endo), (exo), (ncoo), without restricting the exocytosis, or if we allow dissolving rules, then we can again generate CF G(O, H, k) starting from C0, hence we have a general normal form theorem, for P systems of any degree. In order to have an idea about the way the path from Cm 0to an arbitrary configuration C∈CF G≥m(O, H, k) proceeds, we illustrate the construction for a result like that from Theorem 5 – hence without the complications which appear if we want to protect the multisets of objects, in view of a proof of a result like Theorem 7, and without limiting the size of object processing rules. We consider again a configuration Cwith the membrane structure µfrom Figure 1 and multisets M(i) placed in the compartments i= 1,2, . . . , 10 of µ. The configuration Ccan be generated from C2 0, even if we use no exocytosis rule, and we consider here this case. The set of rules used is given in Table 3, which, like in case of Table 2, presents the rules in the order of the steps when they are used. The symbols b, c, d, e, f used in the rules are chosen in an ad hoc manner; in order to generalize the construction to an arbitrary configuration, these symbols should be related in a systematic manner to the membranes whose evolution they control and to the step of the construction (which is also related to the level of the tree where we work). Such technicalities are left to the reader. 9 A Plethora of Research Topics Several research topics were already mentioned above, and many others can be considered. We formulate here only some of them, without any intention to be Editing Configurations of P Systems 151 Table 3. Rules of types (div), (endo), (ncoo) for obtaining the configuration from Figure 1 Step Rules 1 [1a1→M(1)]1,[2a2]2→[2b1]2[3b2]3 2 [2b1]2→[2c1]2[4c2]4,[3b2]3→[3c1]3[5c2]5 3 [2c1]2[4c2]4→[2[4c0 2]4c0 1]2,[3c1]3[5c2]5→[3[5c0 2]5c0 1]3 4 [2c0 1→M(2)]2,[3c0 1→M(3)]3, [4c0 2]4→[4d1]4[7d2]7,[5c0 2]5→[5d1]5[6d2]6 5 [4d1]4[7d2]7→[4[7d0 2]7d0 1]4,[5d1→M(5)]5,[6d2→M(6)]6 6 [4d0 1→M(4)]4,[7d0 2]7→[7e1]7[8e2]8 7 [7e1→M(7)]7,[8e2]8→[8e0 2]8[9e3]9 8 [9e3→M(9)]9,[8e0 2]8→[8f1]8[10f2]10 9 [8f1]8[10f2]10 →[8[10f0 2]10f0 1]8 10 [8f0 1→M(8)]8,[10f0 2→M(10)]10 exhaustive (and without knowing which of these topics are difficult and which are straightforward). In the previous sections we have investigated only some very particular cases: the family CFG(O, H, k), the set of rules R(cre, ncoo2), the generator C0, as well as the family CFG≥2(O, H, k), the set of rules R(div, endo, ncoo2), and the generator Cm 0. Consider other families of configurations. For instance, what about CF Gn,d(O, H, k)? What about families using particular types of membrane structures (described by linear trees, binary trees, trees of depth 2, etc)? Then, there are families of P systems – hence of configurations – which appear in a natural way in various contexts; such a context is that of solving NP-complete problems in polynomial time, using a family of P systems constructed in an uniform manner, starting from the problem to solve (see details in [16] and in a series of other papers). Can such a family be generated from a given unique configuration, using a suitable set of rules? Many problems are suggested by the parallelism with the AFL theory. Define a sort of “abstract family of configurations”, with “nice” closure properties (under operations defined by evolution rules, but also under set-theoretical operations, such as union and intersection). Consider sets of rules Rand families of configurations Csuch that genR(C)6=CF G(O, H, k); which properties has such a family? A large panoply of problems is related to the set of rules taken into account. Any set of rules of types belonging to a subset of the set {(1),. . . , (11)}can be considered, arbitrary or reversible, with specific restrictions on the size of multisets used in rules for object evolution. Also, other types of rules can be considered. 152 E. Csuhaj–Varj´u et al. Find families of configurations and sets of rules for which the minimal generators are not singletons (that is, find families of configurations which are not principal with respect to a given set of rules). Is the property of being a generator decidable for a given family of configurations, a given set of rules, and a given candidate generator? (The answer should be negative in general, because of the Turing completeness of most classes of P systems.) Providing that we know that a family is principal, how can we find a generator? Is this possible in an effective, algorithmic way? Which is the complexity of such an operation? The decidability and complexity issues were already mentioned for the question whether a configuration can be reached from another configuration by means of rules in a given set, and this is of a crucial importance (e.g., for the possible applications of our approach). Again, the answer depends in an essential manner on the set of rules – but how exactly this happens it remains to be discovered. Connections with previous investigations of reachability issues will probably be useful, especially for cases where the reachability can be decided – see, e.g., [9], [10]. A series of interesting questions concerns the possible relations of the investigations above with other areas of computer science, of mathematics in general. Processing configurations means to process the underlying trees, too. Can any connection with tree/graph grammars be established? Then, we can naturally define a graph on the set CF G(O, H, k), with the configurations as nodes and the arcs indicating the transitions among configurations with respect to a given set of rules. How this link can be used? Looking for (the number of) connected components in this graph seems to be directly related to the cardinality of generator sets. Furthermore: what about the topological properties of the metric space defined by a distance editR? Which is the relevance of such connections for membrane computing? On the same line, interesting connections seems to be possible with evolutionary computing. Assume that we have a criterion according to which some configurations can be considered “better” than others (and that this criterion can be checked in an efficient manner). Then we can try to “improve” the configurations as usual in evolutionary computing: start from an initial population of configurations, apply a given number of rules, randomly, to these configurations, so that a new population is obtained; select from this population only part of configurations, in the decreasing order of their quality; repeat these steps until a satisfactory configuration is obtained (or a given number of steps have been performed). Any application of this strategy? We close this section with an “exotic” question, that of self-reproduction: by sending membranes out of the skin membrane (by exocytosis – rules of type (a)), we can send a whole configuration/system into the environment. How can this be done in such a way to start from a given configuration (any given configuration?) and to send out a copy of it? This is interesting also as an intrinsic problem, and it can be useful both for creating exponential space for solving hard problems and Editing Configurations of P Systems 153 for creating further and further agents capable of “exploring the extraterrestrial space” in the speculative framework sketched in [5]. 10 Final Remarks We conclude these notes with the belief that the investigations started here deserve further efforts, both because of the mathematical appeal of the many questions raised in this framework, but also because of the interest for membrane computing in general, and for possible applications in particular (e.g., in finding heuristic algorithms for addressing certain decidability or optimization problems). We hope to return to this topic in a forthcoming paper. Acknowledgement The work of Gh. P˘aun was partially done during a stay as a visiting scientist at MTA SZTAKI EU Center of Excellence, Budapest. References 1. A. Alhazov, T.-O. Ishdorj: Membrane operations in P systems with active membranes. Proc. Second Brainstorming Week on Membrane Computing, Sevilla, February 2004, TR 01/04 of Research Group on Natural Computing, Sevilla University, 2004, 37–44. 2. A. Alhazov, L. Pan, Gh. P˘aun: Trading polarizations for labels in P systems with active membranes. Acta Informatica, 41, 2-3 (2005), 111–144. 3. G. Bel Enguix, M.D. Jim´enez-Lopez: Linguistic membrane systems and applications. In Applications of Membrane Computing (G. Ciobanu, Gh. P˘aun, M.J. P´erezJim´enez, eds.), Springer-Verlag, Berlin, 2005. 4. L. Cardelli: Brane calculi. Interactions of biological membranes. Proc. Computational Methods in Systems Biology, 2004, Springer-Verlag, to appear. 5. C. Calude, Gh. P˘aun: Bio-steps beyond Turing. BioSystems, 77 (2004), 175–194. 6. 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. Proc. Second Brainstorming Week on Membrane Computing, Sevilla, February 2004, TR 01/04 of Research Group on Natural Computing, Sevilla University, 2004, 139–151. 7. R. Freund, L. Kari, M. Oswald, P. Sosik: Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science, 330, 2 (2005), 251–266. 8. S. Ginsburg: Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland, Amsterdam, 1975. 9. O.H. Ibarra: On the computational complexity of membrane computing systems. Theoretical Computer Science, 320, 1 (2004), 98–109. 10. O.H. Ibarra, Z. Dang, O. Egecioglu: Catalytic membrane systems, semilinear sets, and vector addition systems. Theoretical Computer Science, 312, 2-3 (2004), 378–400. 154 E. Csuhaj–Varj´u et al. 11. S.N. Krishna, Gh. P˘aun: P systems with mobile membranes. Natural Computing, to appear. 12. M. Minsky: Computation. Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967. 13. N.J. Nilsoon: Artificial Intelligence. A New Synthesis. The Morgan Kaufmann Series in Artificial Intelligence, San Francisco, 1998. 14. Gh. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61 (2000), 108–143. 15. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002. 16. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini: Teor´ıa de la Complejidad en Modelos de Computati´on Celular con Membranas. Editorial Kronos, Sevilla, 2002.