Catalytic P Systems with Weak Priority of Catalytic Over Non-catalytic Rules

Catalytic P Systems with Weak Priority of Catalytic Over Non-catalytic Rules Artiom Alhazov1, Rudolf Freund2, and Sergiu Ivanov3 1Vladimir Andrunachievici Institute of Mathematics and Computer Science Academiei 5, Chis ,in˘au, MD-2028, Moldova a[email protected] 2Faculty of Informatics, TU Wien Favoritenstraße 9–11, 1040 Wien, Austria [email protected] 3IBISC, Univ ´ Evry, Paris-Saclay University 23, boulevard de France 91034 ´ Evry, France [email protected].fr Summary. Catalytic P systems are among the first variants of membrane systems ever considered in this area. This variant of systems also features some prominent computational complexity questions, and in particularly the problem of using only one catalyst: is one catalyst enough to allow for generating all recursively enumerable sets of multisets? Several additional ingredients have been shown to be sufficient for obtaining even computational completeness with only one catalyst. In this paper we show that one catalyst is sufficient for obtaining even computational completeness if catalytic rules have weak priority over the non-catalytic rules. 1 Introduction Membrane systems were introduced in [8] as a multiset-rewriting model of computing inspired by the structure and the functioning of the living cell. During two decades now membrane computing has attracted the interest of many researchers, and its development is documented in two textbooks, see [9] and [10]. For actual information see the P systems webpage [12] and the issues of the Bulletin of the International Membrane Computing Society and of the Journal of Membrane Computing. One basic feature of P systems already presented in [8] is the maximally parallel derivation mode, i.e., using non-extendable multisets of rules in every derivation step. The result of a computation can be extracted when the system halts, i.e., when no rule is applicable any more. Catalysts are special symbols which allow only one object to evolve in its context (in contrast to promoters) and in their 22 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov basic variant never evolve themselves, i.e., a catalytic rule is of the form ca →cv, where cis a catalyst, ais a single object and vis a multiset of objects. In contrast, non-catalytic rules in catalytic P systems are non-cooperative rules of the form a→v. From the beginning, the question how many catalysts are needed for obtaining computational completeness has been one of the most intriguing challenges regarding (catalytic) P systems. In [3] it has already been shown that two catalysts are enough for generating any recursively enumerable set of multisets, without any additional ingredients like a priority relation on the rules as used in the original definition. As already known from the beginning, without catalysts only regular (semi-linear) sets can be generated when using the standard halting mode, i.e., a result is extracted when the system halts with no rule being applicable any more. As shown, for example, in [5], using various additional ingredients, i.e., additional control mechanisms, one catalyst can be sufficient: in P systems with label selection, only rules from one set of a finite number of sets of rules in each computation step are used; in time-varying P systems, the available sets of rules change periodically with time. On the other hand, for catalytic P systems with only one catalyst a lower bound has been established in [6]: P systems with one catalyst can simulate partially blind register machines, i.e., they can generate more than just semi-linear sets. In this paper we now return to the idea of using a priority relation on the rules, but take only a very weak form of such a priority relation: we only require that overall in the system catalytic rules have weak priority over non-catalytic rules. This means that the catalyst cmust not stay idle if the current configuration contains an object awith which it may cooperate in a rule ca →cv; all remaining objects evolve in the maximally parallel way with non-cooperative rules. On the other hand, if the current configuration does not contain an object awith which the catalyst cmay cooperate in a rule ca →cv,cmay stay idle and all objects evolve in the maximally parallel way with non-cooperative rules. Even without using more than this weak priority of catalytic rules over the non-catalytic (noncooperative) rules, computational completeness can be established for catalytic P systems with only one catalyst, which is the main result of our paper. 2 Definitions For an alphabet V, by V∗we denote the free monoid generated by Vunder the operation of concatenation, i.e., containing all possible strings over V. The empty string is denoted by λ. Amultiset Mwith underlying set Ais a pair (A, f) where f:A→Nis a mapping. If M= (A, f) is a multiset then its support is defined as supp(M) = {x∈A|f(x)>0}. A multiset is empty (respectively finite) if its support is the empty set (respectively a finite set). If M= (A, f) is a finite multiset over Aand supp(M) = {a1, . . . , ak}, then it can also be represented by the string af(a1) 1. . . af(ak) kover the alphabet {a1, . . . , ak}, and, moreover, all permutations of Catalytic P Systems with Weak Priority of Catalytic Rules 23 this string precisely identify the same multiset M. For further notions and results in formal language theory we refer to textbooks like [2] and [11]. 2.1 Register Machines Register machines are well-known universal devices for computing (or generating or accepting) sets of vectors of natural numbers. Definition 1. Aregister machine is a construct 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: •p: (ADD (r), q, s), with p∈B\ {lh},q, s ∈B,1≤r≤m. Increase the value of register rby one, and non-deterministically jump to instruction qor s. •p: (SUB (r), q, s), with p∈B\ {lh},q, s ∈B,1≤r≤m. If the value of register ris not zero then decrease the value of register rby one (decrement case) and jump to instruction q, otherwise jump to instruction s (zero-test case). •lh:HALT . Stop 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. In the accepting case, a computation starts with the input of an l-vector of natural numbers in its first lregisters and by executing the first instruction of P(labeled with l0); it terminates with reaching the HALT-instruction. Without loss of generality, we may assume all registers to be empty at the end of the computation. In the generating case, a computation starts with all registers being empty and by executing the first instruction of P(labeled with l0); it terminates with reaching the HALT -instruction and the output of a k-vector of natural numbers in its last kregisters. Without loss of generality, we may assume all registers except the last koutput registers to be empty at the end of the computation. In the computing case, a computation starts with the input of a l-vector of natural numbers in its first lregisters and by executing the first instruction of 24 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov P(labeled with l0); it terminates with reaching the HALT -instruction and the output of a k-vector of natural numbers in its last kregisters. Without loss of generality, we may assume all registers except the last koutput registers to be empty at the end of the computation. 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. Mis called deterministic if the ADD-instructions all are of the form p: (ADD (r), q). For useful results on the computational power of register machines, we refer to [7]; for example, to prove our main theorem, we need the following formulation of results for register machines generating or accepting recursively enumerable sets of vectors of natural numbers with kcomponents or computing partial recursive relations on vectors of natural numbers: Proposition 1. Deterministic register machines can accept any recursively enumerable set of vectors of natural numbers with lcomponents using precisely l+ 2 registers. Without loss of generality, we may assume that at the end of an accepting computation all registers are empty. Proposition 2. Register machines can generate any recursively enumerable set of vectors of natural numbers with kcomponents using precisely k+2 registers. Without loss of generality, we may assume that at the end of an accepting computation the first two registers are empty, and, moreover, on the output registers, i.e., the last kregisters, no SUB-instruction is ever used. Proposition 3. Register machines can compute any partial recursive relation on vectors of natural numbers with lcomponents as input and vectors of natural numbers with kcomponents as output using precisely l+ 2 + kregisters, where without loss of generality, we may assume that at the end of a successful computation the first l+ 2 registers are empty, and, moreover, on the output registers, i.e., the last kregisters, no SUB-instruction is ever used. In all cases it is essential that the output registers never need to be decremented. 2.2 Partially Blind Register Machines We now consider one-way nondeterministic machines which have registers allowed to hold positive or negative integers and which accept by final state with all registers being zero. Such machines are called blind if their actions depend on state and input alone and not on the register configuration. They are called partially blind if they block when any register is negative (i.e., only non-negative register contents is allowed) but do not know whether or not any of the registers contains zero. Catalytic P Systems with Weak Priority of Catalytic Rules 25 Definition 2. Apartially blind register machine is a construct 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: •p: (ADD (r), q, s), with p∈B\ {lh},q, s ∈B,1≤r≤m. Increase the value of register rby one, and non-deterministically jump to instruction qor s. •p: (SUB (r), q), with p∈B\ {lh},q∈B,1≤r≤m. If the value of register ris not zero then decrease the value of register rby one and jump to instruction l2, otherwise abort the computation. •lh:HALT . Stop the execution of the register machine. Again, a configuration of a partially blind 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. A computation works as for a register machine, yet with the restriction that a computation is aborted if one tries to decrement a register which is zero. Moreover, computing, accepting or generating now also requires all registers (except output registers) to be empty at the end of the computation. Example 1. In [6] it was shown that the vector set S={(n, m)|0≤n, n ≤m≤2n} (which is not semi-linear) can be generated by a P system with only one catalyst and 19 rules. 2.3 Catalytic P Systems As in [6], the following definition cites Definition 4.1 in Chapter 4 of [10]. Definition 3. An extended catalytic P system of degree m≥1is a construct Π= (O, C, µ, w1, . . . , wm, R1, . . . , Rm, i0) where •Ois the alphabet of objects; 26 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov •C⊆Ois the alphabet of catalysts; •µis a membrane structure of degree mwith membranes labeled in a one-to-one manner with the natural numbers 1, . . . , m; •w1, . . . , wm∈O∗are the multisets of objects initially present in the mregions of µ; •Ri,1≤i≤m, are finite sets of evolution rules over Oassociated with the regions 1,2, . . . , m of µ; these evolution rules are of the forms ca →cv or a→v, where cis a catalyst, ais an object from O\C, and vis a string from ((O\C)× {here, out, in})∗; •i0∈ {0,1, . . . , m}indicates the output region of Π. The membrane structure and the multisets in Πconstitute a configuration of the P system; the initial configuration is given by the initial multisets w1, . . . , wm. A transition between configurations is governed by the application of the evolution rules, which is done in the maximally parallel way, i.e., only applicable multisets of rules which cannot be extended by further rules are to be applied to the objects in all membrane regions. The application of a rule u→vin a region containing a multiset Mresults in subtracting from Mthe multiset identified by u, and then in adding the multiset identified by v. The objects can eventually be transported through membranes due to the targets in and out. We refer to [10] for further details and examples. The P system continues with applying multisets of rules in the maximally parallel way until there remain no applicable rules in any region of Π. Then the system halts. We consider the number of objects from O\Ccontained in the output region i0at the moment when the system halts as the result of the underlying computation of Π. The system is called extended since the catalytic objects in C are not counted to the result of a computation. Yet as often done in the literature, in the following we will omit the term extended and just speak of catalytic P systems, especially as we will restrict ourselves to P systems with only one catalyst. The set of results of all computations possible in Πis called the set of natural numbers generated by Πand it is denoted by N(Π) if we only count the total number of objects in the output membrane; if we distinguish between the multiplicities of different objects, we obtain a set of vectors of natural numbers denoted by P s(Π). Remark 1. As in this paper we only consider catalytic P systems with only one catalyst, without loss of generality, we can restrict ourselves to one-membrane catalytic P systems with the single catalyst in the skin membrane, by taking into account the well-known flattening process, e.g., see [4]. Remark 2. Finally, we make the convention that a one-membrane catalytic P system with the single catalyst in the skin membrane and with internal output in the skin membrane, not taking into account the single catalyst cfor the results, throughout the rest of the paper will be described without specifying the trivial membrane structure or the output region (assumed to be the skin membrane), i.e., we will just write Catalytic P Systems with Weak Priority of Catalytic Rules 27 Π= (O, {c}, w, R) where Ois the set of objects, cis the single catalyst, wis the initial input specifying the initial configuration, and Ris the set of rules. As already mentioned earlier, the following result was shown in [6], establishing a lower bound for the computational power of catalytic P systems with only one catalyst: Proposition 4. Catalytic P systems with only one catalyst have at least the computational power of partially blind register machines. 3 Weak Priority of Catalytic Rules In this paper we now study catalytic P systems with only one catalyst in which the catalytic rules have weak priority over the non-catalytic rules. Example 2. To illustrate this weak priority of catalytic rules over the non-catalytic rules, consider the rules ca →cb and a→d. If the current configuration contains k > 0 copies of a, then the catalytic rule ca →cb must be applied to one of the copies, while the rest of objects amay be taken up by the non-catalytic rule a→d. In particular, if k= 1, only ca →cb may be applied. We would like to highlight the fact that weak priority of catalytic rules is much weaker than the general weak priority, as the priority relation is only constrained by the types of rules. Remark 3. The reverse weak priority, i.e., non-catalytic rules having priority over catalytic rules, is useless, since it is equivalent to removing all catalytic rules for which there are non-catalytic rules with the same symbol on the left-hand side of the rule. In that way we just end up with an even restricted variant of P systems with only one catalyst. 3.1 Computational Completeness with Weak Priority In this section, we show that catalytic P systems with one catalyst only and with weak priority of catalytic rules are computationally complete. Theorem 1. Catalytic P systems with only one catalyst and with weak priority of catalytic rules over the non-cooperative rules are computationally complete. Proof. Given an arbitrary register machine M= (m, B, l0, lh, P ) we will construct a corresponding catalytic P system with one membrane and one catalyst Π= (O, {c}, w, R) simulating M. Without loss of generality, we may assume that, depending on its use as an accepting or generating or computing device, the register machine M, as stated in Proposition 1, Proposition 2, and Proposition 3, fulfills 28 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov the condition that on the output registers we never apply any SUB-instruction. The following proof is given for the most general case of a register machine computing any partial recursive relation on vectors of natural numbers with lcomponents as input and vectors of natural numbers with kcomponents as output using precisely l+2+kregisters, where without loss of generality, we may assume that at the end of a successful computation the first l+ 2 registers are empty, and, moreover, on the output registers, i.e., the last kregisters, no SUB-instruction is ever used. In fact, the proof works for any number nof decrementable registers, no matter how many of them are the linput registers and the working registers, respectively. The main idea behind our construction is that all the symbols except the catalyst cand the output symbols (representing the contents of the output registers) go through a cycle of length 2nwhere nis the number of decrementable registers of the simulated register machine. When the symbols are traversing the r-th section of the nsections of length 2, they “know” that they are to probably simulate a SUB-instruction on register rof the register machine M. The alphabet Oof symbols includes register symbols (ar,2i−1),(ar,2i) for every decrementable register rof the register machine and only the register symbol arfor each of the koutput registers r,m−k+ 1 ≤r≤m, the state symbols (p, 2i−1),(p, 2i), 1 ≤i≤n, for every ADD-instruction of the register machine as well as, for p∈BSUB(r)the state symbols (p, 2i−1),(p, 2i) for 1 ≤i≤r as well as (p, 2j−1)−and (p, 2j)0for r+ 1 ≤j≤nfor every SUB-instruction p: (SUB(r), q, s) of the register machine, i.e., p∈BSUB(r), where BSUB(r)denotes the set of labels of all SUB-instruction p: (SUB(r), q, s) of decrementable registers r. Moreover, we use decrement witness symbols λrfor every decrementable register r, as well as the catalyst cand the trap symbol #. Observing that n=m−k, in total we get the following set of objects: O={ar|n+ 1 ≤r≤m} ∪ {(ar, i)|1≤r≤n, 1≤i≤2n} ∪ {λr|1≤r≤n} ∪ {(p, i)|p∈BADD,1≤i≤2n} ∪ {(p, i)|p∈BSUB(r),1≤i≤2r} ∪ {(p, i)−,(p, i)0|p∈BSUB(r),2r+ 1 ≤i≤2n} ∪ {c, #}. BADD denotes the set of labels of ADD-instructions. The starting configuration of Πis w=c(l0,1)α0, where l0is the starting label of the machine and α0is the multiset encoding the initial values of the registers. Catalytic P Systems with Weak Priority of Catalytic Rules 29 All register symbols ar, 1 ≤r≤n, representing the contents of decrementable registers, are equipped with the rules evolving them throughout the whole cycle: (ar, i)→(ar, i + 1),1≤r≤2n−1; (ar,2n)→(ar,1).(1) The construction also includes the trap rule # →#: once the trap symbol # is introduced, it will always keep the system busy and prevent it from halting and thus from producing a result. For simulating ADD-instructions we also need the following rules: Increment p: (ADD(r), q, s): The (variants of the) symbol pcycles together with all the other symbols, always involving the catalyst: c(p, i)→c(p, i + 1),1≤i≤2n−1.(2) At the end of the cycle, the register is incremented and the non-deterministic jump to qor soccurs: for rbeing a decrementable register, we take c(p, 2n)→c(q, 1)(ar,1), c(p, 2n)→c(s, 1)(ar,1),(3) whereas for rbeing a register never to be decremented, we take c(p, 2n)→c(q, 1)ar, c(p, 2n)→c(s, 1)ar(4) The output symbols need not undergo the cycle, in fact, they must not do that because otherwise the computation would never stop. When the computation of the register machine halts, only output symbols will be present, as we have assumed that at the end of a computation all decrementable registers will be empty, i.e., no cycling symbols will be present any more in the P system. Finally, we have to mention that if qor sis the final label lh, then we take λinstead, which means that also the P system will halt, because, as already explained above, the only symbols left in the configuration will be output symbols, for which no rules exist. The state symbol is not allowed to evolve without the catalyst: (p, i)→#,1≤i≤2n. (5) Hence, in that way it is guaranteed that the catalyst cannot be used in another way, i.e., affecting a symbol (ar, i) as explained below during the simulation of a SUB-instruction on register r. Decrement and zero-test p: (SUB(r), q, s): The simulation of a SUB instruction is carried out in two steps of the cycle, i.e., in steps 2r−1 and 2r. Before reaching simulation phase r, i.e., step 2r−1, the state symbol goes through the cycle, necessarily involving the catalyst: