Decidability of Divergence for Catalytic P Systems

Decidability of Divergence for Catalytic P Systems Nadia Busi Dipartimento di Scienze dell’Informazione Universit`a di Bologna Mura A. Zamboni 7, I-40127 Bologna, Italy [email protected] Summary. P systems are a biologically inspired model introduced by Gheorghe P˘aun with the aim of representing the structure and the functioning of the cell. Since their introduction, several variants of P systems have been proposed and explored. We concentrate on the class of catalytic P systems without priorities associated to the rules. We show that the divergence problem (i.e., checking for the existence of an infinite computation) is decidable in such a class of P systems. As a corollary, we obtain an alternative proof of the nonuniversality of deterministic catalytic P systems, an open problem recently solved by Ibarra and Yen. 1 Introduction Membrane computing is a branch of natural computing, initiated by Gheorghe P˘aun with the definition of P systems in [11, 12, 13]. The aim is to provide a formal modeling of the structure and the functioning of the cell, making use especially of automata, languages and complexity theoretic tools. Quoting from the Milano webpage [17], “A P system is a computing model which abstracts from the way the alive cells process chemical compounds in their compartmental structure. In short, in the regions defined by a membrane structure we have objects which evolve according to given rules. The objects can be described by symbols or by strings of symbols (in the former case their multiplicity matters, that is, we work with multisets of objects placed in the regions of the membrane structure; in the second case we can work with languages of strings or, again, with multisets of strings). By using the rules in a nondeterministic, maximally parallel manner, one gets transitions between the system configurations. A sequence of transitions is a computation. With a halting computation we can associate a result, in the form of the objects present in a given membrane in the halting configuration, or expelled from the system during the computation. Various ways of controlling the transfer of objects from a region to another one and 64 N. Busi of applying the rules, as well as possibilities to dissolve, divide, create, or move membranes were considered.” Since their introduction, plenty of variants of P systems have been introduced, and a lot of research effort has been carried out, especially concerned with the study of the expressivity and the universality of the proposed models and with the ability to solve NP-complete problems in polynomial time. In this paper we concentrate on catalytic P systems, namely systems whose rules are of one of the following kinds: •context–free rules, with the form a→vand representing the fact that an instance of ais consumed and the objects in vare produced, or •catalytic rules, with the form ca →cv and representing the fact that ais consumed and the objects in vare produced, provided that an instance of catalyst cis present inside the membrane, and that such an instance of chas not been used yet by another concurrently executed rule. As we will see in Section 3, catalysts are neither produced nor consumed by evolution rules, but they are used to bound the number of instances of catalytic rules applied in a maximal parallelism step. The computational power of catalytic P systems has been tackled in various papers: in [12] the universality of P systems with catalysts and priorities is proved; the result has been improved in [15, 16] by showing that priorities are not necessary for universality. In [5, 4] some minimality properties for universality are investigated; in particular, [4] shows that two catalysts are sufficient to get universality. However, the encodings presented in the aforementioned works present a high degree of nondeterminism. For example, in [4] an encoding of deterministic Minsky’s register machines [10] is provided, that satisfies the following properties: •if the register machine halts, then the encoding of the register machine has a halting computation (but there could also be other nonterminating computations); •if the register machine does not halt, then all the computations of the encoding are nonterminating. A corollary of this result is the undecidability of the existence of an halting computation for catalytic P systems, but the nondeterministic nature of the encoding leaves the door open to the possibility for other properties to be decidable. This fact is quite relevant from the point of view of systems biology, where the interest is to predict the behavior of the living matter. In the present paper we show that divergence, namely, the existence of a nonterminating computation, is decidable for catalytic P systems. The proof is based on the theory of well-structured transition systems [3]: the existence of an infinite computation starting from a given state is decidable for finitely branching transition systems, provided that the set of states can be equipped with a well-quasi-ordering, i.e., a quasi-ordering relation which is compatible with the transition relation and such that each infinite sequence of states admits an increasing subsequence. To this aim, we define a quasi-ordering on the configurations of catalytic P systems Decidability of Divergence for Catalytic P Systems 65 that turns out to be a well-quasi-ordering compatible with the maximally parallel evolution rule. A consequence of this result is the impossibility to provide a deterministic encoding of any Turing powerful formalism in catalytic P systems, as for deterministic systems divergence and the existence of an halting computation are equivalent properties. This yields to an alternative proof of the nonuniversality of deterministic catalytic P systems, an open problem raised in [6, 14] and recently solved by Ibarra and Yen [8, 9]. The paper is organized as follows. After providing some basic definitions in Section 2, in Section 3 we define catalytic P systems. Section 4 is devoted to recalling some basic notions and results concerning well-quasi-orderings and wellstructured transition systems that will be used in the following. Section 5 is devoted to the decidability result: after providing a finer notion of the configurations and evolution rules of catalytic P systems that is suitable to our aims, we define a quasi-ordering relation on the configurations and show that it turns out to be a well-quasi-ordering compatible with the maximally parallel evolution rule, and finally we make use of the theory of well-structured transition systems to get the decidability of divergence. Some conclusive remark is reported in Section 6. 2 Basic definitions In this section we provide some definitions that will be used throughout the paper. We start with the definition of multisets and multiset operations. Definition 1. Given a set S, a finite multiset over Sis a function m:S→IN such that the set dom(m) = {s∈S|m(s)6= 0}is finite. The multiplicity of an element sin mis given by the natural number m(s). The set of all finite multisets over S, denoted by Mfin(S), is ranged over by m. A multiset msuch that dom(m) = ∅is called empty. The empty multiset is denoted by ∅. Given the multiset mand m0, we write m⊆m0if m(s)≤m0(s)for all s∈S while ⊕denotes their multiset union:m⊕m0(s) = m(s) + m0(s). The operator \ denotes multiset difference:(m\m0)(s) = if m(s)≥m0(s)then m(s)−m0(s)else 0. The scalar product,j·m, of a number jwith mis (j·m)(s) = j·(m(s)). The cardinality of a multiset is the number of occurrences of elements contained in the multiset: |m|=Ps∈Sm(s). The set of parts of a set Sis defined as P(S) = {X|X⊆S}. The restriction to a subset of a multiset is defined as follows: Definition 2. Let mbe a finite multiset over Sand X⊆S. The multiset m|Xis defined as follows: for all s∈S, m|X(s) = ½m(s)if s∈X, 0otherwise. We provide some basic definitions on strings, cartesian products and relations. 66 N. Busi Definition 3. A string over Sis a finite (possibly empty) sequence of elements in S. Given a string u=x1. . . xn, the length of uis the number of occurrences of elements contained in uand is defined as follows: |u|=n. With S∗we denote the set of strings over S, and u, v, w, . . . range over S. Given n≥0, with Snwe denote the set of strings of length nover S. Given a string u=x1. . . xnand isuch that 1≥i≥n, with (u)iwe denote the i-th element of u, namely, (u)i=xi. Given a string u=x1. . . xn, the multiset corresponding to uis defined as follows: for all s∈S,mu(s) = |{i|xi=s∧1≤i≤n}|. With abuse of notation, we use uto denote also mu. Definition 4. With S×Twe denote the cartesian product of sets Sand T, with ×nS,n≥1, we denote the cartesian product of ncopies of set Sand with ×n i=1Si we denote the cartesian product of sets S1, . . . , Sn, i.e., S1×. . . ×Sn. The ith projection of (x1, . . . , xn)∈ ×n i=1Siis defined as πi(x) = xi, and lifted to subsets X⊆ ×n i=1Sias follows: πi(X) = {πi(x)|x∈X}. Given a binary relation Rover a set S, with Rnwe denote the composition of ninstances or R, with R+we denote the transitive closure of R, and with R∗we denote the reflexive and transitive closure of R. 3 Catalytic P Systems We recall the definition of catalytic P systems without priorities on rules provided in [4]. For a thorough description of the model, motivation and examples see, e.g., [1, 2, 11, 12, 13]. To this aim, we start with the definition of a membrane structure: Definition 5. Given the alphabet V={[,]}, the set MS is the least set inductively defined by the following rules: •[ ] ∈MS, •if µ1, µ2, . . . , µn∈MS,n≥1, then [µ1. . . µn]∈MS. We define the following relation over MS:x∼yiff the two strings can be written in the form x= [1...[2. . .]2...[3. . .]3. . .]1and y= [1. . . [3. . .]3...[2. . .]2...]1 (i.e., if two pairs of parenthesis that are neighbors can be swapped together with their contents). The set MS of membrane structures is defined as the set of equivalence classes w.r.t. the relation ∼∗. We call a membrane each matching pair of parenthesis appearing in the membrane structure. A membrane structure µcan be represented as a Venn diagram, in which any closed space (delimited by a membrane and by the membranes immediately inside) is called a region of µ. Decidability of Divergence for Catalytic P Systems 67 Definition 6. Acatalytic P system (of degree d, with d≥1) is a construct Π= (V, C, µ, w0 1, . . . , w0 d, R1, . . . , Rd, i0), where: 1. Vis a finite alphabet whose elements are called objects; 2. C⊆Vis a set of catalysts; 3. µis a membrane structure consisting of dmembranes (usually labeled with i and represented by corresponding brackets [iand ]i, with 1≤i≤d); 4. w0 i,1≤i≤d, are strings over Vassociated with the regions 1,2, . . . , d of µ; they represent multisets of objects present in the regions of µ(the multiplicity of a symbol in a region is given by the number of occurrences of this symbol in the string corresponding to that region); 5. Ri,1≤i≤d, are finite sets of evolution rules over Vassociated with the regions 1,2, . . . , d of µ; these evolution rules are of the forms a→vor ca → cv, where cis a catalyst, ais an object from V\C, and vis a string from ((V\C)× {here, out, in})∗; 6. i0is a number between 1and dand it specifies the output membrane of Π. The membrane structure and the multisets represented by wi, 1 ≤i≤d, in Π constitute the initial state1of the system. A transition between states is governed by an application of the evolution rules which is done in parallel; all objects, from all membranes, which can be the subject of local evolution rules have to evolve simultaneously. The application of a rule2u→vin a region containing a multiset mresults in subtracting from mthe multiset identified by u, and then in adding the multiset defined by v. The objects can eventually be transported through membranes due to the targets in and out (we usually omit the target here). Note that the catalysts are neither created nor destroyed by the application of the rules: they simply bound the number of occurrences of (particular sets of) rules in a maximal parallelism step. Moreover, catalysts cannot move across the membranes. The system continues parallel steps until there remain no applicable rules in any region of Π; then the system halts. We consider the number of objects from Vcontained in the output membrane i0when the system halts as the result of the underlying computation of Π. We say that a P system Πdiverges if there exists an infinite computation starting from the initial state of Π. For example, a graphical representation of the initial state of the P system Π1= ({a, b, c},{c},[1[2]2]1, aabc, abc, {a→b, cb →ca, ca →caa},{ca →cb, cb → cba},1) is depicted in Figure 1. 1Here we use the term state instead of the classical term configuration because we will define a (essentially equivalent but syntactically) different notion of configuration in Section 5. 2We use u→vas a shorthand to denote both the rules of kind a→wand ca →cw. 68 N. Busi ' & $ % ' & $ % 1 2 aabc a→b cb →ca ca →caa abc ca →cb cb →cba Fig. 1. The initial state of the P system Π1. Even if both a copy of aand a copy of bare present in the membrane 1 in the initial state, rules cb →ca and ca →caa cannot be applied together in the same step, as only a single instance of catalyst cis present in such a state. We introduce a couple of functions on membrane structures that will be useful in the following: Definition 7. Let µbe a membrane structure consisting of dmembranes, labelled with {1, . . . , d}. Given two membranes iand jin µ, we say that the iis contained in jif the surface delimited by the perimeter of iin the Venn diagram representation of µis contained inside the perimeter of j. We say that iis the father of j(and jis a child of i) if the membrane jis contained in i, and no membrane exists that contains jand is contained in i. The partial function father :{1, . . . , d}→{1, . . . , d}returns the father of a membrane i, or is undefined if iis the external membrane. The function children :{1, . . . , d}→P({1, . . . , d})returns the set of children of a membrane. For example, take µ= [1[2[3]3]2[4]4]1; then, father(2) = father(4) = 1, father(3) = 4 and father(1) is undefined; moreover, children(4) = ∅and children(1) = {2,4}. 4 Well-Structured Transition Systems We start by recalling some basic definitions and results from [3], concerning wellstructured transition systems, that will be used in the following. Aquasi-ordering (qo) is a reflexive and transitive relation. Definition 8. Awell-quasi-ordering (wqo) is a quasi-ordering ≤over a set Xsuch that, for any infinite sequence x0, x1, x2, . . . in X, there exist subscripts i < j such that xi≤xj. Decidability of Divergence for Catalytic P Systems 69 Note that, if ≤is a wqo, then any infinite sequence x0, x1, x2, . . . contains an infinite increasing subsequence xi0, xi1, xi2, . . . (with i0< i1< i2< . . .). Transition systems can be formally defined as follows. Definition 9. Atransition system is a structure T S = (S, →), where Sis a set of states and →⊆ S×Sis a set of transitions. We write Succ→(s)to denote the set {s0∈S|s→s0}of immediate successors of s∈S. TS is finitely branching if ∀s∈S:Succ(s)is finite. We restrict to finitely branching transition systems. Well-structured transition systems, defined as follows, provide the key tool to decide properties of computations. Definition 10. Awell-structured transition system (with strong compatibility) is a transition system T S = (S, →), equipped with a quasi-ordering ≤on S, also written T S = (S, →,≤), such that the following two conditions hold: 1. well-quasi-ordering:≤is a well-quasi-ordering, and 2. strong compatibility:≤is (upward) compatible with →, i.e., for all s1≤t1 and all transitions s1→s2, there exists a state t2such that t1→t2and s2≤t2. The following theorem (a special case of a result in [3]) will be used to obtain our decidability result. Theorem 1. Let T S = (S, →,≤)be a finitely branching, well-structured transition system with decidable ≤and computable Succ. The existence of an infinite computation starting from a state s∈Sis decidable. To show that the quasi-ordering relation we will define on P systems is a wellquasi-ordering we need the following results on well-quasi-ordering relations for finite sets and multisets. Proposition 1. Let Sbe a finite set. Then the equality is a wqo over S. Lemma 1. [Dickson] Let Sbe a finite set. The relation ⊆is a wqo over Mfin(S). The following proposition permits to obtain a well-quasi-ordering on the cartesian product of sets equipped with well-quasi-orderings: Proposition 2. Let Sibe sets and ≤i, be wqo over Si, for i= 1, . . . , n. The relation ≤over ×n i=1Siis defined as follows: x≤yiff πi(x)≤iπi(y)for i= 1, . . . , n. The relation ≤is a wqo over ×n i=1Si. 70 N. Busi 5 Decidability of Divergence for Catalytic P Systems In this section we show that the existence of a divergent computation is decidable for the class of catalytic P systems defined in Section 3. The decidability proof is based on the theory of well-structured transition systems [3]: the existence of an infinite computation starting from a given state is decidable for finitely branching transition systems, provided that the set of states can be equipped with a well-quasi-ordering, i.e., a quasi-ordering relation which is compatible with the transition relation and such that each infinite sequence of states admits an increasing subsequence. To this aim, we need a finer definition of the computation of a P system, where a maximal parallelism evolution step is represented as a (maximal) sequence of simple evolution steps, which are obtained by the application of a single evolution rule. After defining such preliminary notions, we propose a well-quasi-ordering that turns out to be compatible with the maximal parallelism evolution step. 5.1 Partial configurations, reaction relation, and maximal parallelism step To represent the states of the system reached after the execution of a non-maximal sequence of simple evolution rules, we introduce the notion of partial configuration of a system. In a partial configuration, the contents of each region is represented by two multisets: •The multiset of active objects contains the objects that were in the region at the beginning of the current maximal parallelism evolution step. These objects can be used by the next simple evolution step. •The multiset of frozen objects contains the objects that have been produced in the region during the current maximal parallelism evolution step. These objects will be available for consumption in the next maximal parallelism evolution step. Definition 11. Let Π= (V, C, µ, w0 1, . . . , w0 d, R1, . . . , Rd, i0)be a catalytic P system. Apartial configuration of Πis a tuple (w1,¯w1), . . . , (wd,¯wd)∈ ×d(V×V). We use ×d i=1(wi,¯wi)to denote the partial configuration above. The set of partial configurations of Πis denoted by ConfΠ. We use γ, γ0, γ1, . . . to range over ConfΠ. In the above definition, w1, . . . , wdrepresent the active multisets, whereas ¯w1, . . . , ¯wdrepresent the frozen multisets. For example, ((aabc, ∅),(abc, ∅)) and ((abc, cb),(c, ∅)) are partial configurations (not necessarily reachable from the initial state) of the P system in Figure 1. Aconfiguration is a partial configuration containing no frozen objects; configurations represent the states reached after the execution of a maximal parallelism computation step. Decidability of Divergence for Catalytic P Systems 71 Definition 12. Let Π= (V, C, µ, w0 1, . . . , w0 d, R1, . . . , Rd, i0)be a catalytic P system. Aconfiguration of Πis a partial configuration ×d i=1(wi,¯wi)satisfying the following: ¯wi=∅for i= 1, . . . , d. The initial configuration of Πis the configuration ×d i=1(w0 i,∅). For example, ((aabc, ∅),(abc, ∅)) is a configuration (actually the initial configuration) of the P system in Figure 1, whereas the partial configuration ((ab, caa), (abc, ∅)) is not a configuration. The size of a partial configuration is the number of active objects contained in the configuration; it will be used to prove the results in the following part of the paper: Definition 13. Let Π= (V, C, µ, w0 1, . . . , w0 d, R1, . . . , Rd, i0)be a catalytic P system and γ=×d i=1(wi,¯wi)be a partial configuration. The size of γis #(γ) = Pd i=1 |wi|. The execution of a simple evolution rule is formalized by the notion of reaction relation, defined as follows: Definition 14. Let Π= (V, C, µ, w0 1, . . . , w0 d, R1, . . . , Rd, i0)be a catalytic P system. The reaction relation 7→ over ConfΠ×ConfΠis defined as follows: ×d i=1(wi,¯wi)7→ ×d i=1(w0 i,¯w0 i)iff there exist k, with 1≤k≤d, an evolution rule u→v∈Rkand a migration string ρ∈ {1, . . . , d}|v|such that •u⊆wk, •w0 k=wk\u, • ∀i: 1 ≤i≤dand i6=kimplies w0 i=wi, • ∀j: 1 ≤j≤ |v|the following holds: – if π2((v)j) = here, then (ρ)j=k, – if π2((v)j) = out, then3(ρ)j=father(k), – if π2((v)j) = in, then4(ρ)j∈children(k), • ∀i, 1≤i≤d: ¯w0 k= ¯wk⊕L1≤j≤|v|,(ρ)j=k(v)j. For example, in the P system of Figure 1 ((aabc, ∅),(abc, ∅)) 7→ ((ab, caa),(abc, ∅)), ((ab, caa),(abc, ∅)) 7→ ((ab, caa),(a, cba)), ((ab, caa),(a, cba)) 67→ ((ab, cab),(a, cba)). Note that the size of a configuration represents an upper bound to the length of the sequences of reactions starting from that configuration. Hence, infinite sequences of reactions are not possible. 3As ρ∈ {1, . . . , d}|v|, this implies that father(k) is defined. 4This implies that children(k) is not empty. 78 N. Busi 6 Conclusion In this paper we showed that the existence of a divergent computation is a decidable property for catalytic P systems. As a byproduct, we also obtain an alternative proof of the nonuniversality of deterministic catalytic P systems, an open problem recently solved by Ibarra and Yen [8, 9]. Actually, the decidability of divergence permits to derive a slightly more general result, i.e., the nonuniversality of the class of P systems which is uniform w.r.t. termination (we say that a P system is uniform w.r.t. termination iff the following property holds: the P systems has a terminating computation iff all of its computations terminate). Finally, as in [4], we consider P systems without priorities associated to the rules. A detailed investigation of the expressivity of various classes of deterministic P systems with priorities has been carried out in [8, 9]. An investigation of the impact of the introduction of priorities on our result is left for future investigation. In the present paper we showed that divergence is a decidable property for catalytic P systems. The technique employed to prove the decidability of divergence is based on the theory of well-structured transition systems: besides universal termination, such a theory permits to analyse other interesting properties, such as, e.g., coverability, boundedness, and eventuality properties [3]. We plan to investigate the possibility to use this theory for the analysis of other (biologically relevant) properties. Acknowledgement: I’m grateful to George P˘aun, Oscar Ibarra and, last but not least, Claudio Zandron for their precious comments and suggestions. References 1. C.S. Calude, G. P˘aun: Computing with Cells and Atoms. Taylor & Francis, London, 2001. 2. J. Dassow, G. P˘aun: On the power of membrane computing. J. Univ. Comput. Sci., 5, 2 (1999). 3. A. Finkel, Ph. Schnoebelen: Well-structured transition systems everywhere! Theoretical Computer Science, 256 (2001), 63–92. 4. R. Freund, L. Kari, M. Oswald, P. Sosik: Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science, 330 (2005). 5. R. Freund, M. Oswald, P. Sosik: Reducing the number of catalysts needed in computationally universal systems without priorities. In Proc. Fifth International Workshop on Descriptional Complexity of Formal Systems, Budapest, 2003. 6. R. Freund, Gh. P˘aun: On deterministic P systems. Manuscript, 2003. (See the Milano webpage [17]). 7. O.H. Ibarra: Some recent results concerning deterministic P systems. In Proc 6th International Workshop on Membrane Computing (WMC6), LNCS 3850, Springer, 2006. Decidability of Divergence for Catalytic P Systems 79 8. O.H. Ibarra, H.-C. Yen: On deterministic catalytic P systems. In Proc. 10th International Conference on Implementation and Application of Automata (CIAA2205), LNCS 3845, Springer, 2005. 9. O.H. Ibarra, H.-C. Yen: Deterministic catalytic systems are not universal. Submitted, 2006. 10. M.L. Minsky: Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, 1967. 11. Gh. P˘aun: Computing with membranes: an introduction. Bull. EATCS, 67 (1999). 12. Gh. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 13. Gh. P˘aun: Membrane Computing. An Introduction. Springer, Berlin, 2002. 14. Gh. P˘aun: Further twenty–six open problems in membrane computing. In Proc. Third Brainstorming Week on Membrane Computing, Sevilla, 2005. 15. P. Sosik: The power of catalysts and priorities in membrane systems. Grammars, 6, 1 (2003). 16. P. Sosik, R. Freund: P Systems without priorities are computationally universal. In Proc. Membrane Computing. International Workshop, WMC-CdeA 2002, LNCS 2597, Springer, 2003. 17. P Systems webpage: http://psystems.disco.unimib.it.