(Tissue) P Systems with Anti-Membranes

(Tissue) P Systems with Anti-Membranes Artiom Alhazov1, Rudolf Freund2, Sergiu Ivanov3 1Vladimir Andrunachievici Institute of Mathematics and Computer Science Academiei 5, Chi¸sin˘au, MD-2028, Moldova E-mail: [email protected] 2TU Wien, Institut f¨ur Logic and Computation Favoritenstraße 9–11, 1040 Wien, Austria E-mail: [email protected] 3IBISC, Universit´e ´ Evry, Universit´e Paris-Saclay 23, boulevard de France, 91034 ´ Evry, France E-mail: [email protected] Summary. The concept of a matter object being annihilated when meeting its corresponding anti-matter object is taken over for membranes as objects and anti-membranes as the corresponding annihilation counterpart in P systems. Natural numbers can be represented by the corresponding number of membranes with a specific label. Computational completeness in this setting then can be obtained with using only elementary membrane division rules, without using objects. A similar result can be obtained for tissue P systems with cell division rules and cell / anti-cell annihilation rules. In both cases, as derivation modes we may take the standard maximally parallel derivation modes as well as any of the maximally parallel set derivation modes (non-extendable (multi)sets of rules, (multi)sets with maximal number of rules, (multi)sets of rules affecting the maximal number of objects). 1 Introduction The basic model of P systems as introduced in [12] can be considered as a distributed multiset rewriting system, where all objects – if possible – evolve in parallel in the membrane regions and may be communicated through the membranes. Overviews on the field of P systems can be found in the monograph [13] and the handbook of membrane systems [14]; for actual news and results we refer to the P systems webpage [16] as well as to the Bulletin of the International Membrane Computing Society. Computational completeness (computing any partial recursive relation on nonnegative integers) can be obtained with using cooperative rules or with catalytic rules (possibly) together with non-cooperative rules. We recall that noncooperative rules have the form a→w, where ais a symbol and wis a multiset, 30 A. Alhazov, R. Freund, and S. Ivanov catalytic rules have the form ca →cw, where the symbol cis called the catalyst, and cooperative rules have no restrictions on the form of the left-hand side. Without additional control mechanisms, at least two catalysts are needed, see [7]. Using specific control mechanisms, as for example, rule labels or target agreement, only one catalyst is needed, for example, see [6, 8, 9]. In [2, 1], another concept to avoid cooperative rules is investigated: for any object a(matter), its anti-object (anti-matter) a−is considered together with the corresponding annihilation rule aa−→λ, which is assumed to exist in all membranes; this annihilation rule is assumed to be a special non-cooperative rule having priority over all other rules in the sense of weak priority (e.g., see [3], i.e., other rules then also may be applied if objects cannot be bound by some annihilation rule any more). For spiking neural P systems, the idea of anti-matter has been introduced in [11] with anti-spikes as anti-matter objects. In [5] the power of anti-matter for solving NP-complete problems is exhibited. Although, as expected (for example, compare with the Geffert normal forms, see [15]), the annihilation rules are rather powerful, it is still surprising that using matter/anti-matter annihilation rules as the only non-cooperative rules, with the annihilation rules having weak priority, computational completeness can already be obtained without using any catalyst, see [2, 1], whereas usually at least one catalyst is needed even when using other control mechanisms, for example, see [2]. Natural numbers can be represented by the corresponding number of membranes with a specific label. Hence, in this paper we take over the idea of antiobjects for membranes, i.e., for every membrane [ ]hwe take the anti-membrane [ ]h−and the membrane / anti-membrane annihilation rule [ ]h[ ]h−→λ. In the simplest case, we only use elementary membranes, but no objects, and elementary membrane division, i.e., rules of the form [ ]h→[ ]h0[ ]h00 , possibly also allowing membrane renaming rules of the form [ ]h→[ ]h0or membrane deletion rules of the form [ ]h→λ. In this setting, computational completeness then can be obtained with using only elementary membrane division rules, without using objects, together with anti-membranes and membrane / anti-membrane annihilation rules. Natural numbers can also be represented by the corresponding number of cells with a specific label. Hence, a similar computational completeness result can also be obtained for tissue P systems with cell division rules and cell / anti-cell annihilation rules. In both cases, as derivation modes we may take the standard maximally parallel derivation modes as well as any of the maximally parallel set derivation modes (non-extendable (multi)sets of rules, (multi)sets with maximal number of rules, (multi)sets of rules affecting the maximal number of objects). 2 Prerequisites The set of integers is denoted by Z, and the set of non-negative integers by N. Given an alphabet V, a finite non-empty set of abstract symbols, the free monoid (Tissue) P Systems with Anti-Membranes 31 generated by Vunder the operation of concatenation is denoted by V∗. The elements of V∗are called strings, the empty string is denoted by λ, and V∗\{λ}is denoted by V+. For an arbitrary alphabet V={a1, . . . , an}, the number of occurrences of a symbol aiin a string xis denoted by |x|ai, while the length of a string x is denoted by |x|=Pai∈V|x|ai. The Parikh vector associated with xwith respect to a1, . . . , anis (|x|a1,...,|x|an). The Parikh image of an arbitrary language L over {a1, . . . , an}is the set of all Parikh vectors of strings in L, and is denoted by Ps(L). For a family of languages FL, the family of Parikh images of languages in FL is denoted by PsFL, while for families of languages over a one-letter (dletter) alphabet, the corresponding sets of non-negative integers (d-vectors with non-negative components) are denoted by NFL (NdFL ). A (finite) multiset over a (finite) alphabet V={a1, . . . , an}, is a mapping f: V→Nand can be represented by haf(a1) 1, . . . , af(an) nior by any string xfor which (|x|a1,...,|x|an) = (f(a1), . . . , f(an)). In the following we will not distinguish between a vector (m1, . . . , mn), a multiset ham1 1, . . . , amn nior a string x having (|x|a1,...,|x|an)=(m1, . . . , mn). Fixing the sequence of symbols a1, . . . , anin an alphabet Vin advance, the representation of the multiset ham1 1, . . . , amn niby the string am1 1. . . amn nis unique. The set of all finite multisets over an alphabet Vis denoted by V◦. The family of regular and recursively enumerable string languages is denoted by REG and RE, respectively. For more details of formal language theory the reader is referred to the monographs and handbooks in this area as [4] and [15]. Register machines Aregister machine is a tuple M= (m, B, l0, lh, P), where mis the number of registers, Bis a set of labels, l0∈Bis the initial label, lh∈Bis the final label, and Pis the set of instructions bijectively labeled by elements of B. The instructions of Mcan be of the following forms: •l1: (ADD(j), l2, l3), with l1∈B\{lh},l2, l3∈B, 1 ≤j≤m. Increases the value of register jby one, followed by a non-deterministic 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, the value of register jis decreased by one, followed by a jump to instruction l2. The two cases of this instruction are usually called zero-test and decrement, respectively. •lh:HALT. Stops the execution of the register machine. Aconfiguration of a register machine is described by the contents of each register and by the value of the current label, which indicates the next instruction to be executed. Computations start by executing the instruction l0of P, and terminate with reaching the HALT-instruction lh. For useful results on the computational power of register machines, we refer to [10]. 32 A. Alhazov, R. Freund, and S. Ivanov 3 P Systems with Active Membranes and Anti-Membranes For using anti-matter as a frontier of tractability, we refer to [5], where some standard definition of P systems with active membranes can be found. We here consider a special rather restricted model, where no objects are used and inside the skin membrane only the following types of rules for elementary membranes are used: elementary membrane division [ ]h→[ ]h0[ ]h00 the elementary membrane [ ]his divided into two membranes, possibly changing the label hof the parent membrane [ ]hto two new labels h0, h00 for the child membranes [ ]h0and [ ]h00 changing membrane label [ ]h→[ ]h0 the label hof the elementary membrane [ ]his changed to h’ elementary membrane deletion [ ]h→λ the elementary membrane [ ]his deleted membrane / anti-membrane annihilation [ ]h[ ]h−→λ the elementary membrane [ ]hand its corresponding anti-membrane [ ]h0an- nihilate each other Formally, a P system with active membranes and anti-membranes (a PAMS for short) is a construct Π= (H∪ {0},[ ]0, w0, R) where His the set of membrane labels used in the membrane rules specified in R, [ ]0denotes the skin membrane enclosing the initial set of elementary membranes w0with labels from H, and R is the set of rules of the forms described above, with the labels of the elementary membranes taken from H. In any computation step of Πa multiset of rules is chosen from the set Rin such a way that no further rule can be added to it so that the obtained multiset would still be applicable to the existing membranes in the skin membrane. We emphasize that membrane / anti-membrane annihilation rules have weak priority over all other rules, i.e., as long as membrane / anti-membrane annihilation rules may bind some membranes, other rules are not allowed to yet be taken into the multiset of rules constructed to be maximal. Aconfiguration of the system can be represented by the membranes inside the skin membrane. Starting from a given initial configuration and applying evolution rules as described above, we get transitions among configurations; a sequence of transitions forms a computation. A computation is halting if it reaches a configuration where no rule can be applied any more. In the generative case, a halting computation has associated a result, in the form of the number of membranes with the same labels present in the skin membrane; their numbers represents a vector of natural numbers. In the accepting case, all (vectors of) non-negative integers are accepted whose input, given as the corresponding numbers of membranes in the skin membrane in addition to w0, leads (Tissue) P Systems with Anti-Membranes 33 to a halting computation. The set of non-negative integers and the set of (Parikh) vectors of non-negative integers generated/accepted as results of halting computations in Πare denoted by Nδ(Π) and Psδ(Π), respectively, with δ∈ {gen, acc}. The corresponding families of sets of non-negative integers and the sets of vectors of non-negative integers generated/accepted by PAMSs are denoted by Nδ(PAMS) and Psδ(PAMS), respectively. 4 Tissue P Systems with Cell Division and Anti-Cells Instead of considering elementary membranes inside the skin membrane, we may also consider cells floating in a common environment. Then instead of antimembranes, we consider anti-cells, i.e., cells with the anti-label. Again, we here consider a special rather restricted model, where no objects are used and only the following types of rules for cells in the tissue P system are used: cell division #h→#h0#h00 the cell #his divided into two cells, possibly changing the label hof the parent cell #hto two new labels h0, h00 for the child cells #h0and #h00 changing cell label #h→#h0 the label hof cell #his changed to h’ cell deletion #h→λ the cell [ ]his deleted cell / anti-cell annihilation #h#h−→λ the cell #hand its corresponding anti-cell #h−annihilate each other Formally, a tissue P system with anti-cells (a tPAMS for short) is a construct Π= (H, w0, R) where His the set of cell labels used in the rules specified in R, w0is the initial set of cells with labels from H, and Ris the set of rules of the forms described above, with the labels of the cells taken from H. In any computation step of Πa multiset of rules is chosen from the set Rin such a way that no further rule can be added to it so that the obtained multiset would still be applicable to the existing cells. We emphasize that again we assume cell /anti-cell annihilation rules to have weak priority over all other rules, i.e., as long as cell / anti-cell annihilation rules may bind some cells, other rules are not allowed to yet be taken into the multiset of rules constructed to be maximal. Aconfiguration of the system can be represented by the currently existing cells. Starting from a given initial configuration and applying evolution rules as described above, we get transitions among configurations; a sequence of transitions forms a computation. A computation is halting if it reaches a configuration where no rule can be applied any more. 34 A. Alhazov, R. Freund, and S. Ivanov In the generative case, a halting computation has associated a result, in the form of the number of cells present in the system; their numbers represents a vector of natural numbers. In the accepting case, all (vectors of) non-negative integers are accepted whose input, given as the corresponding numbers of initial cells in addition to w0, leads to a halting computation. The set of non-negative integers and the set of (Parikh) vectors of non-negative integers generated/accepted as results of halting computations in Πare denoted by Nδ(Π) and P sδ(Π), respectively, with δ∈ {gen, acc}. The corresponding families of sets of non-negative integers and the sets of vectors of non-negative integers generated/accepted by tPAMSs are denoted by Nδ(tPAMS) and P sδ(tPAMS), respectively. 5 Results As a first result, we observe that rules changing membrane label, i.e., [ ]h→[ ]h0, and elementary membrane deletion rules, i.e., [ ]h→λ, are not needed and can be replaced by using only elementary membrane division and suitable membrane / antimembrane annihilation rules. Lemma 1. Rules changing membrane label, i.e., [ ]h→[ ]h0, and elementary membrane deletion rules, i.e., [ ]h→λ, can be simulated by elementary membrane division and membrane / anti-membrane annihilation rules. Proof. A rule changing the membrane label, i.e., [ ]h→[ ]h0, can be simulated by the rules [ ]h→[ ]h0[ ]h00 ,[]h00 →[ ]g[ ]g−, and [ ]g[ ]g−→λ, where h00, g, g−are new labels (separately for each label h). An elementary membrane deletion rule, i.e., [ ]h→λ, can be simulated by the rules [ ]h→[ ]g[ ]g−and [ ]g[ ]g−→λ, where g, g−are new labels (separately for each label h). ut A similar result obviously also holds for tPAMS: rules changing a cell label, i.e., #h→#h0, and cell deletion rules, i.e., #h→λ, are not needed and can be replaced by using only cell division and suitable cell / anti-cell annihilation rules. The corresponding proof verbatim follows the proof of Lemma 1, just replacing the notation [ ]hby #h. Corollary 1. Rules changing cell label, i.e., #h→#h0, and cell deletion rules, i.e., #h→λ, can be simulated by cell division and cell / anti-cell annihilation rules. A PAMS only using elementary membrane division and membrane / antimembrane annihilation rules is called a PAMS in normal form. As an immediate consequence of Lemma 1 we obtain the following normal form theorem: Theorem 1. For every PAMS Πwe can construct a PAMS Π0in normal form such that Nδ(Π) = Nδ(Π0)and P sδ(Π) = P sδ(Π0), with δ∈ {gen, acc}. (Tissue) P Systems with Anti-Membranes 35 A similar normal form result obviously also holds for tPAMS as an immediate consequence of Corollary 1: Corollary 2. For every tPAMS Πwe can construct a tPAMS Π0in normal form such that Nδ(Π) = Nδ(Π0)and P sδ(Π) = P sδ(Π0), with δ∈ {gen, acc}. 5.1 Computational Completeness We now show that PAMSs characterize the families NRE and P sRE, respectively. The main proof idea – as used very often in the area of P systems – is to simulate (the computations of) register machines, as carried out in a similar way in [1] for P systems with anti-matter. Theorem 2. For any Y∈ {N, P s}and δ∈ {gen, acc}, Yδ(PAMS) = Y RE. Proof. Let M= (m, B, l0, lh, P ) be a register machine. We now construct a PAMS Πwhich simulates (the computations of) M: •Π= (H∪ {0},[ ]0, w0, R); •H={r, r−|1≤r≤m} ∪ {l, l0|l∈B} ∪ {#,#−}is the set of labels for the elementary membranes inside the skin membrane; the label r, 1≤r≤m, is for the copies of membrane [ ]rrepresenting the contents of register r; the labels r−are for the corresponding anti-membranes; •in the generating case, initially the skin membrane contains only the elementary membrane [ ]l0; in the accepting case, suitable copies of membranes for representing the input vector are to be added; •Rcontains the rules described in the following. The contents of register ris represented by the number of copies of the elementary membrane [ ]r, 1 ≤r≤m, and for each membrane [ ]rwe also consider the corresponding anti-membrane [ ]r−. The instructions of Mare simulated by the following rules in R1: •l1: (ADD (j), l2, l3), with l1∈B\ {lh},l2, l3∈B, 1 ≤j≤m. Simulated by the rules [ ]l1→[ ]r[ ]l2and [ ]l1→[ ]r[ ]l3. •l1: (SUB (r), l2, l3), with l1∈B\ {lh},l2, l3∈B, 1 ≤r≤m. As rules common for the simulations of all SUB-instructions, we have [ ]r−→[ ]#−, 1 ≤r≤m, and the annihilation rules [ ]r[ ]r−→λ, 1 ≤r≤m, and [ ]#[ ]#−→λ 36 A. Alhazov, R. Freund, and S. Ivanov as well as the trap rules [ ]#−→[ ]#[ ]#and [ ]#→[ ]#[ ]#; these last two rules lead the system into an infinite computation whenever a membrane with one of the trap symbols # or #−is left without being annihilated. The zero test for instruction l1is simulated by the rules [ ]l1→[ ]l1 0[ ]r−and [ ]l0 1→[ ]#[ ]l3. The membrane labeled by #, generated by the second rule [ ]l0 1→[ ]#[ ]l3can only be eliminated if the anti-membrane [ ]r−generated by the first rule [ ]l1 →[ ]l1 0[ ]r−is not annihilated by [ ]r, i.e., only if register ris empty, which allows for applying the rule [ ]r−→[ ]#−and for using the annihilation rule [ ]#[ ]#−→λafterwards in the next derivation step. The decrement case for instruction l1is simulated by the rule [ ]l1→[ ]l2[ ]r−. The anti-membrane [ ]r−either correctly annihilates one copy of membrane [ ]r, thus decrementing the register r, or else traps an incorrect guess by forcing the anti-membrane [ ]r−to evolve to [ ]#−and then to [ ]#[ ]#in the next two steps in case register ris empty. We finally observe that these two remaining derivation steps for trapping the decrement case as well as the remaining derivation step for correctly completing the decrement case or the zero test case do not influence the correct simulation of another SUB-instruction, even on the same register r, as the involved symbols have evolved at least one step before they could influence the symbols being generated by the new simulation sequence. •lh:HALT. Simulated by [ ]lh→λ. When the computation in Mhalts, the membrane [ ]lhis removed, and no further rules can be applied provided the simulation has been carried out correctly, i.e., if no membranes labeled by trap symbols # are present in this situation. The remaining membranes in the system represent the result computed by M.ut For δ∈ {gen, acc}, let us denote the families of sets of non-negative integers and the sets of vectors of non-negative integers generated/accepted by PAMSs in normal form by Nδ(NFPAMS) and Psδ(NFPAMS), respectively. Then, by combining Lemma 1 and Theorem 2, we obtain the following result: Theorem 3. For any Y∈ {N, P s}and δ∈ {gen, acc}, Yδ(NFPAMS) = Y RE. (Tissue) P Systems with Anti-Membranes 37 Similar results obviously also hold for tissue P systems with anti-cells; the corresponding proofs again verbatim follow the proofs of Theorems 2 and 3, just replacing the notation [ ]hby #h. Corollary 3. For any Y∈ {N, P s}and δ∈ {gen, acc}, Yδ(PAMS) = Y RE. Corollary 4. For any Y∈ {N, P s}and δ∈ {gen, acc}, Yδ(NFPAMS) = Y RE. 5.2 Derivation Modes So far, we only have considered the maximally parallel derivation mode. Yet a thorough investigation of the proofs given so far in this section shows that in a successful derivation each rule need only be applied at most once, which means that instead of the maximally parallel derivation mode we can use any of the set derivation modes, where each rule can only be applied once, defined as follows: setmax take a non-extendable set of rules setmaxrules take a non-extendable set of rules with the maximal number of rules possible setmaxobjects take a non-extendable set of rules affecting the maximal number of objects The concept of using the maximal number of rules or objects can also be taken over for the maximally parallel derivation mode: max take a non-extendable multiset of rules maxrules take a non-extendable multiset of rules with the maximal number of rules possible maxobjects take a non-extendable multiset of rules affecting the maximal number of objects Let us now specify the derivation mode γ∈ {max, maxrules, maxobjects, setmax, setmaxrules, setmaxobjects,} as additional subscript to δ,δ∈ {gen, acc}, for denoting the set of natural numbers and the set of vectors of natural numbers obtained by PAMS and tPAMS, i.e., we now write Nγ,δ and P sγ,δ, respectively. Moreover, we use the bracket notation [t]PAMS to indicate that we mean both PAMS and tPAMS, respectively, and in a similar way for PAMS and tPAMS in normal form. With any of these derivation modes, using sets or multisets of rules, we now get the same normal form and computational completeness results as for the maximally parallel derivation mode max as established so far: