Purely Catalytic P Systems over Integers and Their Generative Power

Purely Catalytic P Systems over Integers and Their Generative Power Artiom Alhazov1, Omar Belingheri2, Rudolf Freund3, Sergiu Ivanov4, Antonio E. Porreca2, and Claudio Zandron2 1Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: [email protected] 2Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy E-mail: {o.belingheri@campus,porreca@disco,zandron@disco}.unimib.it 3Faculty of Informatics, TU Wien Favoritenstraße 9-11, 1040 Vienna, Austria E-mail: [email protected] 4Universit´e Paris Est, France E-mail: [email protected] Summary. We further investigate the computing power of the recently introduced P systems with Z-multisets (also known as hybrid sets) as generative devices. These systems apply catalytic rules in the maximally parallel way, even consuming absent non-catalysts, effectively generating vectors of arbitrary (not just non-negative) integers. The rules may be made inapplicable only by dissolution rules. However, this releases the catalysts into the immediately outer region, where new rules might become applicable to them. We discuss the generative power of this model. Finally, we consider the variant with mobile catalysts. 1 Introduction Membrane systems (cell-like, with symbol-objects) have traditionally been viewed as collections of hierarchically arranged multiset processors [12]. In the list of open problems disseminated in 2015 [11], Gheorghe P˘aun suggested going beyond the traditional setting where symbol multiplicities in multisets are restricted to non-negative integers. One suggested approach [6] defines generalized multisets as taking multiplicities from arbitrary finitely generated, totally ordered commutative groups. In work [3], a different approach is taken: only catalytic rules are allowed, and the applicability of a rule only depends on presence of the corresponding catalyst 16 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron in the given region. Consuming an absent non-catalyst makes its multiplicity negative. While in [3] it was already established that such model is not universal, we found it interesting to investigate its generative power more precisely. Since the number of catalysts remains finite and does not change throughout the computation, this induces a finite set of “rule teams” which can be applied in parallel in one step. The virtual absence of applicability conditions and the finiteness of the “teams” hints at the possibility of seeing them as integer vectors; in this case the P system itself can be seen as evolving by sequentially adding such vectors (possibly having negative components) to the contents of its membranes. Paper [2] compares this general model to vector addition systems [5, 9] (adapted to allow negative vector components [8]) and blind register machines [7]. Here we return to the particular model from [3], discussing the lower bound of its generative power and giving some results on the variant with target indications. 2 Preliminaries The reader is assumed to be familiar with the basic notions of formal languages and membrane computing; see [13] for a comprehensive introduction to both. We only remark that, as common in membrane computing, multisets in O◦=NOare represented by strings in O∗, keeping in mind that the order of symbols is not relevant. 2.1 Extending Multisets To represent also negative multiplicities, multisets must be extended. A Z-multiset, allowing integer multiplicities (called a hybrid set in [4]) would be from ZO; it can be represented by a string in (O∪O−)∗, where O−={a−|a∈O}is a set of symbols that represents objects in multiplicity “negative one”. Note that, as opposed to P systems with matter-antimatter [1], symbol a−here is not an actual object, but simply a convenient way to represent a deficit of a, and the actual multiplicity of arepresented by a string wis |w|a− |w|a−. We also do not distinguish between notations a−kand (a−)k. The superscript −can be used as a morphism, producing a multiset with opposite multiplicities, e.g., (ak)−represents the same Z-multiset as the one in the previous sentence. As the strings here are only used to represent [Z-] multisets, we may write an equality sign between the strings representing the same [Z-] multiset. For conciseness, let us use the notation O•= (O∪O−)∗. Finally, since it will be always clear from the context, we may call an element of O•“multiset”, omitting the word “representing”. Assuming an order is fixed on O, for u∈O•, vector (|u|a− |u|a−)a∈Ois denoted by ψO(u); the subscript Omay be omitted when it is clear from the context. This vector is called the Parihkh image of u. Purely Catalytic P Systems over Integers and Their Generative Power 17 2.2 Linear Sets The linear set generated by a set of vectors A={ai|1≤i≤d} ⊂ Znand an offset a0∈Znis defined as follows: hA, a0iN=a0+Xd i=1 kiai|ki∈N,1≤i≤d. If the offset a0is the zero vector, we will call the corresponding linear set homogeneous; we also will use a short notation hAiN=hA, 0iN. We use the notation ZnLINN=hA, a0iN|A∈(Zn)d,a0∈Z, m ∈N, to refer to the class of all linear sets. Semilinear sets are defined as finite unions of linear sets. We use the notations ZnSLINNto refer to the classes of semilinear sets of n-dimensional vectors. In case no restriction is imposed on the dimension, nis replaced by ∗. We may omit nif n= 1. A finite union of linear sets which only differ in the starting vectors is called uniform semilinear: ZnSLINU N=Sb∈BhA, biN|A∈(Zn)d, B ∈(Zn)k, d, k ∈N =nnb+Pd i=1 kiai|ki∈N,1≤i≤do|A∈(Zn)d, B ∈(Zn)k, d, k ∈No. Let us denote these sets by hA, BiN. 3 Purely Catalytic P Systems over Integers In purely catalytic P systems over integers the set of objects is a disjoint union of catalysts Cand the regular objects O. The regular objects are allowed to have any integer multiplicity, while the catalysts are only allowed to appear in a nonnegative number of copies. The rules can be of the two following types: •catalytic rules: cu →cv, where c∈Cand u, v ∈O∗; •catalytic rules with dissolution:cu →cvδ, where c∈C,u, v ∈O∗, and δ6∈ C∪Ois the symbol indicating membrane dissolution. The rules applied in parallel cannot involve more catalysts than available in the system; the multiplicities of regular objects, on the other hand, do not influence the applicability of rules. An application of a rule cu →cv in a region containing cw (c∈C,u, v ∈O∗,w∈O•produces cw(cu)−cv =cwv(u−), or, in terms of vectors, ignoring the catalyst, vector ψ(w) + ψ(v)−ψ(u) is represented by the contents of that region after the rule has been applied. An application of a rule cu →cvδ produces the same effect, and then dissolves the enclosing membrane, moving the contents of the dissolved membrane into the parent membrane. Purely catalytic P systems over integers evolve under the maximally parallel semantics, so each catalyst enters exactly one rule (non-deterministically chosen), unless the given region has no rules associated with this catalyst. By 18 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron ZdOZPm(pcatk, δ) we denote the family of sets of d-dimensional vectors of integers generated by purely catalytic P systems over integers with dissolution, at most mmembranes and at most kcatalysts. If any of parameters d, m, k is unbounded, it is replaced by ∗in the notation. We also use notations for extended features (listed in parentheses in the notation of the sets of Z-vectors generated by the corresponding families of P systems). Target indications, denoted by tar, allow the non-catalysts to be sent to a different membrane. In the right side of the rules, sending object ais written by (a, tar), where tar ∈ {out}∪{inj|1≤j≤m};jhere is a label of immediately inner membrane. In this paper, we may write tarnin the notation of a set of Z-vectors generated by a family of P systems; this generalization reflects the possibility to assign targets even to negative multiplicites of objects. Another feature is mobile catalysts [10], i.e., targets may also be associated to the catalysts, and thus the catalysts move across the membrane structure; we denote this feature by mpcatksince the systems we consider are purely catalytic. We use the plus sign between the features of catalytic mobility and dissolution when it is allowed for the same rule to move a catalyst and to dissolve the membrane currently containing it. 4 Results 4.1 Simplifications and Observations First, we would like to explicitly allow rules of the form c→cx, (c∈C,x∈O•), i.e., the multiset of regular objects in the left side being empty. This does not change the model, since any Z-multiset xcan be written as u(v−), u, v ∈O∗, and, fixing some a∈O,c→cx is equivalent to cau →av. Moreover, any rule cu →cv is equivalent to c→cu(v−), so it suffices to only consider rules of types c→cx and c→cxδ (c∈C,x∈O•). Second, notice that it is enough to start with a single catalyst in any region, because it can perform the role of any number of catalysts, and if multiple catalysts are initially in the same region, they will always stay in the same region (possibly, merged with others). Indeed, take an arbitrary region of an arbitrary purely catalytic P system over integers, say, it has catalysts ci, 1 ≤i≤d, and each catalyst cihas associated rules ci→cixi,j, 1 ≤j≤ni, where xi,j ∈O•∪O•δ. Note that if none of the catalysts has associated rules, then they are equivalent to a single catalyst with no associated rules, so in the following we assume the contrary. If some catalyst cihas no associated rules, it is then equivalent to it having associated a single rule ci→ci, i.e., xi,1=λand ni= 1, so in the following we assume ni≥1 for 1 ≤i≤d. We can now replace all these catalysts by a single catalyst chaving associated the following set of rules: {c→cx1,j1· · · xd,jd|1≤ji≤ni,1≤i≤d}. Purely Catalytic P Systems over Integers and Their Generative Power 19 On the other side, no catalyst in some region is equivalent to one catalyst with no associated rules. Therefore, without restricting the generality, in the following we assume that in the initial configuration of an arbitrary purely catalytic P system over integers, each membrane region i, 1 ≤i≤m, contains precisely one catalyst, and we can call it ci. Third, notice that no information enters membranes, so the outer regions cannot affect the inner regions in any way. Hence, if the output region i0is not the skin, then only the membrane substructure inside i0, including i0is relevant for the result, and other membranes are irrelevant and may be removed without affecting the result, making i0the skin (unless some rule in some removed membrane had applicable rules, but could never be dissolved, in which case the generated set of vectors is empty, which is a degenerate case). So in the following, we assume that the output region is always the skin. Fourth, every elementary membrane having no rules associated to the catalysts available there may be removed from the system without affecting the result (unless it is the output membrane, in which case a singleton is generated, which is a degenerate case), so in the following we assume that each elementary membrane has some applicable rules. Clearly, the P system will not reach the halting until this membrane is dissolved. Consider this reasoning starting from the elementary membranes outside, by induction. Take any non-elementary membrane iwhich becomes elementary during a computation. Assume iis not dissolved (i.e., it has no rules associated to any of the catalysts that were placed within the membrane substructure inside i, including i), but it is not the output membrane. Then all the computation in the membrane substructure inside i, including i, does not contribute to the result, and can be removed from the system without affecting the result. As a summary of the fourth observation, without restricting the generality (except, possibly the degenerate cases generating the empty set or some singleton), we may assume that any purely catalytic P system over integers has applicable rules associated to all elementary membranes, and all membranes except the skin must be dissolved at some moment during the computation. Finally, for every region except the skin, a catalyst ciwithout associated rules is equivalent to a catalyst with a rule ci→ci. Hence, without restricting the generality, we may assume that the catalysts are never idle before the halting is reached. Clearly, (excluding the degenerate case generating the empty set), the skin should have no rules associated to any catalyst of the system. We would like to note that even without pruning the membrane structure by removing membrane substructures not contributing to the result, the membrane structure obtained at halting (if at all reachable) is unique. We recall that in [2], the following generalization approach is taken: There is a finite number of reachable membrane structures. These could be used as states of a sequential P system, which may be obtained, separately for each membrane structure, by combining the behavior of all catalysts in all regions of the P system. Indeed, having fixed a reachable membrane structure, we know which membranes 20 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron have been dissolved, and thus the resulting location of each catalyst. Then, for each catalyst, associated rules in its current location are considered and combined, similarly to the second observation above, but globally. Having obtained a sequential system, the catalyst is no longer needed. Then, in [2] it was shown that such a generalization is nothing else but a sequential blind vector addition system with states, and it was claimed that it characterizes precisely the family of all semilinear vectors of integers. Indeed, in this way any purely catalytic P system over integers can be substituted by a sequential blind vector addition system with states, so the upper bound of the family of all semilinear sets of vectors of integers, or, equivalently, the family of all integer vector sets, generated by blind register machines, holds. However, the reverse is not necessarily true, i.e., it does not follow that for any sequential blind vector addition system with states there would exist an equivalent purely catalytic P system over integers. Another result in [2] has been obtained for integer vector addition P systems, namely Theorem 5. That model has been shown to characterize exactly the uniform semilinear sets. However, since in the model of integer vector addition P systems, as opposed to purely catalytic P systems over integers, there is no concept of a catalyst, dissolving a membrane only disables rules of that region, without enabling rules that, in purely catalytic P systems over integers, are contained in the parent region and associated to the catalysts that were in the dissolved region. Hence, the characterization from Theorem 5 of [2] has no direct implication on the power of purely catalytic P systems over integers. Therefore, at this point in the present paper we would like to definitely deviate into the particularities of how dissolution affects the computation, and the lower bounds. 4.2 Generative Power We recall that we discuss the family of integer vector sets generated by purely catalytic P systems over integers, with the usual halting condition. Since the output region cannot be dissolved by definition and any other applicable rule can never be stopped, single-membrane purely catalytic P systems over integers are degenerate: ZdOZP1(pcat∗, δ) = {∅} ∪ {{v} | v∈Zd}. For simplicity, we will not mention these degenerate cases while considering multiple membranes. With two membranes, a characterization is still straightforward: ZdOZP2(pcat∗, δ) = ZdSLINU N. Indeed, let Abe the finite set of vectors corresponding to the non-dissolving rules in the elementary membranes, and let Bbe the finite set of sums of two vectors: Purely Catalytic P Systems over Integers and Their Generative Power 21 the one corresponding to the initial configuration and vectors corresponding to the dissolving rules in the elementary membrane; the skin should have no rules. If the catalyst in the elementary membrane is c2, then the correspondence mentioned above is c2→c2x↔ψ(x), and similarly with dissolution. An arbitrary computation of a P system consists of an arbitrary number of applications of non-dissolving rules and one application of a dissolving rule. Hence, the resulting vector sums up from the “initial” vector, one arbitrary “dissolving” vector, and an arbitrary linear combination of “non-dissolving” vectors. It is worth noting that, by a similar reasoning, for a P system with multiple membranes, if the chronological order of dissolving membranes is fixed, the result is still ZdSLINU N. Indeed, each combination of rules (one for each catalyst) yields one vector, so all such possible combinations of non-dissolving rules yield a finite set of vectors, and multiple non-dissolving steps yield a linear set generated by these vectors. Thus, over the whole computation the result sums up from the initial configuration, a finite number of dissolution vectors, and a finite number of linear sets corresponding to the membrane structures reached during that computation. Since the total number of chronological orders of dissolving membranes is bounded, the known result already follows: ZdOZP∗(pcat∗, δ)⊆ZdSLINN. Even with three membranes, in case two of them are elementary, the power of such purely catalytic P systems over integers is still ZdSLINU N, but for a different reason: each elementary membrane contributes with its uniform semilinear set, and a sum of two uniform semilinear sets is still uniform semilinear. Let us now examine a P system with three nested membranes – the minimal number to obtain a set which is not in ZdSLINU N. Let the vector obtained by joining the initial contents of all membranes be a, the set of non-dissolving vectors of the elementary membrane be A3, the set of dissolving vectors of the elementary membrane be B3, the sets of non-dissolving and dissolving vectors in the middle membrane associated to catalyst c2are A2and B2, and the similar sets associated to catalyst c3(which will arrive from the elementary membrane) are Aand B. Let us see what the resulting vector set is built from, besides a. A non-dissolving computation in three membranes adds at each step (an element of) A3to the elementary membrane and (an element of) A2to the middle membrane. Eventually all objects will arrive to the skin, so the three-membrane phase of the computation will contribute by (an arbitrary element of) hA2+A3iN. Then there are two possibilities. If membrane 2 is dissolved first, then the system continues computing by only applying the rules in membrane 3, and eventually dissolving membrane 3, yielding B2+hA3iN+B3. However, if membrane 3 is dissolved first, then both catalysts are active in membrane 2, eventually dissolving it, yielding B3+hA2+AiN+ (B2+A∪A2+B∪A+B). The expression in parentheses corresponds to applying at least one dissolving rule. Therefore, the set of integer vectors generated by such a purely catalytic P system over integers with three nested membranes is 22 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron M=a+B3+hA2+A3iN+B2+hA3iN∪ hA2+AiN+B2+A∪A2+B∪B2+B, and the power of all three-membrane purely catalytic P systems over integers, noting that the power of the nested case subsumes the power of the case with two elementary membranes, is ZdOZP1(pcat∗, δ) = {M|a∈Zd, A2, A3, B2, B3, A, B ∈F IN(Zd)}, where Mis the expression above. Unfortunately, it is not obvious what can be simplified in it, except B3can subsume a. So we try to analyze it in details, possibly going into particular cases. All terms in the expression Mare bounded except three: hA3+A2iN,hA3iN and hA+A2iN. These terms are not independent, even though A2,A3and Aare three independent finite sets of vectors. It is, however, possible to separate them in a particular case when |A3|= 1, choosing A2=−A3and A=C−A2. Since A3is a singleton, the identity A3−A3={0}holds, so the three unbounded terms become h{0}iN,hA3iNand hCiN, so we are getting close to obtaining a union of two particular linear (or even uniform semilinear) sets with different base vectors. Indeed, if we choose a=0,B3={0},B2={0},B={0}and A3={e}, expression Msimplifies to h{e}iN∪hCiN+(C+{e}∪{0}), which can be rewritten as h{e}iN∪ hCiN∪ {e} hCiN. Alternatively, to avoid dealing with the union of three cases when membrane 2 is divided last, if we choose B2=A2and B=A, then the last parenthesis in the general expression of set Mbecomes simply A2+A=C. Choosing a=0, B3={0}, and A3={e}, expression Msimplifies to h{e}iN− {e}∪hCiN+C. Since 0∈ h{e}iN− {e}and hCiN+C∪ {0}=hCiN, in this case we can rewrite Mto −{e} ∪ h{e}iN∪ hCiN, which is a union of any two homogeneous linear sets, such that the first one has only one generator, united with the opposite vector of that generator. Hence, ZdOZPn(cat, δ))ZdSLINU N, n ≥3. What if B=∅, i.e., catalyst c3has no associated dissolution rules in region 2? Then the general expression of set Mis immediately simplified to M=a+B2+B3+hA2+A3iN+ (hA3iN∪ hA2+AiN+A), and in our case of A3={e},A2=−{e}and A=C+{e},Mbecomes a+B2+B3+ (h{e}iN∪ hCiN+C+{e}), and choosing a+B2+B3={−e}, and noticing that C0 times is covered by e0 times and hCiN+C∪{0}=hCiN, we simplify Mto {−e} ∪h{e}iN∪ hCiN, i.e., an “almost clean union” we already obtained before. Finally, we notice that we can equivalently write it as h{e},−eiN∪ hCiN. Continuing the current approach with more membranes would only result in more cases. Purely Catalytic P Systems over Integers and Their Generative Power 23 4.3 Communication We would like to remark that adding target indications to the regular objects should not increase the power of purely catalytic P systems over integers. Indeed, looking at a purely catalytic P system over integers, it is easily decidable which membranes will eventually be dissolved. Hence, the only question is whether the contents of a region specified by target, after possible dissolutions, will be in the output. There is no need to examine the future of a moved regular object, since the resources in purely catalytic P systems over integers are unbounded, and we can view this copy of a moved object as staying in that region until the end of the computation. However, if also the catalysts are allowed to have target indications associated, it does make a difference. We claim the following characterizations. ZdOZP∗(mpcatk, tarn) = ZdSLINN, k ≥1, ZdOZP∗(mpcatk+δ) = ZdSLINN, k ≥1, ZdOZP∗(mpcat∗, δ) = ZdSLINN, The upper bound in either case is easy to see because the number of possible arrangements of catalysts across the given membrane structure (and any possible structures obtained from it by membrane dissolutions) is bounded. Hence, purely catalytic P systems over integers with mobile catalysts are still not more powerful than blind vector-addition systems with states, which characterize Z∗SLINN, see [2]. We now proceed to ⊇inclusions. Consider an arbitrary semilinear set S1≤i≤mhAi, biiN, where for each i, 1 ≤i≤ m,Aiis a finite set, Ai∪ {bi} ⊆ Zd. We construct the following purely catalytic P system over integers Π1= (O, C, µ, w1,· · · , w2m+1, R1,· · · , R2m+1, i0= 1) where O={ai|1≤i≤d}, C ={c}, µ= [ [ [ ]m+2 ]2· · · [ [ ]2m+1 ]m+1 ]1, w1=c, wi+1 =λ, 1≥i≥2m, R1={c→(c, ini+1)vi|1≤i≤m, ψ(vi) = bi}, Ri+1 ={c→c(v, out)|ψ(v)∈Ai}∪{c→(c, inm+i+1)},1≤i≤m, Rm+i+1 =∅,1≤i≤m. The work of Π1consists of a non-deterministic choice of i-th linear set to generate, by moving catalyst cinto membrane i+ 1 and producing bi. After sending to the skin an arbitrary combination of vectors from Ai, the catalyst enters membrane m+i+ 1 and the system halts. The system Π2is obtained from Π1by replacing the sets Ri+1 of rules, 1 ≤ i≤m, by {c→cv |ψ(v)∈Ai}∪{c→(c, inm+i+1)δ}.