Characterizing the Computational Power of Energy-Based P Systems

Characterizing the Computational Power of Energy-Based P Systems Artiom Alhazov1,2, Marco Antoniotti1, Alberto Leporati1 1Universit`a degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336, 20126 Milano, Italy {artiom.alhazov,marco.antoniotti,alberto.leporati}@unimib.it 2Institute of Mathematics and Computer Science Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova [email protected] Summary. We investigate the computational power of energy-based P systems, a model of membrane systems where a fixed amount of energy is associated with each object and the rules transform single objects by adding or removing energy from them. We answer recently proposed open questions about the power of such systems without priorities associated to the rules, for both sequential and maximally parallel modes. We also conjecture that deterministic energy-based P systems are not computationally complete. 1 Introduction Membrane systems (also called P systems) have been introduced in [11] as a class of distributed and parallel computing devices, inspired by the structure and functioning of living cells. Since then, many variants of P systems have been defined in the literature. In what follows we assume the reader is familiar with the basic notions and the terminology underlying P systems. A systematic introduction to the area can be found in [12]; a recent overview of the developments is presented in [13], whereas the latest information can be found in [15]. In this paper we consider energy-based P systems [7, 8, 6], a model of computation in the framework of Membrane Computing in which a given amount of energy is associated to each object, and the energy manipulated during computations is taken into account by means of conservative rules. Let us note in passing that there has been other attempts in the literature to incorporate certain conservation laws in membrane computing. One is purely communicative models, of which the most thoroughly studied is P systems with symport/antiport [10]. In these systems the computation is carried out by moving objects between the regions in groups. To reach computational completeness, the 12 A. Alhazov, M. Antoniotti, A. Leporati workspace is increased by bringing (some types of) objects from the environment, where they can be found in an unbounded supply. Another model is conformon P systems [5], where computations are performed by redistributing energy between objects, than can also be renamed and moved. A feature of these systems is that a different amount of energy may be embedded in the same object at different time steps. Yet another approach is to assign energy to membranes, as in P system with Unit Rules and Energy assigned to Membranes (UREM P systems, for short) [1]. Here the computations are performed by rules renaming and moving an object across a membrane, possibly modifying the energy assigned to that membrane. It has been proved in [1] that UREM P systems working in the sequential mode characterize PsMAT, the family of Parikh sets generated by matrix grammars without appearance checking (and with erasing rules), and that their power is increased to PsRE (the family of recursively enumerable Parikh sets) if priorities are assigned to the rules or the mode of applying the rules is changed to maximally parallel. As stated above, in this paper we consider energy-based P systems, in which energy is assigned to objects in a way that each object from the alphabet is assigned a specific value. Instances of a special symbol are used to denote free energy units occurring inside the regions of the system. The computations are carried out by rules renaming and possibly moving objects, which may consume or release free energy in the region, respecting the energy conservation law (that is, the total amount of energy associated with the objects that appear in the left hand side of a rule is the same as the energy occurring in the right hand side). The result of a computation may be interpreted in many ways: for example, as the amount of free energy units in a designated output region. Also for this model, to give the possibility to reach computational completeness it is necessary (but not sufficient, as we will see) that there may be an unbounded amount of free energy in (at least one) specified region of the system. In [6] it is proved that energy-based P systems working in the sequential way and using a form of local priorities associated to the rules are computationally complete. Without priorities, their behavior can be simulated by vector addition systems, and hence are not universal. However, in [6] the precise characterization of the computational power of energy-based P systems without priorities is left as an open problem. A related open question was whether energy-based P systems can reach computational completeness by working in the maximally parallel mode, without priorities, as it happens with UREM P systems [1]. In this paper we answer these questions, by showing that the power of energybased P systems containing an infinite amount of free energy and without priorities is exactly PsMAT when working in the sequential mode, and PsRE when working in the maximally parallel mode. Nonetheless we will end with another open question: what is the power of energy-based P systems under the restriction of determinism? We conjecture non-universality for this case. The rest of the paper is structured as follows. The next section contains some mathematical preliminaries, to fix the notions, definitions and notations with which Characterizing the Computational Power of Energy-Based P Systems 13 we will work. Section 3 contains our results concerning the characterization of the computational power of energy-based P systems working without priorities, either in the sequential or in the maximally parallel mode. Section 4 contains the conclusions and some discussion on the above mentioned open problem, concerning the computational power of deterministic energy-based P systems. 2 Preliminaries We assume the reader to be familiar with the basics of formal languages; on this subject one may refer to, e.g., [14]. We denote by Nthe set of non-negative integers. An alphabet Vis a finite nonempty set of abstract symbols. Given V, 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+. By |x|we denote the length of the word x over V. Let {a1, . . . , an}be an arbitrary alphabet; the number of occurrences of a symbol aiin xis denoted by |x|ai; the Parikh vector associated with xwith respect to a1, . . . , anis (|x|a1, . . . , |x|an).The Parikh image of a language L over {a1, . . . , an}is the set of all Parikh vectors of strings in L. For a family of languages FL, the family of Parikh images of languages in FL is denoted by PsFL. A finite multiset ⟨m1, a1⟩. . . ⟨mn, an⟩with mi∈N,1≤i≤n, is represented as any string xthe Parikh vector of which with respect to a1, . . . , anis (m1, . . . , mn). The family of recursively enumerable languages is denoted by RE, and the family of context-free languages by CF. The family of all recursively enumerable sets of k-dimensional vectors of non-negative integers can thus be denoted by Ps(k)RE. Since numbers can be seen as one-dimensional vectors, we can replace Ps(1) by N in the notation, thus obtaining NRE. 2.1 Matrix Grammars A context-free matrix grammar (without appearance checking) is a construct G= (N, T, S, M) where Nand Tare sets of non-terminal and terminal symbols, respectively, with N∩T=∅,S∈Nis the start symbol,Mis a finite set of matrices,M={mi|1≤i≤n}, where the matrices miare sequences of the form mi= [mi,1, . . . , mi,ni], ni≥1, 1 ≤i≤n, and the mi,j, 1 ≤j≤ni, 1 ≤i≤n, are context-free productions over (N, T). For mi= [mi,1, . . . , mi,ni] and v, w ∈ (N∪T)∗we define v=⇒miwif and only if there are w0, w1, . . . , wni∈(N∪T)∗ such that w0=v, wni=w, and for each j, 1≤j≤ni,wjis the result of the application of mi,j to wj−1. The language generated by Gis L(G) = {w∈T∗|S=⇒mi1w1. . . =⇒mikwk, wk=w, wj∈(N∪T)∗, mij∈Mfor 1 ≤j≤k, k ≥1}. According to the definitions given in [2], the last matrix can already finish with a terminal word without having applied the whole sequence of productions. The 14 A. Alhazov, M. Antoniotti, A. Leporati family of languages generated by matrix grammars without appearance checking is denoted by MAT. It is known that PsCF ⊂PsMAT ⊂PsRE. Further details about matrix grammars can be found in [2] and in [14]. 2.2 Energy-based P systems Let us now recall the definition of energy-based P systems as given in [8]. An energy-based P system of degree m≥1 is a tuple Π= (A, ε, µ, e, w1, . . . , wm, R1, . . . , Rm, iin, iout) where: •Ais a finite set of objects called the alphabet; •ε:A→Nis a mapping that associates to each object a∈Athe value ε(a) (also denoted by εa), which can be viewed as the “energy value of a”. If ε(a) = ℓ, we also say that object aembeds ℓunits of energy; •µis a description of a tree structure consisting of mmembranes, injectively labeled with elements from the set {1, . . . , m}; •e /∈Ais a special symbol denoting one free energy unit; •wi, for 1 ≤i≤m, specifies multisets (over A∪ {e}) of objects initially present in region i. We will sometimes assume that the number of e’s (but not of objects from A) in some regions of the system is unbounded; •Ri, for 1 ≤i≤m, is a finite set of multiset rewriting rules over A∪ {e} associated with region i. Rules can be of the following types: aek→(b, p) and b→(a, p)ek(1) where a, b ∈A,p∈ {here, in(j), out |1≤j≤m}, and kis a non-negative integer. Rules satisfy the conservativeness condition ε(a) + k=ε(b); •iin ∈ {1,2, . . . , m}specifies the input region of Π; •iout ∈ {0,1, . . . , m}specifies the output region of Π(iout = 0 corresponds to the environment). Remark 1. In the above definition we excluded rules of types e→(e, p), originally included in [8]. It is easy to see that this does not influence the computational power of energy-based P systems. When a rule of the type aek→(b, p) is applied, the object a, in presence of k free energy units, is allowed to be transformed into object b(note that εa+k=εb, for the conservativeness condition). If p= here, then the new object bremains in the same region; if p= out, then bexits from the current membrane. Finally, if p= in(name), then benters into the membrane labelled with name, which must be directly contained inside the current membrane in µ. The meaning of rule b→(a, p)ek, where kis a positive integer number, is similar: the object bis allowed to be transformed into object aby releasing kunits of free energy (also Characterizing the Computational Power of Energy-Based P Systems 15 here, εb=εa+k). As above, the new object amay optionally move one level up or down into the membrane structure. The kfree energy units might then be used by another rule to produce “more energetic” objects from “less energetic” ones. When k= 0 the rule aek→(b, p), also written as a→(b, p), transforms the object ainto the object b(note that in this case εb=εa) and moves it (if p= here) upward or downward into the membrane hierarchy, without acquiring or releasing any free energy unit. A similar observation applies to rules b→(a, p)ekwhen k= 0. Rules can be applied either in the sequential or in the maximally parallel mode. In either cases, we assume that the execution of rules does not consume energy. When working in the sequential mode, at each computation step (a global clock is assumed) exactly one enabled rule is nondeterministically chosen and applied in the whole system. When working in the maximally parallel mode, instead, at each computation step in each region of the system a maximal multiset of applicable rules is selected, and then all those rules are applied in parallel. Here maximal means that no further rule is applicable to objects that are “idle”, that is, not already used by some other rule. If two or more maximal sets of applicable rules exist, then one of them is nondeterministically chosen. A configuration of Πis the tuple (M1, . . . , Mm) of multisets (over A∪ {e}) of objects contained in each region of the system; (w1, . . . ,wm) is the initial configuration. A configuration where no rule can be further applied on is said to be final. A computation is a sequence of transitions between configurations of Π, starting from the initial one. A computation is successful if and only if it reaches a final configuration or, in other words, it halts. The multiset wiin of objects occurring inside the input membrane is the input for the computation, whereas the multiset of objects occurring inside the output membrane (or ejected from the skin, if iout = 0) in the final configuration is the output of the computation. A non-halting computation produces no output. As an alternative, we can consider the Parikh vectors associated with the multisets, and see energy-based P systems as computing devices that transform (input) Parikh vectors to (output) Parikh vectors. We may also assume that energy-based P systems have α≥1 input membranes and β≥1 output membranes, instead of one. This modification does not increase the computational power of energy-based P systems, since for any fixed value of α≥1 (resp., β≥1), the set Nα(resp., Nβ) is isomorphic to N, as it is easily shown by using the well known Cantor mapping. In what follows sometimes we will use energy-based P systems as generating devices: we will disregard the input membrane, and will consider the multisets (or Parikh vectors) produced in the output membrane at the end of the (halting) nondeterministic computations of the system. In particular, in the output multisets we will only count the number of free energy units contained in the βoutput regions in the final configuration. We will denote the family of β-dimensional vectors generated in this way by energy-based P systems with at most mmembranes and unbounded energy by Ps(β)OPm(energy∗). The union of all these classes for βranging through the set of all non-negative integers is denoted by PsOPm(energy∗). When β= 1, the class P s(β)OPm(energy∗) will be written as 16 A. Alhazov, M. Antoniotti, A. Leporati NOPm(energy∗). In all cases we will replace the subscript mby ∗if no bound is placed on the number of membranes. If instead of maximal parallelism we assume that the P system evolves sequentially, we will add the superscript seq to Pin the notation. Our results will thus be proved for energy-based P systems working as generating devices; however, the extension to the cases in which P systems are computing functions or are accepting multisets of objects (or Parikh vectors) will be straightforward. 2.3 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: •l1:ADD(j, l2, l3), with l1∈B\ {lh},l2, l3∈B, 1 ≤j≤m Increase the value of register jby one, and nondeterministically 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. Note that, without loss of generality, we may assume that this instruction always appears exactly once in P, with label lh. 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, that indicates the next instruction to be executed. Computations start by executing the first instruction of P(labelled with l0), and terminate if and when they reach instruction lh. Register machines provide a simple universal computational model [9]. In particular, the results proved in [4] immediately lead to the following proposition. Proposition 1. For any partial recursive function f:Nα→Nβthere exists a deterministic (max{α, β}+2)-register machine Mcomputing fin such a way that, when starting with (n1, . . . , nα)∈Nαin registers 1to α, and all other registers empty, Mhas computed f(n1, . . . , nα) = (r1, . . . , rβ)if it halts in the final label lhwith registers 1to βcontaining r1to rβ, and all other registers being empty. If the final label cannot be reached, then f(n1, . . . , nα)remains undefined. Register machines can also be 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. The following Proposition is a direct consequence of Proposition 1. Characterizing the Computational Power of Energy-Based P Systems 17 Proposition 2. For any recursively enumerable set L⊆Ps (α)RE of vectors of non-negative integers there exists a deterministic register machine Mwith (α+ 2) registers accepting Lin such a way that, when starting with n1to nαin registers 1to α,Mhas accepted (n1, . . . , nα)∈Lif and only if it halts in the final label lh with all registers being empty. To generate vectors of non-negative integers we have to use nondeterministic register machines. The following Proposition is also a direct consequence of Proposition 1. Proposition 3. For any recursively enumerable set L⊆Ps (β)RE of vectors of non-negative integers there exists a nondeterministic register machine Mwith (β+ 2) registers generating Lin such a way that, when starting with all registers being empty, Mhas generated (r1, . . . , rβ)∈Lif it halts in the final label lhwith registers 1to βcontaining r1to rβ,and all other registers being empty. A direct consequence of the results exposed in [9] is that in Propositions 1 and 3 we may assume without loss of generality that only ADD instructions are applied to the output registers. This fact will be used to decrease the number of membranes of energy-based P systems simulating register machines; in particular, for each output register one membrane will suffice, whereas to simulate the behaviour of the other registers we will need two membranes. A register machine is called partially blind if performing a zero-test blocks the computation, thus leading to no result. We can reflect this situation by omitting l3 from all SUB instructions. However, unless all non-output registers have value zero at halting, the result of a computation is discarded; note that this is an implicit final zero-test, imposed by the definition and not affecting the power of register machines in the general case. It is known [3] that partially blind register machines characterize PsMAT. 3 Characterizing the Power of Energy-based P Systems In this section we characterize the computational power of energy-based P systems without priorities associated to the rules and with an unbounded amount of free energy units. As stated in the previous section, we use energy-based P systems as generating devices; the extension to the computing and accepting cases (concerning computational completeness) is easy to obtain. We start with systems working in the sequential mode; with the next two theorems we prove that they characterize PsMAT. We first prove the inclusion PsMAT ⊆PsOPseq ∗(energy∗), obtained by simulating partially blind register machines. Theorem 1. PsOPseq ∗(energy∗)⊇P sMAT . 18 A. Alhazov, M. Antoniotti, A. Leporati Proof. Consider a partially blind register machine M= (m, B, l0, lh, P), generating β-dimensional vectors, and assume that registers β+1, . . . , m are empty in the final configuration of successful computations, corresponding to an implicit final zero-test. We construct a corresponding energy-based P system ΠM, containing an infinite amount of free energy units in the skin, as follows: Π= (A, ε, µ, e, ws, . . . , wf, Rs, . . . , Rf),where A={l, l′, l′′ |l∈B}∪{tj, Tj|β+ 1 ≤j≤m} ∪ {t, T, H, H′}, ε(l) = 1, ε(l′) = 2, ε(l′′) = 0, l ∈B, ε(tj) = 0, ε(Tj) = 2, β + 1 ≤j≤m, ε(t) = 0, ε(T) = 1, ε(H) = 2m+ 1, ε(H′) = 2β+ 2, µ= [ [ ]1· · · [ ]m[ ]f]s, ws=l0, wj=λ, 1≤j≤m, wf=tβ+1 · · · tmT, Rs={l1e→(l′ 1, in(j)) |l1:ADD(j, l2, l3)∈P} ∪ {l1→(l′′ 1, in(j)) e|l1:SUB(j, l2)∈P} ∪ {T→(T, in(f)), lhe2m→(H, in(f))} ∪ {Tj→(t, in(j)) e2|β+ 1 ≤j≤m}. Rj={l′ 1→(l2, out)e, l′ 1→(l3, out)e|l′ 1:ADD(j, l2, l3)∈P} ∪ {l′′ 1e→(l2, out)|l1:SUB(j, l2)∈P} ∪ R′ j,1≤j≤m, R′ j=∅,1≤j≤β, R′ j={T→te, te →T}, β + 1 ≤j≤m, Rf={T→te, te →T, H →H′e2(m−β)−1} ∪ {tje2→(Tj, out)|β+ 1 ≤j≤m}. Note that if β=m, then we replace H→H′e−1in Rfby He →H′. The sets of rules Rjand R′ j, 1 ≤j≤m, are both intended to be associated with region j, and hence should be joined. As explained below, the rules from R′ jare used to produce infinite T↔te loops in the regions corresponding to non-output registers of Mif such registers are nonempty when the computation halts. The simulation consists of a few parts. Every object associated with an instruction label l1embeds 1 unit of energy. To simulate an increment instruction l1:ADD(j, l2, l3), the corresponding object l1consumes 1 more unit of energy, enters the region associated with register jas l′ 1, releases ethere, and returns to the skin either as the object l2or as l3(the choice being made in a nondeterministic way), indicating the next instruction of Mto be simulated. To simulate a decrement instruction l1:SUB(j, l2), the corresponding object l1releases ein the skin and enters as l′′ 1the region associated with register j. There it consumes 1 unit of energy, and returns to the skin as the object l2associated with the next Characterizing the Computational Power of Energy-Based P Systems 19 instruction of Mto be simulated. If the register was empty then this process is blocked. Meanwhile, another process takes place in region f; the order of execution of the two processes is nondeterministic, but both must finish in order for the system to terminate the computation and produce a result. The aim of this latter process is indeed to make ΠM“compute” forever if the above simulation of the SUB instruction gets blocked when trying to decrement an empty register, so that no result is produced in this case. The process consists of object Tcyclically releasing eand capturing it, generating a possibly infinite loop. The only way to stop the loop is to alter the free energy occurring in region m. This is done when the simulation of Mis finished, leading to object Hreleasing e2(m−β)−1. If β=mthis consumes 1 unit of energy, thus stopping the T↔te loop. Otherwise it releases enough energy for objects tj,β+ 1 ≤j≤mto leave the region, and the last one of them stops the T↔te loop. The objects tjare used to ensure that registers β+ 1 ≤j≤mare empty, otherwise causing a T↔te loop in the corresponding region.  The opposite inclusion, PsOPseq ∗(energy∗)⊆P sMAT , is proved by simulating energy-based P systems by matrix grammars. Theorem 2. PsOPseq ∗(energy∗)⊆P sMAT . Proof. Let Πbe an energy-based P system containing an infinite amount of free energy units and applying the rules in the sequential mode. Each rule of Πcan be simulated by a corresponding rewriting rule on multisets of object-region pairs, ignoring those pairs involving energy objects in the regions containing infinite free energy. Such a multiset rewriting rule can be written as a matrix, yielding a matrix grammar. Clearly no matrix can be applied if and only if no rule can be applied. Since matrix languages are closed under morphisms, when this happens we can apply a morphism that erases all object-region pairs except those involving free energy objects in the output regions. The resulting language belongs to MAT, and its Parikh mapping yields exactly Ps(Π).  By joining the two inclusions proved in Theorems 1 and 2 we obtain our characterization of PsMAT by energy-based P systems working in the sequential mode with an unbounded amount of free energy: Corollary 1. PsOPseq ∗(energy∗) = P sMAT . Running energy-based P systems in the maximally parallel mode allows them to reach computational completeness without using priorities, as shown in the next theorem. Theorem 3. Ps(β)RE =Ps(β)OPβ+6(energy∗)for all integers β≥1.