Computational Completeness of P Systems Using Maximal Variants of the Set Derivation Mode

Computational Completeness of P Systems Using Maximal Variants of the Set Derivation Mode Artiom Alhazov1, Rudolf Freund2, and Sergey Verlan3 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, TU Wien Favoritenstraße 9-11, 1040 Wien, Austria E-mail: [email protected] 3LACL, Universit´e Paris Est – Cr´eteil Val de Marne 61, av. G´en´eral de Gaulle, 94010, Cr´eteil, France Email: [email protected] Summary. We consider P systems only allowing rules to be used in at most one copy in each derivation step, especially the variant of the maximally parallel derivation mode where each rule may only be used at most once. Moreover, we also consider the derivation mode where from those sets of rules only those are taken which have the maximal number of rules. We check the computational completeness proofs of several variants of P systems and show that some of them even literally still hold true for the for these two new set derivation modes. Moreover, we establish two new results for P systems using target selection for the rules to be chosen together with these two new set derivation modes. 1 Introduction Membrane systems with symbol objects are a theoretical framework of parallel distributed multiset processing. Usually, multisets of rules are applied in parallel to the objects in the underlying configuration; for example, in the maximally parallel derivation mode (abbreviated max), a non-extendable multiset of rules is applied to the current configuration. In this paper we now consider variants of these derivation modes, where each rule is only used in at most one copy, i.e., we consider sets of rules to be applied in parallel, for example, in the set-maximally parallel derivation mode (abbreviated smax) we apply non-extendable sets of rules, and in another derivation mode we apply sets of rules which contain a maximal number of applicable rules (abbreviated maxrule). 60 A. Alhazov, R. Freund, and S. Verlan Taking sets of rules instead of multisets is a quite natural restriction and it arises from different motivations, e.g., firing a maximal set of transitions in Petri Nets [5, 8] or optimizing an implementation of FPGA simulators [13]. A natural question arises concerning the power of set-based modes in contrast to multisetbased ones. The first attempt to go into this direction was done in [10] where it was shown that in some cases the computational completeness results established for the max-mode also hold for the smax-mode. In this paper we continue this line of research and we show that for several variants of P systems the proofs for computational completeness for max can be taken over even literally for smax and eventually even for maxrule, but on the other hand there are also variants of P systems where the derivation modes smax and maxrule yield even stronger results than the max-mode. 2 Variants of P Systems In this section we recall the well-known definitions of several variants of P systems as well as some variants of derivation modes and also introduce the variants of set derivation modes considered in the following. A (cell-like) P system is a construct Π= (O, C, µ, w1, . . . , wm, R1, . . . , Rm, fO, fI) where •Ois the alphabet of objects, •C⊂Ois the set of catalysts, •µis the membrane structure (with mmembranes), •w1, . . . , wmare multisets of objects present in the mregions of µat the beginning of a computation, •R1, . . . , Rmare finite sets of rules, associated with the regions of µ, •fOis the label of the membrane region from which the outputs are taken (in the generative case) •fIis the label of the membrane region where the inputs are put at the beginning of a computation (in the accepting case). fO= 0/fI= 0 indicates that the output/input is taken from the environment. If a rule u→vhas at least two objects in u, then it is called cooperative, otherwise it is called non-cooperative.Catalytic rules are of the form ca →cv, where c∈Cis a special object which never evolves and never passes through a membrane, it just assists object ato evolve to the multiset v. In catalytic P systems we use non-cooperative as well as catalytic rules. In a purely catalytic P system we only allow catalytic rules. In the maximally parallel derivation mode (abbreviated by max), in any computation step of Πwe choose a multiset of rules from R, defined as the union of the sets R1, . . . , Rm, in such a way that no further rule can be added to it so that the obtained multiset would still be applicable to the existing objects in the regions 1, . . . , m. Maximal Variants of the Set Derivation Modes 61 2.1 Set Derivation Modes The basic set derivation mode is defined as the derivation mode where in each derivation step at must one copy of each rule may be applied in parallel with the other rules; this variant of a basic derivation mode corresponds to the asynchronous mode with the restriction that only those multisets of rules are applicable which contain at most one copy of each rule, i.e., we consider sets of rules: Appl(Π, C, set) ={R∈Appl(Π, C, asyn)| |R|r≤1 for each r∈ R} In the set-maximally parallel derivation mode (this derivation mode is abbreviated by smax for short), in any computation step of Πwe choose a non-extendable multiset Rof rules from Appl(Π, C, set); following the notations elaborated in [7], we define the mode smax as follows: Appl(Π, C, smax) ={R∈Appl(Π, C, set)|there is no R0∈Appl(Π, C, set) such that R0⊃R} The smax-derivation mode corresponds to the min1-mode with the discrete partitioning of rules (each rule forms its own partition), see [7]. The derivation mode maxrulesmax is a special variant where only a maximal set of rules is allowed to be applied. But it can also seen as the variant of the basic set mode where we just take a set of applicable rules with the maximal number of rules in in it, hence, we will also call it the maxrule derivation mode. Formally we have: Appl(Π, C, maxrule) ={R∈Appl(Π, C, set)|there is no R0∈Appl(Π, C, set) such that |R0|>|R|} As usual, with all these variants of derivation modes as defined above, we consider halting computations. We may generate or accept or even computing functions or relations. The inputs/outputs may be multisets or strings, defined in the well-known way. 2.2 The History of the smax-Derivation Mode In [13], a paper on fast P systems simulators using FPGA, the problem of the unbounded max-mode was considered as too difficult to be parallelized on this hardware. In the quest for an efficient solution, the authors proposed to restrict to the case of the maximal parallelism where each rule can be applied at most once. The most important advantage of this variant was that the multiset of applicable rules could be represented as a binary string, i.e., an encoding as a number. Moreover, the paper showed that in many interesting cases it is possible to represent the language of corresponding binary strings at each step by an automaton. Then the problem of the simulation of a P system could be solved as follows: 62 A. Alhazov, R. Freund, and S. Verlan •Find the size Sof the set of multisets of applicable rules (the size of the language of binary strings). •Take a random number k∈ {1..S}and chose the string representing k. This algorithm allowed for obtain a speed-up of magnitude 105. The advantages of the set-maximally parallel derivation mode over the unbounded maximally parallel derivation mode are: •A compact representation of the applicable multisets of rules as binary strings/numbers is obtained. •Most of the computational completeness results still hold. •Simpler analysis of the behavior is possible. •Only a bounded number of (multi)sets of rules has to be computed for each derivation step. In [10], the set-maximally parallel derivation mode was called flat maximal parallel derivation mode, and, for example, P systems with promoters are shown to be computationally complete using this flat maximal parallel derivation mode with non-cooperative rules. 2.3 Examples In the maximally parallel mode, we in addition need target or rule or label agreement to obtain a2n|n≥0, otherwise only {an|n≥1}can be obtained. 1 environment (0) 2 Initial multiset: a 1 : a→a(here)a(here) 2 : a→a(in) target/ rule/ label agreement: the same rule is used for all symbols a Fig. 1. Example of a P system. Maximal Variants of the Set Derivation Modes 63 In the set-maximally parallel mode smax, we in addition need target or rule or label agreement to obtain {an|n≥1}, otherwise only {a}can be obtained, because: •If 2 : a→a(in) is used in the first step, then ais obtained. •If 1 : a→a(here)a(here) is applied at least once, then from the second step on it has to be applied infinitely often, as only one copy of acan be sent into membrane 2 by the second rule 2 : a→a(in). The same arguments hold for the derivation mode maxrule. 3 Symport/Antiport P Systems Asymport/antiport P system is a construct Π= (O, E, µ, w0, w1, . . . , wm, R1, . . . , Rm, fO, fI) where •Ois the alphabet of objects, •E⊆Ois the set of objects being available in the environment in an unbounded number, •µis the membrane structure (with mmembranes), •w0is the finite multiset of objects over O\Epresent in the environment at the beginning of a computation, •w1, . . . , wmare the multisets of objects present in the mregions of µat the beginning of a computation, •R1, . . . , Rmare finite sets of symport and/or antiport rules, associated with the membranes of µ, •fO,fIis the label of the membrane region from which the outputs are taken/the inputs are put in. Every rule is of the form (u, out;v, in) with u, v ∈O∗and uv 6=λ; if u=λ or v=λthen this rule is called a symport rule, otherwise it is called an antiport rule. The application of a rule (u, out;v, in)∈Rimeans sending out ufrom region iand taking vinto it from the surrounding region. For (u, out;v, in), max {|u|,|v|} is called its weight and |uv|is called its size; obviously, for symport rules weight and size are the same. The families of sets Yγ,δ (Π), Y∈ {N, Ps},δ∈ {gen, acc}, and γ∈ {sequ, asyn, max, smax, maxrule, . . . }, computed by symport/antiport P systems with at most mmembranes, symport rules with maximal weight ras well as antiport rules with maximal weight wand maximal size sare denoted by Yγ,δOPm(symr, antiw,s). 3.1 Accepting Antiport P Systems Theorem 1. For Y∈ {N, Ps},β∈ {max, smax, maxrule}, Yβ,accDOPm(anti2,3) = Y RE. 64 A. Alhazov, R. Freund, and S. Verlan Proof. Let M= (m, B, l0, lh, P) be an arbitrary deterministic register machine. We now construct an antiport P system simulating M. The number in register r is represented by the corresponding number of symbol objects or. •An ADD-instruction p: (ADD(r), q) is simulated by the rule (p, out;orq, in). •A SUB-instruction p: (SUB(r), q, s) is simulated by the following rules 1. (p, out;p0p00, in); 2. (p0, out; ˜p, in) as well as (p00or, out; ¯p, in) which is executed in parallel if and only if the register is not empty; 3. (˜pp00, out;s, in) (if register was empty), (˜p¯p, out;q, in) (if register was not empty). As can be seen immediately, in each step only different rules can be applied, each of them only once. Hence, the proof elaborated for the max-mode literally also works for the derivation modes smax and maxrule without any restrictions as well. ut 4 P Systems with Anti-Matter For any object a(matter), we consider its anti-object (anti-matter) a−and the corresponding (cooperative) annihilation rule aa−→λ. This rule is assumed to exist in all membranes. In the following, we assume these annihilation rules to have (weak) priority over all other rules, i.e., other rules may only be applied if objects cannot be bound by an annihilation rule any more. This type of rules is abbreviated by antim/pri, indicating matter/anti-matter annihilation rules having weak priority. For further results we refer to [1]. 4.1 Matter/Anti-Matter Annihilation Rules Having Priority The matter/anti-matter annihilation rules are so powerful that we only need the minimum number of catalysts, i.e., zero (cat(0) = ncoo). Theorem 2. [1] For any n≥1,Y∈ {N, Ps},δ∈ {gen, acc, aut},α∈ {acc, aut}, Z∈ {Fun, Rel}, and β∈ {max, smax, maxrule}, Yβ,δOPn(ncoo, antim/pri) = Y RE and ZYβ,αOPn(ncoo, antim/pri) = ZY RE. 4.2 Deterministic Matter/Anti-Matter Accepting P Systems In the accepting case, we can even simulate the actions of a deterministic register machine in a deterministic way, i.e., for each configuration of the system, there can be at most one multiset of rules applicable to it. Yet the proof exhibited in [1], even fulfills the condition that every rule is only applied at most once. Maximal Variants of the Set Derivation Modes 65 Theorem 3. For any n≥1,Y∈ {N, Ps}, and β∈ {max, smax, maxrule}, Yβ,detaccOPn(ncoo, antim/pri) = Y RE and FunYβ,detaccOPn(ncoo, antim/pri) = F unY RE. Proof. We only show how the SUB-instructions of a register machine M= (m, B0, l0, lh, P) can be simulated in a deterministic way without introducing a trap symbol and therefore causing infinite loops by them: Let B={l|l: (SUB (r), l0, l00)∈P}and, for every register r, ˜ Mr=n˜ l|l: (SUB (r), l0, l00)∈Po, ˜ Mr−=n˜ l−|l: (SUB (r), l0, l00)∈Po, ˆ Mr=nˆ l|l: (SUB (r), l0, l00)∈Po, ˆ Mr−=nˆ l−|l: (SUB (r), l0, l00)∈Po. We now take the rules ar−→˜ Mr−ˆ Mrand the annihilation rules arar−→λ for every register ras well as ˆ lˆ l−→λand ˜ l˜ l−→λfor all l∈B. Then a SUB- instruction l1: (SUB (r), l2, l3), with l1∈B,l2, l3∈B0, 1 ≤r≤m, is simulated by l1→¯ l1ar −, ¯ l1→ˆ l1−(˜ Mr\ {˜ l1}), ˆ l1−→l2(˜ Mr−\ {˜ l1−}), and ˜ l1−→l3(ˆ Mr−\ {ˆ l1−}). The symbol ˆ l1−generated by the second rule is eliminated again and replaced by ˜ l1−if ar−is not annihilated. Again, the proof elaborated for the max-mode literally also works for the derivation modes smax and maxrule without any restrictions as well. ut 5 Catalytic and Purely Catalytic P Systems We now investigate proofs elaborated for catalytic and purely catalytic P systems working in the max-mode for the smax-mode. 5.1 Computational Completeness of Catalytic P Systems We first check the construction for simulating a register machine M= (d, B, l0, lh, R) by a catalytic P system Π, with m≤dbeing the number of decrementable registers, elaborated in [3] for the max-mode, and argue why it works for the smax-mode, too. For all dregisters, nicopies of the symbol oiare used to represent the value niin register i, 1 ≤i≤d. For each of the mdecrementable registers, we take 66 A. Alhazov, R. Freund, and S. Verlan a catalyst ciand two specific symbols di, ei, 1 ≤i≤m, for simulating SUB- instructions on these registers. For every l∈B, we use pl, and also its variants ¯pl,ˆpl,˜plfor l∈BSUB, where BSUB denotes the set of labels of SUB-instructions. Π= (O, C, µ = [ ]1, w1=c1. . . cmd1. . . dmp1w0, R1, f = 1), O=C∪D∪E∪Σ ∪ {#}∪{pl|l∈B}∪{¯pl,ˆpl,˜pl|l∈BSUB}, C={ci|1≤i≤m}, D={di|1≤i≤m}, E={ei|1≤i≤m}, Σ={oi|1≤i≤d}, R1={pj→orpkDm, pj→orplDm|j: (ADD(r), k, l)∈R} ∪ {pj→ˆpjerDm,r, pj→¯pjDm,r,ˆpj→˜pjD0 m,r, ¯pj→pkDm,˜pj→pkDm|j: (SUB(r), k, l)∈R} ∪ {cror→crdr, crdr→cr, cr⊕m1er→cr⊕m1|1≤r≤m}, ∪ {dr→#, crer→cr#|1≤r≤m} ∪ {#→#}. Here r⊕m1 for r < m simply is r+ 1, whereas for r=mwe define m⊕m1 = 1; w0stands for additional input present at the beginning. Usually, every catalyst ci,i∈ {1, . . . , m}, is kept busy with the symbol di using the rule cidi→ci, as otherwise the symbols diwould have to be trapped by the rule di→#, and the trap rule # →# then enforces an infinite non-halting computation. In the smax-derivation mode only one trap rule #→#will be carried out, but this is the only difference! Only during the simulation of SUB-instructions on register rthe corresponding catalyst cris left free for decrementing or for zero-checking in the second step of the simulation, and in the decrement case both crand its “coupled” catalyst cr⊕m1 are needed to be free for specific actions in the third step of the simulation. For the simulation of instructions, we use: Dm=Qi∈[1..m]di, Dm,r =Qi∈[1..m]\{r}di, D0 m,r =Qi∈[1..m]\{r,r⊕m1}di. The HALT-instruction labeled lhis simply simulated by not introducing the corresponding state symbol plh, i.e., replacing it by λ, in all rules defined in R1. Each ADD-instruction j: (ADD(r), k, l), for r∈ {1, . . . , d}, can easily be simulated by the rules pj→orpkDmand pj→orplDm; in parallel, the rules cidi→ci, 1 ≤i≤m, have to be carried out, as otherwise the symbols diwould have to be trapped by the rules di→#. Each SUB-instruction j: (SUB(r), k, l), is simulated as shown in the table listed below (the rules in brackets [ and ] are those to be carried out in case of a wrong choice): Maximal Variants of the Set Derivation Modes 67 Simulation of the SUB-instruction j: (SUB(r), k, l) if register ris not empty register ris empty pj→ˆpjerDm,r pj→¯pjDm,r cror→crdr[crer→cr#] crshould stay idle ˆpj→˜pjD0 m,r ¯pj→pkDm crdr→cr[dr→#] [dr→#] ˜pj→pkDm cr⊕m1er→cr⊕m1 In the first step of the simulation of each instruction (ADD-instruction, SUB- instruction, and even HALT-instruction) due to the introduction of Dmin the previous step (we also start with that in the initial configuration) every catalyst cris kept busy by the corresponding symbol dr, 1 ≤r≤m. Based on the construction elaborated in [3] and recalled above in sum we have obtained the following result: Theorem 4. For any register machine M= (d, B, l0, lh, R), with m≤dbeing the number of decrementable registers, we can construct a catalytic P system Π= (O, C, µ = [ ]1, w1, R1, f = 1) working in the max- or the smax-derivation mode and simulating the computations of Msuch that |R1| ≤ ADD1(R)+2×ADD2(R)+5×SUB(R)+5×m+ 1, where ADD1(R)denotes the number of deterministic ADD-instructions in R, ADD2(R)denotes the number of non-deterministic ADD-instructions in R, and SUB(R)denotes the number of SUB-instructions in R. 5.2 Computational Completeness of Purely Catalytic P Systems For the purely catalytic case, one additional catalyst cm+1 is needed to be used with all the non-cooperative rules. Unfortunately, in this case a slightly more complicated simulation of SUB-instructions is needed, a result established in [12], where for catalytic P systems |R1| ≤ 2×ADD1(R)+3×ADD2(R)+6×SUB(R)+5×m+ 1, and for purely for catalytic P systems |R1| ≤ 2×ADD1(R)+3×ADD2(R)+6×SUB(R)+6×m+ 1, is shown. Yet also this proof literally works for the smax-derivation mode as well, with the only exception that the trap rule # →# is carried out at most once. 74 A. Alhazov, R. Freund, and S. Verlan In the following sections, we now turn our attention to models of P systems where the derivation mode smax yields different, in fact, stronger results than the derivation mode max. 8 Atomic Promoters and Inhibtors As shown in [11], P systems with non-cooperative rules and atomic inhibitors are not computationally complete when the maximally parallel derivation mode is used. P systems with non-cooperative rules and atomic promoters can at least generate PsET0L. On the other hand, already in [10], the computational completeness of P systems with non-cooperative rules and atomic promoters has been shown. In the following we will establish a new proof for the simulation of a register machine where the overall number of promoters only depends on the number of decrementable registers of the register machine. Moreover, we also show a new pretty surprising result, establishing computational completeness of P systems with non-cooperative rules and atomic inhibitors, and the number of inhibitors again only depends on the number of decrementable registers of the simulated register machine. Finally, in both cases, if the register machine is deterministic, then the P system is deterministic, too. 8.1 Atomic Promoters We now establish our new proof for the computational completeness of P systems with non-cooperative rules and atomic promoters when using the derivation mode smax; the overall number of promoters only is 5mwhere mis the number of decrementable registers of the simulated register machine. Theorem 8. For any register machine M= (d, B, l0, lh, R), with m≤dbeing the number of decrementable registers, we can construct a P system with atomic inhibitors Π= (O, µ = [ ]1, w1=l0, R1, f = 1) working in the smax- or maxrule-derivation mode and simulating the computations of Msuch that |R1| ≤ ADD1(R)+2×ADD2(R)+5×SUB(R)+7×m, where ADD1(R)denotes the number of deterministic ADD-instructions in R, ADD2(R)denotes the number of non-deterministic ADD-instructions in R, and SUB(R)denotes the number of SUB-instructions in R; moreover, the number of atomic inhibitors is 5m. Finally, if the register machine is deterministic, then the P system is deterministic, too. Maximal Variants of the Set Derivation Modes 75 Proof. The numbers of objects orrepresent the contents of the registers r, 1 ≤ r≤d; moreover, we denote BSUB ={p|p: (SUB(r), q, s)∈R}. O={or|1≤r≤d}∪{o0 r, cr, c0 r, c00 r, c000 r|1≤r≤m} ∪(B\ {lh})∪ {p0, p00, p000 |p∈BSUB} The symbols from {o0 r, cr, c0 r, c00 r, c000 r|1≤r≤m}are used as promoters. An ADD-instruction p: (ADD(r), q, s) is simulated by the two rules p→qor and p→sor. A SUB-instruction p: (SUB(r), q, s) is simulated in four steps as follows: 1. p→p0cr; 2. p0→p00c0 r;or→o0 r|cr,cr→λ; 3. p00 →p000c000 r,c0 r→c00 r|o0 r,o0 r→λ; 4. p000 →q|c00 r,p000 →s|c0 r,c0 r→λ|c000 r,c00 r→λ,c000 r→λ. As final rule we could use lh→λ, yet we can omit this rule and replace every appearance of lhin all rules as described above by λ.ut 8.2 Atomic Inhibtors We now show that even P systems with non-cooperative rules and atomic promoters using the derivation mode smax can simulate any register machine needing only 2m+ 1 inhibitors where mis the number of decrementable registers of the simulated register machine. Theorem 9. For any register machine M= (d, B, l0, lh, R), with m≤dbeing the number of decrementable registers, we can construct a P system with atomic inhibitors Π= (O, µ = [ ]1, w1=l0, R1, f = 1) a P system with atomic inhibitors Π= (O, µ = [ ]1, w1=l0, R1, f = 1) working in the smax- or maxrule-derivation mode and simulating the computations of M such that |R1| ≤ ADD1(R)+2×ADD2(R)+5×SUB(R)+3×m+ 1, where ADD1(R)denotes the number of deterministic ADD-instructions in R, ADD2(R)denotes the number of non-deterministic ADD-instructions in R, and SUB(R)denotes the number of SUB-instructions in R; moreover, the number of atomic inhibitors is 2m+ 1. Finally, if the register machine is deterministic, then the P system is deterministic, too. Proof. The numbers of objects orrepresent the contents of the registers r, 1 ≤ r≤d. The symbols drprevent the register symbols or, 1 ≤r≤m, from evolving. 76 A. Alhazov, R. Freund, and S. Verlan O={or|1≤r≤d}∪{o0 r|1≤r≤m}∪{dr|0≤r≤m} ∪(B\ {lh})∪ {p0, p00,˜p|p∈BSUB} We denote D=Qm i=1 diand Dr=Qm i=1,i6=rdi. An ADD-instruction p: (ADD(r), q, s) is simulated by the two rules p→qorD and p→sorD. A SUB-instruction p: (SUB(r), q, s) is simulated in four steps as follows: 1. p→p0Dr; 2. p0→p00Dd0; in parallel, the following rules are used: or→o0 r|¬dr,dk→λ, 1 ≤k≤m; 3. p00 →˜pD |¬o0 r;o0 r→λ,d0→λ; again, in parallel the rules dk→λ, 1 ≤k≤m, are used; 4. p00 →qD |¬d0, ˜p→sD. As final rule we could use lh→λ, yet we can omit this rule and replace every appearance of lhin all rules as described above by λ.ut 9 P Systems with Target Selection In P systems with target selection, all objects on the right-hand side of a rule must have the same target, and in each derivation step, for each region a (multi)set of rules – non-empty if possible – having the same target is chosen. We show that for P systems with target selection in the derivation mode smax no catalyst is needed any more, and with maxrule, we even obtain a deterministic simulation of deterministic register machines. Theorem 10. For any register machine M= (d, B, l0, lh, R), with m≤dbeing the number of decrementable registers, we can construct a P system with noncooperative rules working in the smax-derivation mode and simulating the computations of M. Proof. As usual, we take an arbitrary register machine Mwith dregisters satisfying the following conditions: the output registers are m+ 1,· · · , d, and they are never decremented; moreover, registers 1,· · · , m are empty in any reachable halting configuration. Clearly, these conditions do not restrict the generality. We construct the following P system Πsimulating M. The correct behavior of the object associated to the simulated instruction of Mis the following. In the decrement case, we have inr+ 2, out,in2, idle, out,in2, here,out,here (9 steps in total), whereas in the zero-test case, we have the same as before, except that the fourth and the fifth steps are out and here instead of idle and out, respectively. In case of an increment instruction, we get here,here,here, here,in2,here,out,here (8 steps in total). We remark that the first four steps are carried out in the skin, while the last four steps repeat the cases of zero-test and decrement. Maximal Variants of the Set Derivation Modes 77 The value of each register ris represented by the multiplicity of objects orin the skin. For every decrementable register r, there is a rule sending orinto region r+2. However, this rule may only be applied safely in the first step of the simulation of the SUB instruction, as otherwise some other object will also enter the same region as # (either one of e,e0,e00, ˆe, ˆe0, which we will in the following refer to as the guards, or an object associated to the label of the simulated instruction, which we will in the following call a program symbol) forcing an unproductive computation, see the rules in brackets in the tables below. The “correct” target selection for the inner regions normally coincides with that of the program symbol (described above) and no rule is applied there if the program symbol is not there, with the following exceptions. In the first step of simulating an instruction, object eexits membrane 2, as it is the only rule applicable there in this step. In the last step of simulating an instruction, object ¯eis rewritten into ein membrane 2, as it is the only rule applicable there in this step. In the fourth step of the decrement case, the program symbol is idle while object dis erased. The “correct” target selection for the skin coincides with that of the program symbol, and is here if the program symbol is missing in the skin. 78 A. Alhazov, R. Freund, and S. Verlan Π= (O, µ, w1,· · · , wm+2, R1,· · · , Rm+2) where O={or|1≤r≤d}∪{¯p, p |p∈B}∪{p0, p00 ˆp|p∈BADD} ∪ {p0, p−, p0 −, p0, p0 0, p00 0|p∈BSUB}∪{¯e, e, e0, e00,ˆe, ˆe0, d, #}, µ= [ [ ]2· · · [ ]m+2 ]1, w1=l0, w2=e, wr+2 =λ, 1≤r≤m, R1= m+2 [ i=1 (R1,i,s ∪R1,i,#), Ri=Ri,1,s ∪Ri,1,#∪Ri,i,s ∪Ri,i,#,2≤j≤m+ 2, R1,1,s ={e→e0, e0→e00, e00 →ˆe, ˆe→ˆe0, e0→λ} ∪ {p0 0→p00 0|p∈BSUB}∪{¯p→p|p∈B} ∪ {p→˜por|p: (ADD(r), q, s)∈P} ∪ {˜p→p0, p0→p00, p00 →ˆp|p∈BADD}, R1,2,s ={p0→(p−, in2), p0→(p0, in2), p0 −→(p0 −, in2), p00 0→(p00 0, in2) |p∈BSUB}∪{ˆp→(ˆp, in2)|p∈BADD}∪{d→(d, in2)} R1,r+2,s ={or→(or, inr+2)}∪{p→(p, inr+2) |p: (SUB(r), q, s)∈P},1≤r≤m, R1,1,#={p0→#, p00 0→#, p0 −→#|p∈BSUB}∪{ˆp→#|p∈BADD} ∪ {#→#}, R1,2,#={p0 0→(#, in2), e00 →(#, in2)|p∈BSUB} ∪ {¯p→(#, in2)|p∈B}, R1,r+2,#={x→(#, inr+2} | x∈ {e, e0, e00,ˆe, ˆe0} ∪ {p0 0, p0 −|P∈BSUB}∪{¯p|P∈B}} ∪ {p→(#, inr+2)|p: (SUB(i), q, s)∈P, i 6=r} ∪ {p0→(#, inr+2)|p∈BSUB},1≤r≤m, R2,1,s ={e→(e, out)}∪{¯p→(¯p, out)|p∈B} ∪ {p0→(p0 0, out), p−→(p0 −, out)|p∈BSUB}, R2,2,s ={d→λ, ¯e→e} ∪ {| p∈B} ∪ {p00 0→¯s¯e, p0 −→¯q¯e|p: (SUB(r), q, s)∈P} ∪ {ˆp→¯q¯e, ˆp→¯s¯e|p: (ADD(r), q, s)∈P}, R2,1,#={d→(#, out),#→(#, out)}, R2,2,#={p0→#|p∈BSUB}∪{¯p→#|p∈B}, Rr+2,1,s ={p→(p0, out)|p∈BSUB}∪{or→(d, out},1≤r≤m Rr+2,r+2,#={#→(#, out)}, Rr+1,r+1,s =Rr+1,r+1,#=∅. Most trapping rules, given in brackets in the tables below and listed in rule groups Ri,j,#above, are only needed to force the “correct” target selection. The exception are some rules in steps 4 and 5 of the simulation of SUB instructions, Maximal Variants of the Set Derivation Modes 79 needed for verifying that the decrement and the zero test have been performed correctly (the guess is made at step 3 by the program symbol, and is reflected in its subscript). Indeed, if the zero-test is chosen while dis present (signifying that the register was decremented), causing a target conflict: either p0or dwill be anyway rewritten into #. However, if the decrement is chosen while dis absent (signifying that the register was zero), then p−will appear in the skin in step 4 instead of step 5, causing a target conflict: either p0 −or e00 will be anyway rewritten into #. Below we present the tables describing the simulation of instructions of M. An application of one of the rules given in brackets leads to non-halting computations, not contributing to the result. (p: (SUB(r), q, s)) r+ 2 1 2 1 - or→(or, inr+2)e→(e, out) -p→(p, inr+2) [p→(#, ini+2), i6=r] 2p→(p0, out)e→e0- or→(d, out) [e→(#, ini+2)] 3 - p0→(p−, in2) - p0→(p0, in2) d→(d, in2) [p0→#] [e0→(#, ini+2)] 1,- 1,0 2,- 2,0 4e0→e00 d→λ p0→(p0 0, out) [p−→(p0 −, out)] [d→(#, out)] [p0→#] 5e00 →ˆe p0 0→p00 0p−→(p0 −, out) - [p0 −→(p0 −, in2)] e00 →ˆe [p0 −→#] [p0 0→(#, int)] [e00 →(#, int)] [e00 →(#, int)] [for t > 1] [for t > 1] 6p0 −→(p0 −, in2)p00 0→(p00 0, in2) - [p0 −→#] [p00 0→#] [p0 −→(#, ini+2)] [p00 0→(#, ini+2)] 7 ˆe→ˆe0p0 −→¯q¯e p00 0→¯s¯e [ˆe→(#, ini+2)] 8 ˆe0→λ¯q→(¯q, out) ¯s→(¯s, out) [ˆe0→(#, ini+2)] [¯q→#] [¯s→#] 9 ¯q→q¯s→s¯e→e [¯q→(#, int)] [¯s→(#, int)] 80 A. Alhazov, R. Freund, and S. Verlan (p: (ADD(r), q, s)) 1 2 1p→˜pore→(e, out) 2 ˜p→p0- e→e0 3p0→p00 - e0→e00 4p00 →ˆp- e00 →ˆe 5 ˆp→(ˆp, in2) - [ˆp→#] 6 ˆe→ˆe0ˆp→¯x¯e 7 ˆe0→λ¯x→(¯x, out) [¯x→#] 8 ¯x→x¯e→e Auxiliary rules r+ 2 1 2 [# →(#, out)] [# →#] [# →(#, out)] Nearly half of the steps in the preceding constructions is needed for releasing the auxiliary symbol ein the first step of a simulation from membrane 2, yet in our construction, eand its derivatives are needed to control the correct target selection in the skin membrane, and especially to keep the register objects orfrom moving into membrane r+ 2. ut We now show that taking the maximal sets of rules which are applicable, the simulation of SUB-instructions can even be carried out in a deterministic way. Theorem 11. For any register machine M= (d, B, l0, lh, R), with m≤dbeing the number of decrementable registers, we can construct a P system with noncooperative rules Π= (O, µ = [ [ ]2. . . [ ]2m+1 ]1, w1, λ, . . . , λ, R1. . . R2m+1, f = 1) working in the maxrule-derivation mode and simulating the computations of M such that |R1| ≤ 1×ADD1(R)+2×ADD2(R)+4×SUB(R) + 10 ×m+ 3, where ADD1(R)denotes the number of deterministic ADD-instructions in R, ADD2(R)denotes the number of non-deterministic ADD-instructions in R, and SUB(R)denotes the number of SUB-instructions in R. Maximal Variants of the Set Derivation Modes 81 Proof. The contents of the registers r, 1 ≤r≤dis represented by the numbers of objects or, and for the decrementable registers we also use a copy of the symbol o0 r for each copy of the object or. This second copy o0 ris needed during the simulation of SUB-instructions to be able to distinguish between the decrement and the zero test case. For each r, the two objects orand o0 rcan only be affected by the rules or→(λ, inr+1) and o0 r→(λ, inr+1) sending them into the membrane r+ 1 corresponding to membrane r(and at the same time erasing them; in fact, we could also leave them in the membrane unaffected forever as a garbage). These are already two rules, so any other combination of rules with different targets has to contain at least three rules. One of the main ideas of the proof construction is that in the skin membrane the label pof an ADD-instruction is represented by the three objects pand e, e0, and the label pof any SUB-instruction is represented by the eight objects p, e, e0, e00, dr, d0 r,˜ dr,˜ dr 0. Hence, for each p∈(B\ {lh}) we define R(p) = pee0for p∈BADD and R(p) = pee0e00drd0 r˜ dr˜ dr 0for p∈BSUB as well as R(lh) = λ; as initial multiset w1in the skin membrane, we take R(l0). O={or|1≤r≤d}∪{o0 r|1≤r≤m} ∪ (B\ {lh}) ∪ndr, d0 r,˜ dr,˜ dr 0|1≤r≤mo∪ {e, e0, e00} An ADD-instruction p: (ADD(r), q, s) is simulated by the rules p→R(q)or and p→R(s)oras well as the rules e→λand e0→λ. This combination of three rules supercedes any combination of rules or→(λ, inr+1) and o0 r→(λ, inr+1), for some 1 ≤r≤m. A SUB-instruction p: (SUB(r), q, s) is simulated in two steps as follows: 1. In R1, for the first step we take one of the following tuple of rules p→(p, inr+1), dr→(λ, inr+1), d0 r→(λ, inr+1), ˜ dr→(λ, inr+1), or→(λ, inr+1), o0 r→(λ, inr+1); p→(p, inm+r+1), dr→(λ, inm+r+1), d0 r→(λ, inm+r+1), ˜ dr→(λ, inm+r+1), ˜ dr 0→(λ, inm+r+1); the application of the rules or→(λ, inr+1), o0 r→(λ, inr+1) in contrast to the application of the rule ˜ dr 0→(λ, inm+r+1) determines whether the first or the second tuple of rules has to be chosen. Here it becomes clear why we have to use the two register symbols orand o0 r, as we have to guarantee that the target r+ 1 cannot be chosen if none of these symbols is present, as in this case then only four rules could be chosen in contrast to the five rules for the zero test case. On the other hand, if some of these symbols orand o0 rare present, then six rules are applicable superceding the five rules which could be used for the zero test case. 2. In the second step, the following three or four rules, again superceding any combination of rules or→(λ, inr+1) and o0 r→(λ, inr+1) for some 1 ≤r≤m, are used in the skin membrane: e→λ,e0→λ,e00 →λ, and in the decrement case also the rule ˜ dr 0→λ. 82 A. Alhazov, R. Freund, and S. Verlan In the second step, we either find the the symbol pin membrane r+ 1, if a symbol ortogether with its copy o0 rhas been present for decrementing or in membrane m+r+ 1, if no symbol orhas been present (zero test case). In the decrement case, the following rule is used in Rr+1:p→(R(q), out). In the zero test case, the following rule is used in Rm+r+1:p→(R(s), out). We finally point out that the simulation of the SUB-instructions works deterministically, hence, although the P system itself is not deterministic syntacticly, it works in a deterministic way if the underlying register machine is deterministic. ut 10 Conclusion and Future Work It is not very surprising that the proofs we have checked in the preceding sections also work for the derivation mode smax, as many constructions elaborated for the derivation mode max just “break down” maximal parallelism to near sequentiality in order to work for the simulation of register machines. On the other hand, we also have shown that due to this fact some variants of P systems become even stronger with the modes smax and maxrule. •There are many models of P systems for which the maximally parallel derivation mode has been used, especially for showing computational completeness. •As we have seen by careful inspection of several proofs for computational completeness, many results established with using the maximally parallel derivation mode literally hold true as well for the derivation modes smax and maxrule. •Many other constructions working in the maximally parallel derivation mode have to be checked carefully if they work for the derivation modes smax and maxrule, too. •For some proofs having been established in the maximally parallel derivation mode we might need completely new proofs or proof techniques for the setmaximally parallel derivation mode; one such example is the proof for P systems with target selection. •Some variants of P systems become even stronger with the mode smax; as already pointed out by Gheorghe P˘aun, P systems with non-cooperative rules and atomic promoters are computationally complete with the smax-mode, also see [10], and in this paper we have shown a new proof for this computational completeness result and even shown a similar result for P systems with noncooperative rules and atomic inhibitors. •On the other hand, eventually, some results stablished in the maximally parallel derivation mode are not valid any more for the set-maximally parallel derivation mode. Maximal Variants of the Set Derivation Modes 83 References 1. A. Alhazov, B. Aman, R. Freund, and Gh. P˘aun. Matter and anti-matter in membrane systems. In Proceedings of the Twelfth Brainstorming Week on Membrane Computing, pages 1–26, 2014. 2. A. Alhazov and R. Freund. P systems with toxic objects. In M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sos´ık, and C. Zandron, editors, Membrane Computing - 15th International Conference, CMC 2014, Prague, Czech Republic, August 20–22, 2014, Revised Selected Papers, volume 8961 of Lecture Notes in Computer Science, pages 99–125. Springer, 2014. 3. A. Alhazov and R. Freund. Small catalytic P systems. In M. J. Dinneen, editor, Proceedings of the Workshop on Membrane Computing 2015 (WMC2015), (Satellite workshop of UCNC2015), August 2015, volume CDMTCS-487 of CDMTCS Research Report Series. Centre for Discrete Mathematics and Theoretical Computer, ScienceDepartment of Computer Science University of Auckland, Auckland, New Zealand, 2015. 4. A. Alhazov, R. Freund, H. Heikenw¨alder, M. Oswald, Yu. Rogozhin, and S. Verlan. Sequential P systems with regular control. In E. Csuhaj-Varj´u, M. Gheorghe, G. Rozenberg, A. Salomaa, and Gy. Vaszil, editors, Membrane Computing - 13th International Conference, CMC 2012, Budapest, Hungary, August 28-31, 2012, Revised Selected Papers, volume 7762 of Lecture Notes in Computer Science, pages 112–127. Springer, 2013. 5. H. Burkhard. Ordered firing in petri nets. Elektronische Informationsverarbeitung und Kybernetik, 17(2/3):71–86, 1981. 6. R. Freund and Gh. P˘aun. How to obtain computational completeness in P systems with one catalyst. In T. Neary and M. Cook, editors, Proceedings Machines, Computations and Universality 2013, MCU 2013, Z¨urich, Switzerland, September 9-11, 2013, volume 128 of EPTCS, pages 47–61, 2013. 7. R. Freund and S. Verlan. A formal framework for static (tissue) P systems. In G. Eleftherakis, P. Kefalas, Gh. P˘aun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing. 8th International Workshop, WMC 2007 Thessaloniki, Greece, June 25-28, 2007. Revised Selected and Invited Papers, volume 4860 of Lecture Notes in Computer Science, pages 271–284. Springer, 2007. 8. P. Frisco and G. Govan. P systems with active membranes operating under minimal parallelism. In M. Gheorghe, Gh. P˘aun, G. Rozenberg, A. Salomaa, and S. Verlan, editors, Membrane Computing - 12th International Conference, CMC 2011, Fontainebleau, France, August 23-26, 2011, Revised Selected Papers, volume 7184 of Lecture Notes in Computer Science, pages 165–181. Springer, 2011. 9. K. Krithivasan, Gh. P˘aun, and A. Ramanujan. On controlled P systems. In L. Valencia-Cabrera, M. Garc´ıa-Quismondo, L. Mac´ıas-Ramos, M. Mart´ınez-del- Amor, Gh. P˘aun, and A. Riscos-N´u˜nez, editors, Proceedings 11th Brainstorming Week on Membrane Computing, Sevilla, 4–8 February 2013, pages 137–151. F´enix Editora, Sevilla, 2013. 10. L. Pan, Gh. P˘aun, and B. Song. Flat maximal parallelism in P systems with promoters. Theoretical Computer Science, 2015, to appear. 11. D. Sburlan. Further results on P systems with promoters/inhibitors. International Journal of Foundations of Computer Science, 17(1):205–221, 2006. 12. P. Sos´ık and M. Langer. Small catalytic P systems simulating register machines. Theoretical Computer Science, accepted, 2015.