Asynchronous and Maximally Parallel Deterministic Controlled Non-Cooperative P Systems Characterize NFIN coNFIN

Asynchronous and Maximally Parallel Deterministic Controlled Non-Cooperative P Systems Characterize N F IN ∪coN F IN Artiom Alhazov1,2and Rudolf Freund3 1Universit`a degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336, 20126 Milano, Italy [email protected] 2Institute of Mathematics and Computer Science Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova [email protected] 3Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria E-mail: [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. In this paper we show that the power of the deterministic subclass of such systems is computationally complete in the sequential mode, but only subregular in the asynchronous mode and in the maximally parallel mode. 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 [2] and [4]. It is also known that non-cooperative rewriting P systems with either promoters or inhibitors are computationally complete, [1]. 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. The purpose of this paper is to formally prove that computational completeness cannot be achieved by deterministic systems when working in the asynchronous or in the maximally parallel mode. 26 A. Alhazov, R. Freund 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 NFIN (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. Arule 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. 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. A Characterization of N F IN ∪coN F IN 27 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), multiple 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 rule is applicable to them. In the asynchronous 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 promoters 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. 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. 28 A. Alhazov, R. Freund 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). Example 1. Consider an arbitrary finite set Hof numbers. Choose K= max (H)+ 1; then we construct the following deterministic accepting P system with promoters and inhibitors: Π= (O, {a}, s0f0· · · fK, R′, R), O={a}∪{si, fi|0≤i≤K}, R′={si→si+1 |0≤i≤K−1}∪{fi→fi|0≤i≤K}, R={si→si+1|ai+1 ,|0≤i≤K−1} ∪{fi→fi|si,¬ai+1 ,|0≤i < K, i /∈H}∪ {fK→fK|sK}. The system step by step, by the application of the rule si→si+1|ai+1 , 0 ≤i < K, checks if (at least) i+ 1 copies of the symbol aare present. If the computation stops after isteps, i.e., if the input has consisted of exactly icopies of a, then this input is accepted if and only if i∈H, as exactly in this case the system does not start an infinite loop with using fi→fi|si,¬ai+1 . If the input has contained more than max (H) copies of a, then the system arrives in the state sKand will loop forever with fK→fK|sK. Therefore, exactly His accepted. To accept the complement of Hinstead, we simply change i /∈Hto i∈Hand as well omit the rule fK→fK|sK. It is easy to see that for the maximally parallel mode, we can A Characterization of N F IN ∪coN F IN 29 replace each rule fi→fi|si,¬ai+1 by the corresponding rule fi→fi|si; in this case, this rule may be applied with still some abeing present while the system passes through the state si, but it will not get into an infinite loop in that case. In sum, we have shown that NdetaOPasyn 1(ncoo, (pro1,∗, inh1,∗)1)⊇FIN ∪coNF IN and NdetaOPmaxpar 1(ncoo, pro1,∗)⊇FIN ∪coNF IN. Example 2. For P systems working in the maximally parallel way we can even construct a system with inhibitors only: Π= (O, {a}, tsK, R), O={a, t}∪{si|0≤i≤K}, R′={si→tsi−1, si→si|1≤i≤K}∪{t→λ, s0→s0}, R={si→tsi−1|¬ai|1≤i≤K} ∪ {t→λ}∪{si→si|¬t|0≤i≤K, i /∈H}. This construction does not carry over to the case of the asynchronous mode, as the rule t→λis applied in parallel to the rules si→tsi−1|¬aiuntil the input ai is reached. In this case, the system canot change the state sianymore, and then it starts to loop if and only if i /∈H. To accept the complement of Hinstead, change i∈Hto i /∈H, i.e., in sum, we have proved that NdetaOPmaxpar 1(ncoo, inh1,∗)⊇FIN ∪coNF IN. As we shall show later, all the inclusions stated in Example 1 and Example 2 are equalities. 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 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). 2.1 Register machines In what follows we will need to simulate register machines; here we briefly recall their definition and some of their computational properties. A register machine is a tuple M= (m, B, l0, lh, P), where mis the number of registers, Pis the set of instructions bijectively labeled by elements of B,l0∈Bis the initial label, and lh∈Bis the final label. The instructions of Mcan be of the following forms: 30 A. Alhazov, R. Freund •l1: (ADD (j), l2, l3), with l1∈B\ {lh},l2, l3∈B, 1 ≤j≤m. Increase the value of register jby one, and non-deterministically jump to instruction l2or l3. This instruction is usually called increment. •l1: (SUB (j), l2, l3), with l1∈B\ {lh},l2, l3∈B, 1 ≤j≤m. If the value of register jis zero then jump to instruction l3, otherwise decrease the value of register jby one and jump to instruction l2. The two cases of this instruction are usually called zero-test and decrement, respectively. •lh:HALT . Stop the execution of the register machine. A register machine is deterministic if l2=l3in all its ADD instructions. A configuration of a register machine is described by the contents of each register and by the value of the program counter, which indicates the next instruction to be executed. Computations start by executing the first instruction of P(labeled with l0), and terminate with reaching a HALT -instruction. Register machines provide a simple universal computational model [5]. We here consider register machines used as accepting or as generating devices. In accepting register machines, a vector of non-negative integers is accepted if and only if the register machine halts having it as input. Usually, without loss of generality, we may assume that the instruction lh:HALT always appears exactly once in P, with label lh. In the generative case, we start with empty registers and take the results of all possible halting computations. 3 Results In this section we mainly investigate deterministic accepting P systems with context conditions and priorities on the rules (deterministic P systems for short) using only non-cooperative rules and working in the sequential, the asynchronous, and the maximally parallel mode. Remark 4. We first notice that maximal parallelism in systems with noncooperative rules means the total parallelism for all symbols to which at least one rule is applicable, and determinism guarantees that “at least one” is “exactly one” for all reachable configurations and objects. Determinism in the sequential mode requires that at most one symbol has an associated applicable rule for all reachable configurations. Surprisingly enough, in the case of the asynchronous mode we face an even worse situation than in the case of maximal parallelism – if more than one copy of a specific symbol is present in the configuration, then no rule can be applicable to such a symbol in order not to violate the condition of determinism. We now define the bounding operation over multisets, with a parameter k∈N as follows: for u∈O∗,bk(u) = vwith |v|a= min(|u|a, k) for all a∈O. A Characterization of N F IN ∪coN F IN 31 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. Context conditions are equivalent to predicates defined on boundings. Proof. We start by representing context conditions by predicates on boundings. Consider a rule with a simple context condition (r, p, Q), and let the current configuration be C. Then, it suffices to take k≥max (|p|,max{|q| | q∈Q}), and let C′=bk(C). The applicability condition for (r, p, Q) may be expressed as p⊆C′∧(∧q∈Qq⊆ C′). Indeed, x⊆C←→ x⊆C′for every multiset xwith |x| ≤ k, because for every a∈O,|x|a≤ |C|a←→ |x|a≤min (|C|a, k) holds if |x|a≤k. Finally, we notice that context conditions which are not simple can be represented by a disjunction of the corresponding predicates. Conversely, we show that any predicate E⊆ {0,· · · , k}Ofor the bounding mapping bkfor rule rcan be represented by some context conditions. For each multiset c∈E, we construct a simple context condition to the effect of “contains c, but, for each acontained in cfor less than ktimes, not more than |c|asymbols a”: {(r, c, {a|c|a+1 | |c|a< k}) |c∈E}. Joining multiple simple context conditions over the same rule into one rule with context conditions concludes the proof.  The following theorem is valid even when the rules are not restricted to noncooperative ones, and when determinism is not required, in either derivation mode (also see [3]). Theorem 1. Priorities are subsumed by conditional contexts. Proof. A rule is prohibited from being applicable due to a priority relation if and only if at least one of the rules with higher priority might be applied. Let rbe a rule of a P system (O, Σ, w, R′, R, >), and let r1> r, · · · , rn> r. Hence, the rule r is not blocked by the rules r1,· · · , rnif and only if the left-hand sides of the rules r1,· · · , rn,lhs (r1),· · · , lhs (rn) are not present in the current configuration or the context conditions given in these rules are not fulfilled. According to Lemma 1, these context conditions can be formulated as predicates on the bounding bkwhere kis the maximum of weights of all left-hand sides, promoters, and inhibitors in the rules with higher priority r1,· · · , rn. Together with the context conditions from r itself, we finally get context conditions for a new rule r′simulating r, but also incorporating the conditions of the priority relation. Performing this transformation for all rules rconcludes the proof.  32 A. Alhazov, R. Freund Remark 5. From [3] we already know that in the case of rules without context conditions, the context conditions in the new rules are only sets of atomic inhibitors, which also follows from the construction given above. A careful investigation of the construction given in the proof of Theorem 1 reveals the fact that the maximal weights for the promoters and inhibitors to be used in the new system are bounded by the number kin the bounding bk. 3.1 Sequential Systems Although throughout the rest of the paper we are not dealing with sequential systems anymore, the proof of the following theorem gives us some intuition why, for deterministic non-cooperative systems, there are severe differences between the sequential mode and the asynchronous or the maximally parallel mode. Theorem 2. NdetaOP sequ 1(ncoo, pro1,1, inh1,1) = NRE. Proof. Consider an arbitrary deterministic register machine M= (m, B, l0, lh, P). We simulate Mby a deterministic P system Π= (O, {a1}, l0, R) where O={aj|1≤j≤m}∪{l, l1, l2|l∈B}, R={l→ajl′|(l:ADD(j), l′)∈P} ∪ {l→l1|aj, aj→a′ j|l1,¬a′ j, l1→l2|a′ j, a′ j→λ|l2, l1→l′|¬a′ j, l→l′′|¬aj|(l:SUB(j), l′, l′′)∈P}. We claim that Πis deterministic and non-cooperative, and it accepts the same set as M. As can be seen in the construction of the deterministic P system in the proof above, the rule aj→a′ j|l1,¬a′ jused in the sequential mode can be applied exactly once, priming exactly one symbol ajto be deleted afterwards. Intuitively, in the asynchronous or the maximally parallel mode, it is impossible to choose only one symbol out of an unbounded number of copies to be deleted. The bounding operation defined above will allow us to put this intuition into a formal proof. 3.2 Asynchronous and Maximally Parallel Systems 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 proceed by showing that bounding induces equivalence classes preserved by any computation. Lemma 2. Assume u⇒xand v⇒y. Then bk(u) = bk(v)implies bk(x) = bk(y). A Characterization of N F IN ∪coN F IN 33 Proof. Equality bk(u) = bk(v) means that for every symbol a∈O, if |u|a=|va| then |u|a≥kand |v|a≥k, and we have a few cases to be considered. If no rule is applicable to a, then the inequality of symbols awill be indistinguishable after bounding also in the next step (both with at least kcopies of a). Otherwise, exactly one rule ris applicable to a(by determinism, and bounding does not affect applicability), then the difference of the multiplicities of the symbol amay only lead to differences of the multiplicities of symbols bfor all b∈rhs (r). However, either all copies of aare erased by the rule a→λor else at least one copy of a symbol bwill be generated from each copy of aby this rule alone, so |x|b≥ |u|a≥k and |y|b≥ |v|a≥k, so all differences of multiplicities of an object bin uand vwill be indistinguishable after bounding in this case, too.  Corollary 1. If bk(u) = bk(v), then uis accepted if and only if vis accepted. Proof. Let wbe the fixed part of the initial configuration. Then we consider computations from uw and from vw. Clearly, bk(uw) = bk(vw). Equality of boundings is preserved by one computation step, and hence, by any number of computation steps. Assume the contrary of the claim: one of the computations halts after ssteps, while the other one does not, i.e., let uw ⇒su′and vw ⇒sv′. By the previous paragraph, bk(u′) = bk(v′). Since bounding does not affect applicability of rules, either both u′and v′are halting, or none of them. The contradiction proves the claim.  We should like to notice that the arguments in the proofs of Lemma 2 and Corollary 1 are given for the maximal parallel mode; following the observation stated at the end of Remark 4, these two results can also be argued for the asynchronous mode. Theorem 3. For deterministic P systems working in the asynchronous or in the maximally parallel mode, we have the following characterization: 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). Proof. 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|). This proves the “at most NFIN ∪coNFIN” part. In Examples 1 and 2 we have already shown that NdetaOPα 1(ncoo, pro1,∗, inh1,∗)⊇FIN ∪coNF IN