Deterministic Non-cooperative P Systems with Strong Context Conditions

Deterministic Non-cooperative P Systems with Strong Context Conditions Artiom Alhazov1, Rudolf Freund2 1Institute of Mathematics and Computer Science, Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova E-mail: [email protected] 2Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria E-mail: [email protected] Summary. We continue the line of research of deterministic parallel non-cooperative multiset rewriting with control. We here generalize control, i.e., rule applicability context conditions, from promoters and inhibitors checking presence or absence of certain object up to some bound, to regular and even stronger predicates, focusing at predicates over multiplicity of one symbol at a time. 1 Introduction It is known, see [7], that non-cooperative P systems with atomic promoters or atomic inhibitors characterize ET0L, while using either one catalyst, see [6], [3], or promoters or inhibitors of weight 2, see [4], leads to the computational completeness of non-cooperative P systems. A question about the power of deterministic systems was posed in [5], inspired by the fact that all identical objects have the same behavior in the same context. This question was answered in [1]: deterministic non-cooperative P systems have weak behaviour, namely, only accepting finite number sets and their complements, even using generalized context conditions (except the sequential case, when they keep the computational completeness). Generalized context conditions of rule applicability are defined as a list of pairs (pi, Fi), 1 ≤i≤k, applicable to a rule if at least one condition applies, in the following way: pi, called promoter, must be a submultiset of the current configuration (or the contents of the current region), and none of the elements of Fi, called inhibitors, are allowed to be submultisets of the current configuration (or the contents of the current region). A subsequent paper, [2], precisely characterized the power of priorities alone, as well as established how much power of promoters and inhibitors is actually needed to reach NFIN ∪coNFIN. Already in [1] it has been shown that generalized context conditions are equivalent to arbitrary predicates on boundings, i.e., all boolean combinations over conditions < m (and, 2 A. Alhazov, R. Freund hence, also ≥m,> m,≤m, = mand 6=m) for multiplicities of symbols. In other words, generalized context conditions are able to check exactly the multiplicities of symbols up to an arbitrary fixed bound m. In this paper we consider stronger context conditions. 2 Definitions Let Obe a finite alphabet. In this paper we will not distinguish between a multiset, its string representation (having as many occurrences of every symbol as its multiplicity in the multiset, the order in the string being irrelevant), and a vector of multiplicities (assuming that the order of enumeration of symbols from Ois fixed). By O◦we denote the set of all multisets over O. By a strong context in this paper we mean a language of multisets, i.e., a subset of O◦. Let a∈Oand u∈O◦, then a→uis a non-cooperative rule. The rules are applied in the maximally parallel way, which in the case of our interest, i.e., for deterministic non-cooperative P systems, correspond to replacing every occurrence of each symbol aby the corresponding multiset ufrom the right side of the applicable rule (if there is any; no competition between different rules can happen due to the determinism). Let region jof a membrane system contain multiset w. Then rule a→uwith a strong context condition C⊂O◦(written a→u|C) is applicable if and only if |w|a>0 and w∈C. Consider the following examples: •a singleton atomic promoter s∈Ocorresponds to the context +(s) = {w∈ O◦| |w|s>0}; we denote this feature by pro1,1; •a singleton atomic inhibitor s∈Ocorresponds to the complementary context condition: −(s) = {w∈O◦| |w|s= 0}; •a singleton promoter s∈O◦of a higher weight corresponds to the context +(s) = {w∈O◦|s⊆w}; •a singleton inhibitor s∈O◦of a higher weight corresponds to the complementary context condition: −(s) = {w∈O◦|s6⊆ w}; •a (finite) promoter-set S⊂O◦corresponds to the context +(S) = Ss∈S+(s), i.e., at least one promoter must be satisfied; •a (finite) inhibitor-set S⊂O◦corresponds to the complementary −(S) = Ts∈S−(s), i.e., any inhibitor can forbid the rule; •a promoter-set Pand an inhibitor-set Qtogether are called a simple context condition, written (P, Q); it corresponds to the strong context condition +(P)∩ −(Q); •context conditions as considered in [1] and [2] constitute a finite collection of simple context conditions (P1, Q1),· · · ,(Pm, Qm), they correspond to the strong context condition S1≤i≤m(+(Pi)∩ −(Qi)), and were shown to be equivalent to predicates on boundings3; 3the meaning of a promoter-set in [3] is different, but the computational power results are equivalent up to the descriptional complexity parameters such as number of promoters/inhibitors and their weights Deterministic Non-cooperative P Systems with Strong Context Conditions 3 •a bounding bkis an operation on a multiset, for any symbol preserving its multiplicity up to k, or “cropping” it down to kotherwise; a predicate on bounding can be specified by a finite set Mof multisets with multiplicities not exceeding k; it corresponds to a strong context condition {w∈O◦|bk(w)∈ M}, and can express precisely all boolean combinations of conditions |w|a< j, a∈O, 1 ≤j≤k; •a regular strong context condition can be specified by a regular multiset language, or as a Parikh image of a regular string language; e.g., Eq(a, b) = {w∈ O◦| |w|a=|w|b}is an example; we denote the family of such conditions by ctxt(REG); •if a strong context condition only depends on the multiplicities of ksymbols from O(and all other symbols do not affect the applicability), we represent this property by a superscript kof ctxt; for instance, if we denote the symbols mentioned above by S={s1,· · · , sk}, then ctxtk(REG) = {{u∪v|u∈L, v ∈ (O\S)◦} | L⊆S◦, L ∈PsREG}; hence Eq(a, b)∈ctxt2(REG); by ctxt(Eq) we denote being able to compare the multiplicities of two symbols (for different pairs of symbols separately) for being equal, together with the complementary condition; •to stay within Turing computability of the resulting P systems, in this paper we only consider recursive context conditions, i.e., multiset languages with decidable membership, denoted by ctxt(REC); •if a one-symbol strong context condition only depends on the multiplicity of one symbol, it can be specified by a predicate over N; e.g., Sq(a) = {w∈O◦| |w|a=k2, k ≥0}and Sq0(a) = {w∈O◦| |w|a=k2, k ≥1}are examples; hence, Sq,Sq0∈ctxt1(REC); by ctxt(Sq) or ctxt(Sq0) we denote being able to test the multiplicities (of different symbols separately) for squares (including zero or not, respectively), together with the complementary condition. 3 Regular conditions Theorem 1. PsaDOP1(ncoo, ctxt2(REG)) = PsaDOP1(ncoo, ctxt(Eq)) = PsRE. Proof. Consider an arbitrary register machine Mwith mregisters. For each working register i, 1 ≤i≤m, we represent its value by the difference of the multiplicities of associated objects aiand bi. Hence, increment can be performed by producing one copy of ai, decrement can be performed by producing one copy of bi, and zero can be distinguished from non-zero by the following regular conditions: Zi={w∈O◦| |w|ai=|w|bi}=Eq(ai, bi),1≤i≤m, Pi={w∈O◦| |w|ai6=|w|bi}=O◦\Eq(ai, bi),1≤i≤m, We construct the following P system: Π= (O, Σ, µ = [ ]1, w1=q0, R1),where 4 A. Alhazov, R. Freund O=Q∪T∪ {ai, bi|1≤i≤m}, Σ⊆ {ai|1≤i≤m}, R1={q→aiq0|q: (ADD(i), q0)∈P} ∪ {q→biq0|Pi, q →q00|Zi|q: (SUB(i), q0, q00)∈P}.  If only regular conditions over one symbol are allowed, then we expect the power of such P systems to be much more limited. 4 Stronger Conditions Consider one-symbol context conditions that are even stronger than regular. It is expected that, with recursively enumerable conditions over one number we get something like NRE ∪coNRE, so we look at intermediate cases. We look at ways of obtaining RE by encoding a number by a multiplicity of one object, say, ai, in such a way that increment and decrement are reasonably simple to perform by non-removable objects. We propose the following encoding: “ignoring the greatest square”, i.e., number n=k2+tencodes tif 0 ≤t < 2k+ 1. In this way, zero-test becomes a test whether the encoding number is a perfect square. Increment is performed as increment of the encoding number, followed by addition of 2k+ 1 if the next perfect square, i.e., (k+ 1)2, is reached. Decrement can thus be done by adding 2kto the encoding number. The value kcan be stored as the multiplicity of another non-removable object, say, bi, whose multiplicity should be incremented each time the encoding number is increased by 2kor by 2k+ 1. Putting it all together, the following construction is obtained: Zi={w∈O◦| |w|ai=k2, k ≥0}=Sq(ai), Pi=O◦\Zi,1≤i≤m, We construct the following P system: Π= (O, Σ, µ = [ ]1, w1=q0, R1),where O=Q∪T∪ {ai, bi|1≤i≤m}, Σ⊆ {ai|1≤i≤m}, R1={q→ai˜q, ˜q→q0|Pi,˜q→ˆq|Zi,ˆq→aibiq0, bi→aiaibi|ˆq |q: (ADD(i), q0)∈P} ∪ {q→q00|Zi, q →ˆq|Pi,ˆq→biq0, bi→aiaibi|ˆq |q: (SUB(i), q0, q00)∈P}. Yet there is a major drawback of this result established above in comparison with the result from Theorem 1, as the input has to be encoded: given a number nifor input register i, we have to compute numbers ni+k2 iand ki, such that k2 i≤ ni≤k2 i+ 2ki. But this is an algorithm which is not difficult to be implemented; Deterministic Non-cooperative P Systems with Strong Context Conditions 5 also our context condition for testing a number to be a perfect square does not require a difficult algorithm. Hence, we have just shown the following result, where the index wa instead of a in PswaDOP1(ncoo, pro1,1, ctxt(Sq)) indicates weak computational completeness as for having to encode the input: Theorem 2. PswaDOP1(ncoo, ctxt1(REC)) = PsPswaDOP1(ncoo, pro1,1, ctxt(Sq)) = P sRE. Adding rules ai→λ|qf,bi→λ|qfand qf→λfor 1 ≤i≤m, where qfis the final state of the simulated register machines, we even obtain the clean result, i.e., halting without additional objects, still preserving determinism. We can strengthen the claim of Theorem 2 by showing strong computational completeness (in the sense of deterministic acceptance and even deterministic way of computing functions). Without restricting the power of register machines, we assume that in the simulated register machine, the output registers are never decremented. Then, for the output registers, we replace the simulation of each increment instructions with a single rule q→aiq0, where q: (ADD(i), q0)∈Pand iis an output register. In this way, the output will be produced without encoding. It remains to show that P systems with strong context conditions over one symbol can simulate register machines where also the input is not encoded. We use the following idea. To represent the input Nof a register in the way the P system constructed in the proof of Theorem 2 needs it, we first describe how to get two numbers xNand yNsuch that Nis a function of xNand yN, and, moreover, by computing these two numbers from N, we get their representation in the form we need them as for the P system constructed in Theorem 2. First we explain the algorithm how to obtain xNand yN: Starting with N represented by Ncopies of an object cN, the multiplicity of these input objects is incremented until it becomes a perfect square (counting the increments, thus finally obtaining xN), and then incrementing it (again counting the increments, thus finally obtaining yN) until it again becomes a perfect square. From these two numbers xNand yNwe can regain Nby the formula computed in the following: Given input N, the next perfect squares are k2 N=N+xN(xN≥0) and (kN+ 1)2=N+xN+yN, then yN= 2kN+ 1, so kN= (yN−1)/2, and N= k2 N−xN= (yN−1)2/4−xN. Of course, the function f(xN, yN)=(yN−1)2/4−xN decoding Nfrom xNand yNcan be implemented by a register machine and simulated by a P system as described in Theorem 2. In the following example we specify more formally the precomputing block mentioned above. Example 1. Encoding the input number N. Let the input Nbe given as a multiplicity of symbol ci, and we want to obtain values xNand yNdescribed above in auxiliary registers jand l, respectively, but represented already in the way we need their contents xNand yNimplemented 6 A. Alhazov, R. Freund with the corresponding number of symbols ajand bjas well as aland bl. We also use an additional starting object siand in sum the following rules: si→ciaj˜si|P0 i,˜si→s0|Pj,˜si→ˆsi|Zj,ˆsi→ajbjs0, bj→ajajbj|ˆsi, si→citi|Z0 i, ti→cial˜ ti|P0 i,˜ ti→t0 i|Pl,˜ ti→ˆ ti|Zl,ˆ ti→albkt0, bk→alalbl|ˆ ti, ti→q(i) 0|Z0 i,where Z0 i={w∈O◦| |w|ci=k2, k ≥0}=Sq(ci), P0 i=O◦\Z0 i. Essentially, the rules above are exactly like increment instructions from Theorem 2, tracking how many times the multiplicity of the input object cihas to be incremented to reach a perfect square and the next perfect square. In the next phase of the encoding procedure, the P system should simulate a register machine which starts in state q(i) 0and computes the function f(xN, yN) = (yN−1)2/4−xN, given xNin register jand yNin register l, producing the result (i.e., the value Nof the input register ito be represented) in register i, represented by symbols aiand biand thus in a suitable way to be the input for the P system constructed in Theorem 2. Theorem 3. PsaDOP1(ncoo, ctxt1(REC)) = PsaDOP1(ncoo, pro1,1, ctxt(Sq)) = PsRE. Proof. Clearly, any input vector can be processed accordingly in the way described in Example 1, and then a simulation of the register machine on these inputs as outlined in Theorem 2 completes the explanation of the following result.  The construction in Theorem 3 may be adjusted so that we never rely on multiplicities of symbols aibeing zero, i.e., when starting with a value 0 in a register, we start with encoding it by 1. Moreover, testing for the appearance of a symbol which never appears more than once (which we needed for the symbols corresponding to the states of the simulated register machine) corresponds with testing for a perfect square of positive integers. Hence, for each checking set from Sq0(or its complement) or each singleton promoter used in the previous construction we can use a set from Sq0(or its complement) only. In sum we get: Corollary 1. PsaDOP1(ncoo, ctxt(Sq0)) = PsRE. 5 Conclusions It was known that generalized context conditions are equivalent to predicates on boundings, and that using them in deterministic maximally parallel noncooperative P systems still leaves their accepting power as low as NF IN ∪ coNFIN. We have shown that regular context conditions yield computational Deterministic Non-cooperative P Systems with Strong Context Conditions 7 completeness of deterministic maximally parallel non-cooperative P systems, expecting that the power of P systems with regular context conditions over one symbol is still quite limited. However, we have shown computational completeness using a simple stronger one-symbol context condition, namely, {w∈O◦| |w|ai= k2, k ≥0}. References 1. A. Alhazov, R. Freund: Asynchronous and Maximally Parallel Deterministic Controlled Non-Cooperative P Systems Characterize N F I N and coN F I N . In: E. Csuhaj-Varj´u, M. Gheorghe, G. Rozenberg, A. Salomaa, Gy. Vaszil: Membrane Computing – 13th International Conference, CMC13, Budapest, Revised Selected Papers, Lecture Notes in Computer Science 7762, Springer, 2013, 101–111. 2. A. Alhazov, R. Freund: Priorities, Promoters and Inhibitors in Deterministic Non- Cooperative P Systems. In: M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sos´ık, C. Zandron: Membrane Computing - 15th International Conference, CMC 2014, Prague, Revised Selected Papers, Lecture Notes in Computer Science 8961, Springer, 2014, 86–98. 3. A. Alhazov, R. Freund, S. Verlan: Promoters and Inhibitors in Purely Catalytic P Systems. In: M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sos´ık, C. Zandron: Membrane Computing - 15th International Conference, CMC 2014, Prague, Revised Selected Papers, Lecture Notes in Computer Science 8961, Springer, 2014, 126–138. 4. A. Alhazov, D. Sburlan: Ultimately Confluent Rewriting Systems. Parallel Multiset- Rewriting with Permitting or Forbidding Contexts. In: G. Mauri, Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg, A. Salomaa: Membrane Computing, 5th International Workshop, WMC 2004, Milan, Revised Selected and Invited Papers, Lecture Notes in Computer Science 3365, Springer, 2005, 178–189. 5. M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Research Frontiers of Membrane Computing: Open Problems and Research Topics. International Journal of Foundations of Computer Science 24 (5), 2013, 547–624. 6. M. Ionescu, D. Sburlan: On P Systems with Promoters/Inhibitors. Journal of Universal Computer Science 10 (5), 2004, 581–599. 7. D. Sburlan: Further Results on P Systems with Promoters/Inhibitors. International Journal of Foundations of Computer Science 17 (1), 2006, 205–221.