Priorities, Promoters and Inhibitors in Deterministic Non-Cooperative P Systems

Priorities, Promoters and Inhibitors in Deterministic Non-Cooperative P Systems Artiom Alhazov1, Rudolf Freund2 1Institute of Mathematics and Computer Science Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova [email protected] 2Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria [email protected] Summary. Membrane systems (with symbol objects) are distributed controlled multiset processing systems. Non-cooperative P systems with either promoters or inhibitors (of weight not restricted to one) are known to be computationally complete. Since recently, it is known that the power of the deterministic subclass of such systems is subregular. We present new results on the weight of promoters and inhibitors, as well as for characterizing the systems with priorities only. 1 Introduction The most famous membrane computing model where determinism is a criterion of universality versus decidability is the model of catalytic P systems, see [3] and [6]. It is also known that non-cooperative rewriting P systems with either promoters or inhibitors are computationally complete, [2]. Moreover, the proof satisfies some additional properties: •Either promoters of weight 2 or inhibitors of weight 2 are enough. •The system is non-deterministic, but it restores the previous configuration if the guess is wrong, which leads to correct simulations with probability 1. Recently, in [1] it was shown that the computational completeness cannot be achieved by deterministic non-cooperative systems with promoters, inhibitors and priorities (in maximally parallel or asynchronous mode, unlike the sequential mode), and characterizations of the corresponding classes were obtained: 28 A. Alhazov, R. Freund NFIN ∪coNFIN =NdetaOPasyn 1(ncoo, pro1,∗, inh1,∗) =NdetaOPmaxpar 1(ncoo, pro1,∗) =NdetaOPmaxpar 1(ncoo, inh1,∗) =NdetaOPasyn 1(ncoo, (pro∗,∗, inh∗,∗)∗, pri) =NdetaOPmaxpar 1(ncoo, (pro∗,∗, inh∗,∗)∗, pri),but NRE =NdetaOP sequ 1(ncoo, pro1,1, inh1,1). A few interesting questions have been left open. For instance, what is the power of P systems, e.g., in the maximally parallel mode, when we only use priorities, or when we restrict the weight of the promoting/inhibiting multisets. These are the questions we address in this paper. 2 Definitions An alphabet is a finite non-empty set Vof abstract symbols. The free monoid generated by Vunder the operation of concatenation is denoted by V∗; the empty string is denoted by λ, and V∗\ {λ}is denoted by V+. The set of non-negative integers is denoted by N; a set Sof non-negative integers is called co-finite if N\S is finite. The family of all finite (co-finite) sets of non-negative integers is denoted by NF IN (coNFIN, respectively). The family of all recursively enumerable sets of non-negative integers is denoted by NRE. In the following, we will use ⊆both for the subset as well as the submultiset relation. Since flattening the membrane structure of a membrane system preserves both determinism and the model, in the following we restrict ourselves to consider membrane systems as one-region multiset rewriting systems. A(one-region) membrane system (P system) is a tuple Π= (O, Σ, w, R′), where Ois a finite alphabet, Σ⊆Ois the input sub-alphabet, w∈O∗is a string representing the initial multiset, and R′is a set of rules of the form r:u→v, u∈O+,v∈O∗. A configuration of the system Πis represented by a multiset of objects from O contained in the region, the set of all configurations over Ois denoted by C(O). A rule r:u→vis applicable if the current configuration contains the multiset specified by u. Furthermore, applicability may be controlled by context conditions, specified by pairs of sets of multisets. Definition 1. Let Pi,Qibe (finite) sets of multisets over O,1≤i≤m. A rule with context conditions (r, (P1, Q1),· · · ,(Pm, Qm)) is applicable to a configuration Cif ris applicable, and there exists some j∈ {1,· · · , m}for which •there exists some p∈Pjsuch that p⊆Cand •q⊆ Cfor all q∈Qj. Controls in Deterministic Non-Cooperative P Systems 29 In words, context conditions are satisfied if there exists a pair of sets of multisets (called promoter set and inhibitor set, respectively) such that at least one multiset in the promoter set is a submultiset of the current configuration, and no multiset in the inhibitor set is a submultiset of the current configuration. Definition 2. AP system with context conditions and priorities on the rules is a construct Π= (O, Σ, w, R′, R, >), where (O, Σ, w, R′)is a (one-region) P system as defined above, Ris a set of rules with context conditions and >is a priority relation on the rules in R; if rule r′has priority over rule r, denoted by r′> r, then rcannot be applied if r′is applicable. Throughout the paper, we will use the word control to mean that at least one of these features is allowed (context conditions or promoters or inhibitors only and eventually priorities). In the sequential mode (sequ), a computation step consists in the nondeterministic application of one applicable rule r, replacing its left-hand side (lhs (r)) with its right-hand side (rhs (r)). In the maximally parallel mode (maxpar), a multiset of applicable rules may be chosen non-deterministically to be applied in parallel to the underlying configuration to disjoint submultisets, possibly leaving some objects idle, under the condition that no further applicable rule can be added to that multiset (i.e., no supermultiset of the chosen multiset is applicable to the same configuration). Maximal parallelism is the most common computation mode in membrane computing, see also Definition 4.8 in [5]. In the asynchronuous mode (asyn), any positive number of applicable rules may be chosen non-deterministically to be applied in parallel to the underlying configuration, to disjoint submultisets. The computation step between two configurations Cand C′is denoted by C→C′, thus yielding the binary relation ⇒:C(O)×C(O). A computation halts when there are no rules applicable to the current configuration (halting configuration) in the corresponding mode. The computation of a generating P system starts with w, and its result is |x| if it halts, an accepting system starts with wx,x∈Σ∗, and we say that |x|is its results – is accepted – if it halts. The set of numbers generated/accepted by a P system working in the mode αis the set of results of its computations for all x∈Σ∗and denoted by Nα g(Π) and Nα a(Π), respectively. The family of sets of numbers generated/accepted by a family of (one-region) P systems with context conditions and priorities on the rules with rules of type βworking in the mode αis denoted by NδOPα 1(β, (prok,l, inhk′,l′)d, pri)with δ=gfor the generating and δ=afor the accepting case; ddenotes the maximal number min the rules with context conditions (r, (P1, Q1),· · · ,(Pm, Qm)); kand k′denote the maximum number of promoters/inhibitors in the Piand Qi, respectively; land l′indicate the maximum of weights of promotors and inhibitors, respectively. If any of these numbers k,k′,l,l′is not bounded, we replace it by ∗. As types of rules we are going to distinguish between cooperative (β=coo) and non-cooperative (i.e., the left-hand side of each rule is a single object; β=ncoo) ones. 30 A. Alhazov, R. Freund In the case of accepting systems, we also consider the idea of determinism, which means that in each step of any computation at most one (multiset of) rule(s) is applicable; in this case, we write deta for δ. In the literature, we find a lot of restricted variants of P systems with context conditions and priorities on the rules, e.g., we may omit the priorities or the context conditions completely. If in a rule (r, (P1, Q1),· · · ,(Pm, Qm)) we have m= 1, we say that (r, (P1, Q1)) is a rule with a simple context condition, and we omit the inner parentheses in the notation. Moreover, context conditions only using promoters are denoted by r|p1,··· ,pn, meaning (r, {p1,· · · , pn},∅), or, equivalently, (r, (p1,∅),· · · ,(pn,∅)); context conditions only using inhibitors are denoted by r|¬q1,··· ,¬qn, meaning (r, λ, {q1,· · · , qn}), or r|¬{q1,··· ,qn}. Likewise, a rule with both promoters and inhibitors can be specified as a rule with a simple context condition, i.e., r|p1,··· ,pn,¬q1,··· ,¬qnstands for (r, {p1,· · · , pn},{q1,··· , qn}). Finally, promoters and inhibitors of weight one are called atomic. Remark 1. If we do not consider determinism, then (the effect of) the rule (r, (P1, Q1),· · · ,(Pm, Qm)) is equivalent to (the effect of) the collection of rules {(r, Pj, Qj)|1≤j≤m}, no matter in which mode the P system is working (obviously, the priority relation has to be adapted accordingly, too). Remark 2. Let (r, {p1,· · · , pn}, Q) be a rule with a simple context condition; then we claim that (the effect of) this rule is equivalent to (the effect of) the collection of rules {(r, {pj}, Q ∪ {pk|1≤k < j})|1≤j≤m} even in the the case of a deterministic P system: If the first promoter is chosen to make the rule rapplicable, we do not care about the other promoters; if the second promoter is chosen to make the rule rapplicable, we do not allow p1to appear in the configuration, but do not care about the other promoters p3to pm; in general, when promoter pjis chosen to make the rule rapplicable, we do not allow p1to pj−1to appear in the configuration, but do not care about the other promoters pj+1 to pm; finally, we have the rule {(r, {pm}, Q ∪ {pk|1≤k < m})}. If adding {pk|1≤k < j}to Qhas the effect of prohibiting the promotor pjfrom enabling the rule rto be applied, this makes no harm as in this case one of the promoters pk, 1 ≤k < j, must have the possibility for enabling rto be applied. By construction, the domains of the new context conditions now are disjoint, so this transformation does not create (new) non-determinism. In a similar way, this transformation may be performed on context conditions which are not simple. Therefore, without restricting generality, the set of promoters may be assumed to be a singleton. In this case, we may omit the braces of the multiset notation for the promoter multiset and write (r, p, Q). Remark 3. As in a P system (O, Σ, w, R′, R, >) the set of rules R′can easily be deduced from the set of rules with context conditions R, we omit R′in the description of the P system. Moreover, for systems having only rules with a simple Controls in Deterministic Non-Cooperative P Systems 31 context condition, we omit din the description of the families of sets of numbers and simply write NδOPα 1(β, prok,l, inhk′,l′, pri). Moreover, each control mechanism not used can be omitted, e.g., if no priorities and only promoters are used, we only write NδOPα 1(β, prok,l). 3 Results 3.1 Recent results We first recall from [1] the bounding operation over multisets, with a parameter k∈Nas follows: for u∈O∗,bk(u) = vwith |v|a= min(|u|a, k) for all a∈O. The mapping bk“crops” the multisets by removing copies of every object a present in more than kcopies until exactly kremain. For two multisets u, u′, bk(u) = bk(u′) if for every a∈O, either |u|a=|u′|a< k, or |u|a≥kand |u′|a≥k. Mapping bkinduces an equivalence relation, mapping O∗into (k+ 1)|O| equivalence classes. Each equivalence class corresponds to specifying, for each a∈ O∗, whether no copy, one copy, or · · · k−1 copies, or “kcopies or more” are present. We denote the range of bkby {0,· · · , k}O. Lemma 1. [1] Context conditions are equivalent to predicates defined on boundings. Theorem 1. [1] Priorities are subsumed by conditional contexts. Remark 4. It is worth to note, see also [4], that if no other control is used, the priorities can be mapped to sets of atomic inhibitors. Indeed, a rule is inhibited precisely by the left side of each higher priority rule. This is straightforward in case when the priority relation is assumed to be a partial order. If it is not, then both the semantics of computation in P systems and the reduction of priorities to inhibitors is a bit more complicated, but the claim still holds. Fix an arbitrary deterministic controlled non-cooperative P system. Take kas the maximum of size of all multisets in all context conditions. Then, the bounding does not influence applicability of rules, and bk(u) is halting if and only if uis halting. We recall that bounding induces equivalence classes preserved by any computation. Lemma 2. [1] Assume u→xand v→y. Then bk(u) = bk(v)implies bk(x) = bk(y). Corollary 1. [1] If bk(u) = bk(v), then uis accepted if and only if vis accepted. 32 A. Alhazov, R. Freund Finally, the “at most NFIN ∪coNFIN” part of characterizing NdetaOPmaxpar 1(ncoo, (pro∗,∗, inh∗,∗)∗, pri) (the main theorem of [1]) is shown with the following argument: Each equivalence class induced by bounding is completely accepted or completely rejected. If no infinite equivalence class is accepted, then the accepted set is finite (containing numbers not exceeding (k−1) · |O|). If at least one infinite equivalence class is accepted, then the rejected set is finite (containing numbers not exceeding (k−1) · |O|). 3.2 Priorities only We start with an example how to deterministically rewrite an object tdepending on the presence or absence of object a. Example 1. Π= ({a, A, A′, t, t′, t+, t−},{a}, tA, R, R, >),where R={1 : t→t′,2 : a→λ, 3 : A→A′,4 : t′→t+,5 : t′→t−,6 : A′→λ}, >={a→λ > A →A′, A →A′> t′→t−, A′→λ > t′→t+}. Indeed, object twaits for one step by becoming t′, while Ahas to change to A′or wait, depending on the presence of a. Then, object t′becomes either t+ or t−, depending on whether Aor A′is present. Notice, e.g., how adding either rule t+→t+or rule t−→t−leads to a system accepting {0}or N\ {0}. Of course, accepting only zero could instead be done by a trivial one-rule system, but this example is important because such a deciding subsystem can be used, with suitable delays, as a building block for checking combinations of presence/absence of multiple symbols. We now proceed with characterizing systems with priorities only. Theorem 2. NdetaOPmaxpar 1(ncoo, pri) = {Nk,Nk∪ {0} | k≥0} ∪ {{0},∅}. Proof. We already know that the priorities correspond to sets of atomic inhibitors. This means that each system accepts a union of some equivalence classes induced by bounding b1(i.e., checking presence/absence). Note that various combinations of “= 0” and “≥1” yield numeric sets {0}and Nk(where k > 0 is the number of different symbols present). The family of all unions of these sets is Fpri ={Nk,Nk∪ {0} | k≥0} ∪ {{0},∅}. It follows that NdetaOPmaxpar 1(ncoo, pri)⊆Fpri. We proceed with the converse inclusion. Let Π0= ({a, t},{a}, t, R, R, >), then R={t→t}and empty relation >yields ∅. To accept {0}, we instead take R={a→a}and empty relation >. Controls in Deterministic Non-Cooperative P Systems 33 Now suppose we want to accept Nk. It would suffice to count that we have at least one of each objects a1,· · · , ak(we recall that we need to accept at least one input of size jfor each j≥k, or reject the input if j > k). To accept Nk∪ {0} instead, we may first perform a simultaneous check for the absence of all input symbols. Using the idea from Example 1, we construct the system Π1= (O, Σ ={ai,0|1≤i≤k}, tA0,0· · · Ak,0, R, R, >),where O={ai,j |1≤i≤k, 0≤j≤i+ 1} ∪ {Ai,j |0≤i≤k, 0≤j≤i+ 2} ∪ {t, z, p}∪{ti|0≤i≤i+ 1}, R={1 : ai,j →ai,j+1 |1≤i≤k, 0≤j≤i} ∪ {2 : Ai,j →Ai,j+1 |1≤i≤k, 0≤j≤i+ 1} ∪ {3 : t→t0,4 : t0→z, 5 : t0→t1,6 : p→p} ∪ {7 : ti→ti+1,8 : ti→p|1≤i≤k}, >={ai,0→ai,1> A0,0→A0,1|1≤i≤k} ∪ {A0,0→A0,1> t0→z, A0,1→A0,2> t0→t1} ∪ {ai,i →ai,i+1 > Ai,i →Ai,i+1 |1≤i≤k} ∪ {Ai,i →Ai,i+1 > ti→p, Ai,i+1 →Ai,i+2 > ti→ti+1}. Such system accept exactly Nk∪ {0}. Indeed, after first step, A0,0is present if all input symbols were absent, otherwise A0,1is present instead. For any i, 1 ≤i≤k, after step 1+i, object Ai,i is present if input symbol ai,0was present in the input, and otherwise Ai,i+1 is present instead. These “decision symbols” are used by ti, 0≤i≤k, to build the “presence picture”. We recall that it suffices to accept when all input symbols are present, or when none of them is present. In the first case, t0becomes z, and the computation only continues by rules from groups 1 and 2, leading to halting. Let us assume that the first sof the input symbols are present, s<k. Then, t0becomes t1, and then ···,ts, and then the absence of ts+1 will change tsinto p, leading to an infinite computation. Finally, if all input symbols are present, then the computation will halt with tk+1. It remains to notice that accepting Nk,k≥1, can be done by simply adding a rule z→z. 3.3 Promoters or inhibitors of weight 2 We start from examples, illustrating deterministic choice of rewriting p, depending on whether object ais absent, occurs exactly once, or occurs multiple times. Example 2. Symbols A,Bare primed if input is present (multiple input symbols are present). Then primed and unprimed symbols form mutually exclusive conditions. 34 A. Alhazov, R. Freund Π= (O={p, p′, p′′, p>, p1, p0, A, B, a}, Σ ={a}, pAB, R′, R),where R′={1 : p→p′,2 : A→A′,3 : B→B′, 4 : p′→p>,5 : p′→p′′,6 : p′′ →p1,7 : p′′ →p0}, R′={1 : p→p′,2 : A→A′|a,3 : B→B′|aa, 4 : p′→p>|B,5 : p′→p′′|B′,6 : p′′ →p1|A,7 : p′′ →p0|A′}. Example 3. Notice that if we replace all promoters by inhibitors with the same context, the effect of blocking rules will be reversed, but the result will be the same. Indeed, the role of A′and B′will switch from found aand found aa, respectively, to not found aand not found aa, respectively. R′={1 : p→p′,2 : A→A′|¬a,3 : B→B′|¬aa, 4 : p′→p>|¬B,5 : p′→p′′|¬B′,6 : p′′ →p1|¬A,7 : p′′ →p0|¬A′}. We now proceed with characterizing systems with context of weight two. Notice that we already know that their power does not exceed NFIN ∪coNFIN. Theorem 3. NdetaOPmaxpar 1(ncoo, pro2) = NdetaOPmaxpar 1(ncoo, inh2) = NFIN ∪coNFIN. Proof. We use the technique from Example 2 for all input symbols and combine the extracted information. Consider an arbitrary finite set M, and let max(M) = n. We will use the following strategy: to accept a number j∈M, we will accept an input multiset with exactly jsymbols appearing once, and nothing else. To accept the complement of M, we split it into sets M′′ ={j|j > n}and M′={j|j≤ n, j /∈M}. While M′is treated similarly to M, it only remains to accept M′′, which is covered by equivalence classes when all symbols are present, and at least one is present more than once. Π= (O, Σ ={ai|1≤i≤n}, tA1· · · AnB1···Bn, R′, R),where O={ti,j, Ti,j , t′ i,j, T ′ i,j |1≤i≤n+ 1,0≤j≤n} ∪ {Ai, A′ i, Bi, B′ i|1≤i≤n}∪{t, #}, R′={ti,j →Ti+1,j+1, Ti,j →Ti+1,j+1, ti,j →t′ i,j, Ti,j →T′ i,j, t′ i,j →ti+1,j+1, T′ i,j →Ti+1,j+1, t′ i,j →ti+1,j, T ′ i,j →Ti+1,j, Ai→A′ i, Bi→B′ i|1≤i≤n}∪{t→t1,0#→#} ∪ {Ti,n+1 →#|1≤i≤n}∪{ti,n+1 →#|i /∈M}, R={ti,j →Ti+1,j+1|Bi, Ti,j →Ti+1,j+1|Bi, ti,j →t′ i,j|B′ i, Ti,j →T′ i,j|B′ i, t′ i,j →ti+1,j+1|Ai, T′ i,j →Ti+1,j+1|Ai, t′ i,j →ti+1,j|A′ i, T′ i,j →Ti+1,j|A′ i, Ai→A′ i|ai, Bi→B′ i|aiai|1≤i≤n}∪{t→t1,0,#→#} ∪ {Ti,n+1 →#|1≤i≤n}∪{ti,n+1 →#|i /∈M}. Controls in Deterministic Non-Cooperative P Systems 35 The meaning of Ti,n+1 is that exactly iinput symbols are present, and at least one of them is present multiple times. The meaning of ti,n+1 is that the input consisted of exactly idifferent symbols. This is how an arbitrary finite set is accepted. To accept instead of Mits complement, replace i /∈Mby i∈Mand remove rule Tn,n+1 →#. Therefore, deterministic P systems with promoters of weight two accept exactly NFIN ∪coNFIN. For the inhibitor counterpart, notice that the computation of the number of different symbols present, as well as checking if any symbol is present multiple times, stays correct by simply changing promoters to the inhibitors with the same condition, just like in Example 3. Rules processing objects ti,n+1 and Ti,n+1 will have an opposite effect, accepting the complement of the set accepted by the system with promoters, again yielding NFIN ∪coNFIN. It is still open whether only inhibitors in the rules or only promoters in the rules are sufficient to yield NF IN ∪coNF IN with the asynchronuous mode, too. 4 Conclusion We have shown the characterizations of deterministic non-cooperative P systems with inhibitors of weight 2, with promoters of weight 2, and with priorities. The first two cases did not reduce the accepting power with respect to unrestricted weight. References 1. A. Alhazov, R. Freund: Asynchronuous and Maximally Parallel Deterministic Controlled Non-Cooperative P Systems Characterize N F IN and coN F IN .The Tenth Brainstorming Week in Membrane Computing, vol. 1, Sevilla, 2012, 25–34, and Membrane Computing - 13th International Conference, CMC13, Budapest (E. Csuhaj- Varj´u, M. Gheorghe, G. Rozenberg, A. Salomaa, Gy. Vaszil, Eds.), Lecture Notes in Computer Science 7762, 2013, 101-111. 2. 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, Milano, Revised Selected and Invited Papers, Lecture Notes in Computer Science 3365, Springer, 2005, 178–189. 3. R. Freund, L. Kari, M. Oswald, P. Sos´ık: Computationally Universal P Systems without Priorities: Two Catalysts are Sufficient, Theoretical Computer Science 330, 2, 2005, 251–266. 4. R. Freund, M. Kogler, M. Oswald, A General Framework for Regulated Rewriting Based on the Applicability of Rules. In: J. Kelemen, A. Kelemenov´a, Computation, Cooperation, and Life, Springer, Lecture Notes in Computer Science 6610, 2011, 35–53.