P Systems with Tables of Rules

P Systems with Tables of Rules Gheorghe P ˘ AUN1,2, Mario P´ EREZ-JIM´ ENEZ2, Agust´ın RISCOS-N ´ U˜ NEZ2 1Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Technical Higher School of Computer Science Engineering University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {gpaun, marper, ariscosn}@us.es Abstract. In the last time, several efforts were made in order to remove the polarization of membranes from P systems with active membranes; the present paper is a contribution in this respect. In order to compensate the loss of power represented by avoiding polarizations, we introduce tables of rules: each membrane has associated several sets of rules, one of which is nondeterministically chosen in each computation step. Three universality results for tabled P systems are given, trying to use rules of as few as possible types. Then, we consider tables with obligatory rules – rules which must be applied at least once when the table is applied. Systems which use tables with at most one obligatory rule are proven to be able to solve SAT problem in linear time. Several open problems are also formulated. 1 Introduction In membrane computing, the P systems with active membranes have a special place, because of the fact that they provide biologically inspired means to solve computationally hard problems: by using the possibility to divide membranes, one can create an exponential working space in a linear time, which can then be used in a parallel computation for solving, e.g., NP-complete problems in polynomial or even linear time. Details can be found in [7], [8], as well as in the comprehensive page from the web address http://psystems.disco.unimib.it). One of the important ingredients of P systems with active membranes is the polarization of membranes: besides a label, each membrane also has an “electrical charge”, one of + (positive), −(negative), 0 (neutral). These electrical charges correspond only remotely to biological facts; by sending ions outside, cells and cell compartments can get polarizations, but this is not a very common phenomenon. Starting from this observation and also as a mathematical challenge, in the last time several efforts were made to avoid using polarizations. 366 However, the question seems not to be a simple one, and the best result obtained so far was to reduce to two the number of “electrical charges”; this is achieved in [1], where both the universality and the possibility of solving SAT in linear time are proven for P systems with active membranes and only two polarizations. When completely removing the polarizations, similar results are obtained (see [2], [3]) only by compensating the loss of power (of “programming” possibilities) by using additional ingredients, such as the possibility of changing the labels of membranes, division of non-elementary membranes, etc. The present paper goes into the same direction of research: we get rid of polarizations and we “pay” this by structuring the sets of rules associated with each membrane by considering tables of rules, like in Lindenmayer systems. Specifically, several sets of rules are associated with each membrane, and in each step of a computation we nondeterministically choose one of these sets, its rules are used in the maximally parallel manner. The use of tables can have a biological motivation, in the same way as the tables from L systems theory have a biological origin: the change of environmental conditions (for instance, of seasons) can select specific evolution rules for different times (different seasons). The use of tables proves to be helpful in what concerns the computing power: we get universality for systems of a rather reduced forms, with only a few types of rules used, and without polarizations. An important problem remains unsolved: can tables compensate polarizations also in what concerns the possibility to solve hard problems in polynomial time? A possible negative answer to this problem would be a very nice finding: in view of the result from [1], it would follow that passing from one polarization (all membranes neutral) to two polarizations makes possible the step from the complexity class Pto NP. If, however, we add a further ingredient – at the first sight not very powerful – to tabled P systems, namely designating in each table rules which should be used at least once when applying the table, then we can solve SAT in linear time. The construction uses at most one obligatory rule in each table. 2 P Systems with Active Membranes We assume the reader to be familiar with basic elements of membrane computing, but, for the sake of completeness, we recall here the definition of the class of P systems we work with, those with active membranes (and electrical charges). Such a system is a construct Π = (O, µ, w1, . . . , wm, R), where: 1. m≥1 (the initial degree of the system); 2. Ois the alphabet of objects; 3. µis a membrane structure, consisting of mmembranes, labeled in a one-to-one manner with elements of H={1,2, . . . , m}; 4. w1, . . . , wmare strings over O, describing the multisets of objects placed in the m regions of µ; 5. Ris a finite set of developmental rules, of the following forms: 367 (a) [ a→v]e h, for h∈H, e ∈ {+,−,0}, a ∈O, v ∈O∗ (object evolution rules, associated with membranes and depending on the label and the charge of the membranes, but not directly involving the membranes, in the sense that the membranes are neither taking part in the application of these rules nor are they modified by them); (b)a[ ]e1 h→[b]e2 h, for h∈H, e1, e2∈ {+,−,0}, a, b ∈O (communication rules; an object is introduced in the membrane, possibly modified during this process; also the polarization of the membrane can be modified, but not its label); (c) [ a]e1 h→[ ]e2 hb, for h∈H, e1, e2∈ {+,−,0}, a, b ∈O (communication rules; an object is sent out of the membrane, possibly modified during this process; also the polarization of the membrane can be modified, but not its label); (d) [ a]e h→b, for h∈H, e ∈ {+,−,0}, a, b ∈O (dissolving rules; in reaction with an object, a membrane can be dissolved, while the object specified in the rule can be modified); (e) [ a]e1 h→[b]e2 h[c]e3 h, for h∈H, e1, e2, e3∈ {+,−,0}, a, b, c ∈O (division rules for elementary membranes; in reaction with an object, the membrane is divided into two membranes with the same label, possibly of different polarizations; the object specified in the rule is replaced in the two new membranes by possibly new objects). We have omitted the rules for dividing non-elementary membranes, usually identified as being “of type (f)”. In the customary definition of P systems with active membranes, the initial membranes of µare not necessarily labeled in a one-to-one manner, but there is no loss of generality in the assumption that the labels are unique: we can relabel the membranes with the same label and then duplicate the necessary rules. Moreover, because in what follows we only consider that by membrane division we obtain membranes with the same label, the labels present in the system are always from the set {1,2, . . . , m}present at the beginning (maybe some of them used several times, because of the division of membranes). Therefore, the set Hof labels is specified by µ, it can be omitted when specifying the system. The rules of type (a) are applied in the parallel way (all objects which can evolve by such a rule should do it), while the rules of types (b),(c),(d),(e) are used sequentially, in the sense that one membrane can be used by at most one rule of these types at a time. In total, the rules are used in the non-deterministic maximally parallel manner: all objects and all membranes which can evolve, should evolve. Only halting computations give a result, and the result is the number of objects expelled into the environment during the computation; the set of numbers computed in this way by the various halting computations in Π is denoted by N(Π). By NOPm,n,p(pol3, a, b, c, d, e) we denote the family of sets N(Π) computed as sketched above by systems starting with at most mmembranes, using membranes of at most ntypes, 368 at most pmembranes being simultaneously present, and using all types of rules; when rules of a certain type are not used the corresponding letter a, b, c, d, e will be missing. Also, when membrane division rules are not used, we will specify only the number of membranes in the initial configuration (hence, only m) as a subscript of NOP . The parameter pol3 indicates the fact that one uses three polarizations. Further details can be found in [7] – including the proof of the following result. (We denote by REG, CF, CS, RE the families of regular, context-free, context-sensitive, and of recursively enumerable languages. In general, for a family FL of languages, NF L denotes the family of length sets of languages in FL. Therefore, NRE is the family of Turing computable sets of natural numbers.) Theorem 2.1 NOP3(pol3, a, b, c) = NRE. The number of polarizations were decreased to two in [1]; with the previous notations, the result can be written as: Theorem 2.2 NOP2(pol2, a, c) = NRE. Note that the result from Theorem 2.1 was improved both in the number of polarizations and the number of membranes, while the used rules are of the same types. In [3] and [2] rules of types (a)−(e) without polarizations were considered. Because “no polarization” means “neutral polarization”, we add the subscript 0 to the previous letters identifying the five types (a0)−(e0) of rules. The power of polarizationless P systems with active membranes is not precisely known, but it was shown in [2] that they are able to compute at least the Parikh images of languages generated by matrix grammars without appearance checking. Because the notion of a matrix grammar will be also used below, we introduce it here in its general form. Amatrix grammar (with appearance checking) is a construct G= (N, T, S, M, F), where Nand Tare disjoint alphabets, S∈N,Mis a finite set of sequences of the form (A1→x1,. . . , An→xn), n≥1, of context-free rules over N∪T(with Ai∈N, xi∈ (N∪T)∗, in all cases), and Fis a set of occurrences of rules in M(Nis the nonterminal alphabet, Tis the terminal alphabet, Sis the axiom, while the elements of Mare called matrices). For w, z ∈(N∪T)∗we write w=⇒zif there is a matrix (A1→x1, . . . , An→xn) in Mand the strings wi∈(N∪T)∗,1≤i≤n+ 1, such that w=w1, z =wn+1,and, for all 1≤i≤n, either wi=w0 iAiw00 i, wi+1 =w0 ixiw00 i, for some w0 i, w00 i∈(N∪T)∗, or wi=wi+1, Aidoes not appear in wi, and the rule Ai→xiappears in F. (The rules of a matrix are applied in order, possibly skipping the rules in Fif they cannot be applied – therefore we say that these rules are applied in the appearance checking mode.) The language generated by Gis defined by L(G) = {w∈T∗|S=⇒∗w}.The family of languages of this form is denoted by MATac. If the set Fis empty, then the grammar is said to be without appearance checking. It is known that CF ⊂MAT ⊂MATac =RE,NREG =NCF =NMAT ⊂NCS, (for instance, the one-letter languages in MAT are known to be regular, [6]). A matrix grammar G= (N, T, S, M, F ) is said to be in the binary normal form if N=N1∪N2∪ {S, #}, with these three sets mutually disjoint, and the matrices in Mare in one of the following forms: 369 1. (S→XA),with X∈N1, A ∈N2, 2. (X→Y, A →x),with X, Y ∈N1, A ∈N2, x ∈(N2∪T)∗,|x| ≤ 2, 3. (X→Y, A →#),with X, Y ∈N1, A ∈N2, 4. (X→λ, A →x), with X∈N1, A ∈N2,and x∈T∗,|x| ≤ 2. Moreover, there is only one matrix of type 1 (that is why one uses to write it in the form (S→X0A0), in order to fix the symbols X, A present in it), and Fconsists exactly of all rules A→# appearing in matrices of type 3; # is a trap-symbol, because once introduced, it is never removed. A matrix of type 4 is used only once, in the last step of a derivation. For each matrix grammar there is an equivalent matrix grammar in the binary normal form. Details can be found in [4]. 3 Tables of Rules In the “standard” P systems with active membranes there is specified only one set of rules; because the membranes are present in the rules, we precisely know where each rule is to be applied with respect to each membrane. A possible generalization is to consider several sets of rules – for uniformity with L systems, we call them tables – such that in each step of a computation a table is used, non-deterministically chosen (the rules of the selected table are applied in the maximally parallel manner, as mentioned in the previous section). This case corresponds to having global tables; a more relaxed variant is to consider local tables, sets of rules associated with each membrane. Specifically, for each membrane iwe can consider sets Ri,1, . . . , Ri,kiof rules, for some ki≥1, all of the rules involving membrane i. In a step of a computation, we apply the rules from one of the tables associated with each membrane, as usual, in the maximally parallel non-deterministic manner with respect to the chosen table. If we are allowed to “evolve” a region by means of a table for which no rule is actually applied, then the local tables can be combined in global tables, hence in this case the local version is weaker than the global one. However, there is no difference from the computational point of view (at least in the cases investigated in the next section): systems with local tables (and restricted types of rules) are equivalent with Turing machines; moreover, the proofs are based on systems with one or two membranes, with the “main work” of two-membranes systems done in the inner membrane, hence choosing tables which change nothing in one of the regions do not change the generated set of numbers. In what follows we will consider only local tables, that is why we choose a more restricted – also, more natural – definition of a transition step: if there are tables by which a region can effectively evolve (at least a rule of these tables can be effectively applied), then one of these tables must be chosen. Otherwise stated, we cannot choose a table with no applicable rule if there are tables with applicable rules. This restriction both corresponds to the notions of parallelism and synchronization, basic in membrane computing, and it is also useful in the proofs below. In systems with tables (either local or global) we have two levels of non-determinism: in each step we first non-deterministically choose one table (in the local case, associated with each membrane), and then we use the rules of the chosen table in a non-deterministic manner (observing the restriction of maximal parallelism for the chosen table). The standard definition of P systems corresponds to the case where we have only one table (at the level of the system). 370 The fact that we use (local) tables is indicated by adding tab to the notations from the previous section. We do not know whether the number of tables associated with membranes matters (that is, whether it induces an infinite hierarchy of the computed sets of numbers) or normal form theorems like that known for ET0L systems (two tables are enough, see [9]) are true also in our case. In view of this open problem it could be better to indicate also the maximal number of tables used, writing tabsfor using at most stables, but we do not deal with this aspect here. The usefulness of using tables is intuitively obvious, because by clustering the rules in “teams of rules” we can control in a more careful way the work of the system. This is illustrated also by the following simple example: consider the system Π = ({a, b},[ ]1, a, R1,1, R1,2, R1,3), R1,1={[a→aa ]1}, R1,2={[a→b]1}, R1,3={[b]1→a}. After using n≥0 times the first table (thus producing 2ncopies of a), we can end the computation by using once the second table, and then 2ntimes the third one. Consequently, N(Π) = {2n|n≥1} ∈ NOP1(tab, a0, c0), a set of numbers which is not in NMAT . 4 Universality Results The usefulness of tables is illustrated also by the results below: the computational universality is obtained without polarizations for various reduced combinations of types of rules. The first result uses rules of the first three types (hence not membrane dissolution or membrane division operations). Theorem 4.1 NOP2(tab, a0, b0, c0) = NRE. Proof. Let us consider a matrix grammar with appearance checking G= (N, {a}, S, M, F ) in the binary normal form, hence with N=N1∪N2∪ {S, #}and with matrices of the four types mentioned in Section 2. All matrices of Mare supposed to be labeled in an injective manner with mi,1≤i≤n(hence iuniquely identifies the matrix). Each terminal matrix (X→λ, A →x) is replaced with (X→f, A →x), where fis a new symbol (the label of the matrix remains unchanged). We construct the tabled P system with active membranes, Π, with the components: O=N1∪N2∪ {Zi, Z0 i,hii | 1≤i≤n}∪{a, a0, e, f, #}, µ= [ [ ]2]1, w1=λ, w2=X0A0e, where (S→X0A0) is the initial matrix of G, and the following tables (by Uwe denote the set N1∪ {Zi, Z0 i,hii | 1≤i≤n}). 371 1. For each matrix mi: (X→Y, A →x) in Mof types 2 or 4, we consider the tables R2,i ={[X→Zi]2,[A]2→[ ]2hii,[e]2→#} ∪ {[α→# ]2|α∈U}, R0 2,i ={[Zi→Z0 i]2,hii[ ]2→[hii]2} ∪ {[α→# ]2|α∈U}, R00 2,i ={[Z0 i→λ]2,[hii → xY ]2} ∪ {[α→# ]2|α∈U}. 2. For each matrix mi: (X→Y, A →#) in Mof type 3, we consider the table R2,i ={[X→Y]2,[A→# ]2} ∪ {[α→# ]2|α∈U}. 3. We also consider the following tables: R2,f ={[f→λ]2} ∪ {[α→# ]2|α∈U∪N2}, R2,a ={[a]2→[ ]2a0,[ # →# ]2}, R1={[a0]1→[ ]1a, [ # →# ]1}. We have the equality N(Π) = {n|an∈L(G)}. Indeed, we start with the multiset X0A0ein the central membrane; assume that we have here a multiset Xwe for some X∈N1and w∈(N2∪ {a})∗. There is only one table for membrane 1, sending out a copy of a(provided that there are copies of a0in the skin region), and using the trap-rule # →# provided that the object # is present; in this latter case, the computation will never stop. If applied in membrane 2 when Xwe is here, the table R2,f will introduce the trap-object #, and this happens also if we use any table of the forms R0 2,i, R00 2,i. Thus, we can apply only a table of type R2,i for mia matrix of M. That matrix should be either of the form mi: (X→Y, A →x) (of type 2 or of type 4), or of the form mi: (X→Y, A →#) (of type 3): if the first rule of the matrix is α→βwith α6=X, then the trap-object is introduced. The case of a matrix of type 3 is simpler: if Ais present, then the trap-object is introduced, and the computation will never stop (because of the table R2,a, which can be used forever). If Ais not present, then we just change Xinto Y. Thus, the simulation of the matrix miof type 3 is correct. If we choose to simulate a matrix of types 2 or 4, then it must have the second rule of the form A→x, for Aas specified by the table R2,i: if the rule [ A]2→[ ]2hiiis not used, thus “keeping busy” the membrane, then the rule [ e]2→# must be used, and the computation will never stop (table R1can be applied forever). In the next step we have to continue the simulation of the matrix miby using the corresponding table R0 2,i. This is the only table which will not introduce # which can be applied without introducing the trap-object. In this way, hiicomes back to membrane 2, and Ziis replaced by Z0 i. In the next step, again only one table can be used without introducing the trap-object, namely R00 2,i. It erases the object Z0 iand replaces hiiwith xY , thus completing the simulation of the matrix. 372 At any moment, if any object ais present in membrane 2, then table R2,a can be used and ais sent out (first transformed into a0in the skin region). The system is returned to a configuration with the contents of membrane 2 as in the beginning, hence the process can be iterated. When the object fis introduced, no table R2,i, R0 2,i, R00 2,i can be used. By means of R2,f we check whether any symbol from N2is present, hence whether the derivation in Gis terminal. The computation in Π ends by sending out all copies of a, hence N(Π) equals the length set of the language L(G). 2 In the previous proof, the role of rules of type (b0),(c0) (besides sending the result outside the system) was to ensure that only one object Ais replaced by x, thus correctly simulating the second rule of a matrix (X→Y, A →x) of types 2 or 4. This can be done also by using rules of type (e0). Theorem 4.2 NOP2,2,3(tab, a0, c0, e0) = NRE. Proof. As above, we consider a matrix grammar with appearance checking G= (N, {a}, S, M, F ) in the binary normal form, with the matrices of Mlabeled in an injective manner with mi,1≤i≤n, and each terminal matrix (X→λ, A →x) replaced with (X→f, A →x), where fis a new symbol. We now construct the tabled P system with active membranes Π, with the components: O=N1∪N2∪ {Zi,hii | 1≤i≤n}∪{a, a0, d, e, f, #}, µ= [ [ ]2]1, w1=λ, w2=X0A0e, where (S→X0A0) is the initial matrix of G, and the following tables (by Uwe denote the set N1∪ {Zi,hii | 1≤i≤n}). 1. For each matrix mi: (X→Y, A →x) in Mof types 2 or 4, we consider the tables R2,i ={[X→Zi]2,[A]2→[hii]2[d]2, [d→# ]2,[e]2→[#]2[#]2} ∪ {[α→# ]2|α∈U∪ {a}}, R0 2,i ={[Zi→λ]2,[hii → xY ]2,[d→# ]2} ∪ {[α→# ]2|α∈U∪ {a}}. 2. For each matrix mi: (X→Y, A →#) in Mof type 3, we consider the table R2,i ={[X→Y]2,[A→# ]2,[d→# ]2} ∪ {[α→# ]2|α∈U∪ {a}}. 3. We also consider the following tables: R2,f ={[f→λ]2,[d→# ]2} ∪ {[α→# ]2|α∈U∪N2}, R2,d ={[d]2→d, [a]2→[ ]2a0,[ # →# ]2}, R1={[a0]1→[ ]1a, [ # →# ]1}. 373 The equality N(Π) = {n|an∈L(G)}follows in a similar way as in the previous proof, this time with the interplay of rules [ A]2→[hii]2[d]2and [ e]2→[ # ]2[ # ]2ensuring that the second rule of each matrix of type 2 or 4 is correctly simulated (used exactly once): if the second rule is used, then the computation never stops, hence [ A]2→[hii]2[d]2 must be used. In this way, membrane 2 is divided. In the first copy of the membrane we have the object hii, which will complete the simulation of the matrix. In the second copy of the membrane, the one containing the object d, we cannot use any table which contains the rule d→#, hence the only continuation is by using the table R2,d. This dissolves the membrane, and its objects, remained free in the skin region, will no longer evolve. The matrices of type 3 are again simulated in only one step of a computation in Π. All copies of object aare immediately sent out of membrane 2 (to prevent their duplication when dividing the membrane), and from the skin region are sent out of the system. We leave the details to the reader and conclude that the system correctly simulates the matrix grammar G.2 One of the difficulties in the previous proofs was to inhibit the parallelism of using the rules of type (a0). In membrane computing, the usual way to do this is by using catalysts, distinguished objects which never evolve, but can enter rules of the form ca →cv, where ais a single object, which evolves under the control of the catalyst c. This idea can be considered also for P systems with active membranes, allowing rules of type (a0) of the form [ ca →cv ]i, where cis a catalyst, ais an object and va multiset of objects. (When specifying a system with catalysts, the set Cof catalysts is explicitly given after the set of objects.) We indicate the use of catalysts by writing catrin the notation for families of numbers computed by systems of a given type as above; rindicates the fact that at most rcatalysts are used. The previous results have the following counterpart for the catalytic case – with only two types of rules being used, and with only one membrane (note that one catalyst suffices). Theorem 4.3 NOP1(tab, cat1, a0, c0) = NRE. Proof. We consider again a matrix grammar with appearance checking G= (N, {a}, S, M, F ) in the binary normal form, with each terminal matrix (X→λ, A →x) replaced with (X→f, A →x), where fis a new symbol, and we construct the tabled P system with catalysts Π, with the components: O=N1∪N2∪ {a, c, d, f, #}, C={c}, µ= [ ]1, w1=X0A0d, where (S→X0A0) is the initial matrix of G, and the following tables. 1. For each matrix mi: (X→Y, A →x) in Mof types 2 or 4, we consider the table R1,i ={[X→Y]1,[cA →cx ]1,[cd →c# ]1} ∪ {[Z→# ]1|Z∈N1∪ {f}}. 2. For each matrix mi: (X→Y, A →#) in Mof type 3, we consider the table R1,i ={[X→Y]1,[A→# ]1} ∪ {[Z→# ]1|Z∈N1∪ {f}}. 374