No Cycles in Compartments. Starting from Conformon-P Systems

No Cycles in Compartments. Starting from Conformon-P Systems Pierluigi Frisco1, Gheorghe P˘aun2 1School of Mathematical and Computer Sciences Heriot-Watt University Edinburgh, EH14 4AS, UK E-mail: [email protected] 2Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucharest, Romania and Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mails: [email protected], [email protected] Summary. Starting from proofs of results about the computing power of conformon- P systems, we infer several results about the power of certain classes of tissue-like P systems with (cooperative) rewriting rules used in an asynchronous way, without cycles in compartments. This last feature is related to an important restriction appearing when dealing with lab implementations of P systems, that of avoiding local evolution loops of objects. 1 Introduction This note addresses a technical issue which appeared in the framework of the recent attempt to implement a P system in biochemical terms, at Technion institute, Haifa, Israel, namely of avoiding cyclical evolution of chemicals in any compartment of the system – see a more precise description of the problem in [9]. Here we consider a class of tissue-like P systems, namely as introduced in [16], with rewriting rules present in membranes, and with target indications of the forms here, go associated with the “products of reactions”: rules of the form u→v, where uand vare multisets of objects and the objects in vhave associated target indications here, go (actually, here is omitted) indicating that the respective object remains in the same compartment or it has to go to any of the adjacent compartments, non-deterministically choosing the destination. We also consider an evolution-communication (EC) version of these systems, following the ideas of [1], i.e., using evolution rules without target indications and using separate communication rules (of the form (a, go), with the obvious meaning: object 158 P. Frisco, Gh. P˘aun ais communicated to any of the adjacent membranes). In order to transfer in a direct way to these systems results from conformon-P systems area, we add to the definition in [16] several “non-standard” ingredients: we work asynchronously (in any step, in any compartment, a rule may be used or not), maybe with a priority relation among rules, of a global type (in each compartment, evolution rules have priority over communication rules: if an object can evolve and, at the same time, communicated, an evolution rule is applied first), an acknowledging membrane (the computation stops when any object is sent to this membrane, which is empty in the beginning of the computation). The number of membranes we use is arbitrary (rather high, if we take into account the number of membranes used in conformon-P systems simulating register machines), but, on the good side, the evolution rules we need to simulate a conformon-P system are of a very restrictive form: each of the multisets u, v from a rule u→vhas exactly two objects. Although, for the sake of readability, we recall here the definitions of conformon- P systems and of P systems with a graph structure, we do not enter into details, and we assume the reader to be familiar with basic elements of membrane computing. However, we indicate a series of papers related to conformons. This concept was introduced independently in [10] and [17]. Following the definition given in [10] conformons and conformon-like entities have been classified into 10 families according to their biological functions [12]. To know more about the Bhopalator refer to [11, 13]. The term conformon was adopted in [14, 15] where the authors started to develop a quantum mechanical theory based on this concept. Conformon-P systems have been introduced in [3] and later studied, among others, in [4, 6]. Conformon-P systems have also been successfully used as a platform to model biological process. The interested reader can refer to [8, 2, 7]. 2 Basic Definitions Let Vbe an alphabet (a finite set of abstract symbols), and Nbe the set of natural numbers, including 0. A multiset over Vis a function M:V−→ N∪ {+∞}. The support of M(the set of elements a∈Vfor which M(a)>0) is denoted by supp(M) and the cardinality of M(the sum of multiplicities of all elements in supp(M)) is denoted by |M|. 2.1 Conformon-P Systems In what follows, a conformon is an element of V×N, denoted by [a, n]. We refer to aas the name of the conformon [a, n] and to nas its value. Two conformons can interact according to an interaction rule. An interaction rule is of the form ae →b, where a, b ∈Vand e∈N, and it says that a conformon with name acan give efrom its value to the value of a conformon having name b. If, for instance, there are conformons [a, 5] and [b, 9] and the rule a3 →b, one application this rule leads to [a, 2] and [b, 12]. As here we consider that the value No cycles in compartments 159 of a conformon cannot be a negative number, the rule a3 →bcannot be applied to [a, 2]. Each membrane present in a conformon-P system has associated a label, different from the labels of other membranes. These membranes are placed in the nodes of a directed graph, hence they are connected in a unidirectionally way. Each connection has associated a predicate, which is an element of the set pred(N) = {≥ n, ≤n|n∈N}. If, for instance, there are two compartments (with labels) m1and m2and there is an connection from m1to m2having predicate ≥4, then conformons having value greater than or equal to 4 can pass from m1 to m2. Aconformon-P system is a construct Π= (V, µ, ωz, ack, L1, . . . , Lm, R1, . . . , Rm), where: Vis a finite alphabet; µ= (Q, E) is a directed labelled graph underlying Π, where Q={1, . . . , m}is the set of membranes (we also say compartments) of Π; E⊆Q×Q×pred(N) defines directed labelled edges between vertices, indicated by (i, j, pred), i, j ∈Q, i 6=j, where pred ∈pred(N) is a predicate; ωzwith ω∈ {in, out}and z∈Qindicates whether Πis an accepting (ω=in) or generating (ω=out) device; the compartment zcontains the input or output, respectively; ack ∈Qindicates the acknowledging compartment; Li: (V×N)→N∪{+∞}, i ∈Q, are multisets of conformons initially associated with the vertices in Q; Ri, i ∈Q, are finite sets of interaction rules associated with the vertices in Q, with supp(Lack) = ∅. Let Miand Ribe the multiset of conformons and the set of rules, respectively, associated with the compartment i∈Q. Two conformons present in compartment ican interact according to a rule in Risuch that the multiset of conformons Mi changes into M0 i. If, for instance, [a, p],[b, q]∈Mi, a e →b∈Riand p≥e, then M0 i= (Mi− {[a, p],[b, q]})∪ {[a, p −e],[b, q +e]}. A conformon [a, p] present in compartment ican pass to compartment jif (i, j, pred)∈Eand pred(p) holds. This passage changes the multisets of conformons Miand Mjinto M0 iand M0 j, respectively, such that M0 i=Mi− {[a, p]}and M0 j=Mj∪ {[a, p]}. At the moment we do not assume any requirement (such as maximal parallelism, priorities, etc.) on the application of operations. If a conformon can pass to another compartment or interact with another conformon according to an interaction rule, then one of the two operations or none of them is non-deterministically chosen. 160 P. Frisco, Gh. P˘aun The possibility to carry out one of the two allowed operations in a compartment or none of them lets conformon-P systems to be non-deterministic. Nondeterminism can also arise from the configurations of a conformon-P system if in a compartment a conformon can interact with more than one conformon and also from the graph underlying Πif a compartment has edges with the same predicate going to different compartments. Aconfiguration of Πis an m-tuple (M1, . . . , Mm) of multisets over V×N. The m-tuple (L1, . . . , Lm), is called initial configuration (remember that supp(Lack) = ∅, so in the initial configuration the acknowledging compartment does not contain any conformon) while any configuration having supp(Mack)6=∅is called final configuration. In a final configuration no operation is performed even if it could. For two configurations (M1, . . . , Mm),(M0 1, . . . , M0 m) of Πwe write (M1, . . . , Mm)⇒(M0 1, . . . , M0 m) indicating a transition from (M1, . . . , Mm) to (M0 1, . . . , M0 m), that is, the application of one operation to at least one conformon. In other words, in any configuration in which supp(Lack) = ∅any conformon present in a compartment can either interact with another conformon present in the same compartment or pass to another compartment or remain in the same compartment unchanged. If no operation is applied to a multiset Mi, then M0 i=Mi. The reflexive and transitive closure of ⇒is indicated by ⇒∗. Acomputation is a finite sequence of transitions between configurations of a system Πstarting from (L1, . . . , Lm). In case Πis an accepting device (ω=in), then the input is given by the number of conformons (counted with their multiplicity) present in Lz. The input is accepted by Πif it reaches a configuration in which any conformon is present in ack, halting in this way the computation. Formally: N(Π) = {|Lz| | (L1, . . . , Lm)⇒∗(M0 1, . . . , M0 m)⇒(M1, . . . , Mm), supp(M0 ack) = ∅, supp(Mack)6=∅}. In case Πis a generating device (ω=out), then supp(Lz) = ∅. The result of a computation is given by Mzwhen any conformon is present in ack. When this happens the computation is halted and the number of conformons (counted with their multiplicity) present in Mzdefines the number generated by Π. Formally: N(Π) = {|Mz| | (L1, . . . , Lm)⇒∗(M0 1, . . . , M0 m)⇒(M1, . . . , Mm), supp(M0 ack) = ∅, supp(Mack)6=∅}. In the conformon-P systems area, in general one uses graphical representations instead of formal definitions in order to specify systems appearing in examples or proofs. We recall now some conventions used in these representations – details can be found in the papers mentioned in the end of Introduction. Membranes/compartments are represented by labelled ovals, having inside the associated conformons and interaction rules. Conformons present in the initial No cycles in compartments 161 configuration of a system are written in bold inside a membrane while the ones written in normal font are present in that compartment in one of the possible configurations of the system. A slash (/) between values in a conformon indicates that a conformon can have any of the indicated values. The multiplicity is indicated only for conformons which appear in more than one copy. Directed edges between compartments are represented as arrows with their predicate indicated close to them. Several edges connecting two compartments are depicted as just one edge with different predicates separated by a slash (/). For instance, Figure 1 presents a conformon-P system which accepts any positive even number (the input membrane is the one with label 1 and the acknowledging one is membrane 11). ≤11 ≥1 ≥2 ≥3 ≥5 ≥6 ≤2 ≤5 ≤1 ≤0 ≥7 ≥7 ≤0 ≥7 ≥8 ≤3 ≤6 ≥14 10 ≤8 ≤0/≥14 [B,3/14] [C,11] 2 ([A, 0], q) 15 [B, 7] 11 [B, 14] [C, 0] 14 B11 →C [A, 8] 9 [B, 1] [A, 6] 10 A6 →B [C, 5] [A, 2] 12 A2 →C [B, 7] [C, 7] 13 C7 →B 7 6 5 4 3 [B, 3] B2 →A [C, 11] C6 →A ([A,0], p) 1 [B, 1/3] [A, 2/6/8] [C, 5/11] [A, 6/8] [C, 11] [A, 6/8] [C, 5/11] [B, 3] [A, 6/8] [C, 5/11] [B, 3] [A, 2/6/8] [C, 5/11] [A, 8] [C, 11] ≥11 8 ≥3 Fig. 1. A conformon-P system accepting even numbers. In proofs there appear large conformon-P systems, that is why it is useful to consider modules which are sort of shortcuts of graphical representations. Such modules are explained in detail in several papers, e.g., in [3]. The basic modules are the splitter (it selects conformons depending on their values; specifically, when conformons of type [a, pi],1≤i≤h, are present in a 162 P. Frisco, Gh. P˘aun given compartment, they can pass to specific different compartments depending on values pi) and the separator (it selects conformons depending on their name; specifically, when conformons of type [ai, p],1≤i≤h, are present in a compartment, they can pass to specific different compartments depending on ai). In the pictorial representations of conformon-P systems the modules are indicated by tick ovals, linked by arrows marked with predicates, which are of the form =niin the case of splitters and of the form [a, pi] in the case of separators; usual membranes and arrows marked with predicates can be interleaved with modules. For instance, in Figure 2 we give a version of the system represented in Figure 1 where a splitter is also involved. ≤11 ≤0 ≥7 ≥7 ≤0 ≥7 ≥14 ≤0/≥14 = 8 = 1/ = 6 ≥1= 3/ = 11 = 2/= 5 spl [B,3/14] [C,11] 2 ([A, 0], q) 15 [B, 7] 11 [B, 14] [C, 0] 14 B11 →C [A, 8] 9 [B, 1] [A, 6] 10 A6 →B [C, 5] [A, 2] 12 A2 →C [B, 7] [C, 7] 13 C7 →B [B, 3] B2 →A [C, 11] C6 →A ([A,0], p) 1 ≥3 [B, 1/3] [A, 2/6/8] [C, 5/11] Fig. 2. The conformon-P system with a splitter associated to the system in Figure 1. 2.2 Asynchronous Tissue-like P Systems We introduce the P systems of the form we have described in the Introduction, with a series of ingredients as presented before for conformon-P systems. Because we work only with asynchronous systems, from now on we omit mentioning this feature. An EC tissue-like P system of degree mis a tuple No cycles in compartments 163 Π= (V, µ, ωz, ack, L1, . . . , Lm, R1, . . . , Rm, P1, . . . , Pm), where: Vis a finite alphabet whose elements are called objects; µ= (Q, E) is a graph indicating the underlying compartment structure of Π, where Q={1, . . . , m}is the set of membranes/compartments; E⊆Q×Qis the set of directed edges between compartments; ωzwith ω∈ {in, out}and z∈Qindicates if Πis an accepting (ω=in) or generating (ω=out) device; the compartment zcontains the input or output, respectively; ack ∈Qindicates the acknowledging compartment; Li:V→N∪{+∞},1≤i≤m, are multisets of objects in V, with supp(Lack) = ∅; Ri,1≤i≤m, are sets of evolution rules of the form ab →cd with a, b, c, d ∈V; Pi,1≤i≤m, are sets of communication rules of the form (a, go) with a∈V. A tissue-like P system is cycle-free if ab →cd ∈Riimplies that cd →ab does not belong to Ri(with some abuse of notation we represent multisets by strings and all their permutations). Aconfiguration of Πis an m-tuple (M1, . . . , Mm) of multisets over V. The mtuple (L1, . . . , Lm), is called initial configuration (in the initial configuration the acknowledge compartment does not contain any object) while any configuration having supp(Mack)6=∅is called final configuration. In a final configuration no operation is performed even if it could. For two configurations (M1, . . . , Mm),(M0 1, . . . , M0 m) of Πwe write (M1, . . . , Mm)⇒(M0 1, . . . , M0 m) indicating a transition from (M1, . . . , Mm) to (M0 1, . . . , M0 m), that is, the application of one rule in a compartment according to the following. If a, b ∈Miand ab →cd ∈Ri, then M0 i=Mi− {a, b} ∪ {c, d}. If a∈Miand (a, go)∈Pi, then M0 i=Mi− {a}, M0 j=Mj∪ {a}if (i, j)∈E. If no rule is applied to a multiset Mi, then M0 i=M0 i. The reflexive and transitive closure of ⇒is indicated by ⇒∗. If in a configuration a symbol can be subject to more than one rule, then one of them is non-deterministically applied. Acomputation is a finite sequence of transitions between configurations of the system Πstarting from (L1, . . . , Lm). In case Πis an accepting device (ω=in), then the input is given by the number of symbols (counted with their multiplicity) present in Lz. The input is accepted by Πif it reaches a configuration in which any conformon is present in ack, halting in this was the computation. Formally, N(Π) = {|Lz| | (L1, . . . , Lm)⇒∗(M0 1, . . . , M0 m)⇒(M1, . . . , Mm), supp(M0 ack) = ∅, supp(Mack)6=∅}. In case Πis a generating device (ω=out), then supp(Lz) = ∅. The result of a computation is given by Mzwhen any symbol is present in ack. When this 164 P. Frisco, Gh. P˘aun happens the computation is halted and the number of symbols (counted with their multiplicity) present in Mzdefines the number generated by Π. Formally, N(Π) = {|Mz| | (L1, . . . , Lm)⇒∗(M0 1, . . . , M0 m)⇒(M1, . . . , Mm), supp(M0 ack) = ∅, supp(Mack)6=∅}. As usual in P systems (i.e., without separating evolution from communication), we avoid rules of the form (a, go) and associate target indication directly to evolution rules: an object which has to be communicated will appear in the right hand side of a rule paired with go (the objects without such a pair remain in the same membrane). Note the important detail that this time the communication of an object cappearing in the form (c, go) in a rule must be done immediately, this does not mean application of a rule, but it is just part of using the evolution rule. This is a difference with respect to conformon-P systems and to EC tissue-like P systems, but in the proofs below we will not have to take care of this aspect: communication will be done by evolution rules of the form a→(a, go) which are directly associated with communication rules of the form (a, go). 3 Computing with Conformon-P Systems We recall now some results concerning the computing power of conformon-P systems. Proofs can be found, e.g., in [3]. A conformon-P systems is called value-restricted (in short, VR) if in its initial configuration all conformons present in an unbounded number of copies have value 0. In this way, the total value of conformons present in the system at any step of a computation is finite. Theorem 1. The family of sets of numbers generated by VR conformon-P systems coincides with the family of sets of numbers generated by partially blind register machines. The conformon-P system which can simulate a partially blind register machine is based on the construction indicated in Figure 3. We recall it because later we will point out some basic features of this construction useful in inferring results about (asynchronous) tissue-like P systems. From Theorem 2 in [5] we know that if in the conformon-P system described in the previous theorem either priorities, maximal concurrency, or maximal parallelism are added, then the resulting systems are computationally complete. Theorem 2. The family of sets of numbers generated by VR conformon-P systems where evolution has priority on communication (if a conformon can be subject of an interaction rule and it can also pass to another membrane, then the interaction should be done) coincides with the family of sets of numbers generated by register machines (hence with the family of Turing computable sets of numbers). No cycles in compartments 165 [s00 j,γ ,7] [sf,7] [s0 j,γ ,6] [s00 j,γ ,4] [si,1] [si,3] si 1 →s0 j,γ si 3 →s00 j,γ [s0 j,γ ,2] [γ, 4] ([γ, 0],kγ) γ4 →s0 j,γ s00 j,γ 3 →γ [s00 j,γ ,4] [sf,7] [si,3][si,1]/ 2 3 [s0 j,γ ,2]/ [γ, 4] 4 [s0 j,γ ,6] [s00 j,γ ,4] [si,0]/ [s0 j,γ ,7]/ [s00 j,γ ,7] [s0 j,γ ,0]/[sj,7]/ [s00 j,γ ,0] 5 ([γ, 0],+∞) [s0 j,γ ,6] s0 j,γ 4 →γ [s00 j,γ ,1] [γ, 3] γ3 →s00 j,γ [s00 j,γ ,4] [s0 j,γ ,0] [s00 j,γ ,0] [si,7] 1 si 6 →s0 j,γ si 4 →s00 j,γ [s0 j,γ ,6] [γ, 3] [s00 j,γ ,1]/ [sj,0] [s0 j,γ ,7] 6 s00 j,γ 7 →sj s0 j,γ 7 →sj Fig. 3. The conformon-P system related to Theorem 1. Also for this case we recall – in Figure 4 – the construction used in proving that a conformon-P system with priority as above can simulate a register machine. 4 From Conformon- to Tissue-like P Systems First, let us point out a direct passage from conformon-P systems to EC tissue-like P systems. Theorem 3. Given any VR conformon-P system Π= (V, µ, ωz, ack, L1, ..., Lm, R1, . . . , Rm), we can construct an EC tissue-like P system Π0= (V0, µ0, ωz, ack, L0 1, . . . , L0 m, R0 1, . . . , R0 m, P 0 1, . . . , P0 m)such that N(Π0) = N(Π). Proof. Consider a conformon-P system Πas above, with µ= (Q, E); denote by Sthe sum of the values of the conformons in Π. We construct the tissue-like P system Π0with: V0={ap|a∈V, 0≤p≤S}; µ0= (Q, E0) with (i, j)∈E0for each (i, j, pred)∈E; L0 i(ap) = kif Li([a, p]) = kfor 1 ≤i≤m; apbq→ap−ebq+e∈R0 iif ae →b∈Ri, 0 ≤p, q ≤S, p ≥e; (ap, go)∈P0 iif (i, j, ≥r)∈Efor r≤p≤Sor (i, j, ≤r)∈Efor 0 ≤p≤r.