Tissue-like P Systems with Channel-States

Tissue-like P Systems with Channel-States Rudolf FREUND1, Gheorghe P ˘ AUN2,3, Mario J. P´ EREZ JIM´ ENEZ3 1Faculty of Computer Science Vienna University of Technology Favoritenstr. 9–11, A–1040 Vienna, Austria E-mail: [email protected] 2Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania 3Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {gpaun,marper}@us.es Abstract. We consider tissue-like P systems with states associated with the links (we call them synapses) between cells, controlling the passage of objects across the links. We investigate the computing power of such devices for the case of using – in a sequential manner – antiport rules of small weights. Systems with two cells are proven to be universal when having arbitrarily many states and minimal antiport rules, or two states, and antiport rules of weight two. Also the systems with arbitrarily many cells, three states, and minimal antiport rules are universal. In contrast, the systems with one cell and any number of states and rules of any weight only compute Parikh sets of matrix languages (generated by matrix grammars without appearance checking); characterizations of Parikh images of matrix languages are obtained for such one-cell systems with antiport rules of a reduced weight. A series of open problems are also formulated. 1 Introduction In membrane computing area there are two main classes of systems: cell-like and tissuelike P systems. The former type is inspired from the cell organization (and has membranes hierarchically arranged, hence corresponding to a tree), the latter one mimics the “collaboration” of cells from tissues of various kinds (hence corresponds to membranes placed in the nodes of an arbitrary graph). Actually, there are two sub-classes of tissue-like P systems, one using symport/antiport rules for communicating among cells, and the other one, closer to the neural net organization, having states associated with the cells, for controlling multiset rewriting rules which make evolve the multisets of objects from the cells. 206 In the present paper, we take a different perspective, somewhat mixing the two subcases of tissue-like systems: we associate states to the links between cells, and use these states in order to control the communication among cells; in its turn, the communication is done by means of symport/antiport rules. Among two cells at most one link is established (also called synapse). Because the states can be changed by using rules, a conflict can appear when two rules used on the same link ask for changing the state to two different new states. That is why we use the rules in a sequential manner: on each possible channel between two cells we use only one rule. At the level of the whole net of cells, the evolution is parallel (synchronous): we have to use a rule on each synapse where a rule can be used. Considering a sequential use of rules on each link between cells is also challenging from a mathematical point of view; the maximal parallelism, usual in membrane computing, combined with the definition of successful computations as the halting ones, is a powerful tool in “programming” the work of P systems of various types (in particular, it provides a way to implement “appearance checking”, as in regulated context-free grammars). In our framework, the expected loss in power induced by the sequential use of rules is compensated by the use of states. The issue of considering states associated with the communication channels among membranes is part of a more general research topic, that of considering tissue-like P systems with a dynamic structure (dynamically changing membranes and/or links among them). Our approach can be considered as a partial answer to this general problem, as the states control the passage of objects across the links, selectively permitting the objects to pass, possibly completely inhibiting certain channels. The power of systems as suggested above, with antiport rules of small weights used sequentially are shown to be Turing complete in the case of two cells (even with minimal antiport rules, if “enough” states are used) and to characterize the Parikh images of languages generated by matrix grammars without appearance checking in the case of one cell (no matter how many states and no matter how general rules are used). The case of the parallel use of rules (in a step we can use simultaneously all rules which pass from a given state to a unique next state) – as well as other related problems – remain to be investigated. 2 Tissue-like P Systems with States The reader is supposed to be familiar with basic elements of membrane computing, e.g., from [11] (rather useful is the comprehensive information which can be found in the web page http://psystems.disco.unimib.it), in particular, with the tissue-like P systems introduced in [9]. Here we deal with the following type of systems (for the very few elements of computability – mainly formal language theory – we refer to any monograph in this area, in particular, to [13]; just for the sake of completeness, we mention that V∗ is the free monoid generated by the alphabet Vunder the operation of concatenation and the empty string, denoted by λ, as identity). A tissue-like P system (of degree m≥1) with channel-states is a construct Π = (O, T, K, w1, . . . , wm, E, syn, (s(i,j))(i,j)∈syn,(R(i,j))(i,j)∈syn, io), where Ois the alphabet of objects,T⊆Ois the alphabet of terminal objects, Kis the alphabet of states (not necessarily disjoint of O), w1, . . . , wmare strings over Orepresenting the initial multiset of objects present in the cells of the system (it is assumed 207 that we have mcells, labelled with 1,2, . . . , m), E⊆Ois the set of objects present in arbitrarily many copies in the environment, syn ⊆ {(i, j)|i, j ∈ {0,1,2, . . . , m}, i 6=j} is the set of links among cells (we call them synapses; 0 indicates the environment) such that for i, j ∈ {0,1, . . . , m}at most one of (i, j),(j, i) is present in syn,s(i,j)is the initial state of the synapse (i, j)∈syn,R(i,j)is a finite set of rules of the form (s, x/y, s0), for some s, s0∈Kand x, y ∈O∗, associated with the synapse (i, j)∈syn, and, finally, io∈ {1,2, . . . , m}is the output cell. We note the important restriction that there is at most one synapse among two given cells, and the synapse is given as an ordered pair (i, j), with which a state from Kis associated. The fact that the pair is ordered does not restrict the communication among the two cells (or between a cell and the environment), because we work here in the general case of antiport rules, specifying simultaneous movements of objects in the two directions of a synapse. A rule of the form (s, x/y, s0)∈R(i,j)is interpreted as an antiport rule for the ordered pair (i, j) of cells, acting only if the synapse (i, j) has the state s; the application of the rule means moving the objects specified by xfrom cell i(from the environment, if i= 0) to cell j, at the same time with the move of the objects specified by yin the opposite direction, as well as the change of the state of the synapse from sto s0. (The rules with one of x, y empty are, in fact, symport rules, but we do not explicitly consider here this distinction, as it is not relevant for what follows.) The objects from Eare never exhausted, irrespective how many copies of each of them are brought into the system, arbitrarily many copies remain available in the environment. The computation starts with the multisets specified by w1, . . . , wmin the mcells; in each time unit, a rule is used on each synapse for which a rule can be used (if no rule is applicable for a synapse, then no object passes over it and its state remains unchanged). Therefore, the use of rules is sequential at the level of each synapse, but it is parallel at the level of the system: all synapses which can use a rule must do it (the system is synchronously evolving). The computation is successful if and only if it halts and the result of a halting computation is the vector which describes the multiplicity of objects from Tpresent in cell ioin the halting configuration (the objects from O−Tare ignored when considering the result). The set of all vectors computed in this way by the system Π is denoted by Ps(Π). The family of sets Ps(Π) of vectors computed as above by systems with at most m cells, using at most kstates, and rules (s, x/y, s0) with |x| ≤ i, |y| ≤ iis denoted by PsOtPm(statesk, antii). When one of the parameters m, k, i is not bounded, it is replaced with ∗. We also denote by PsFL the set of Parikh images of languages from a given family FL; by RE we denote the family of recursively enumerable languages, and by CF the family of context-free languages. 3 Two Examples Before investigating the computing power of the above introduced devices, let us illustrate their work by some examples. The first one (of degree 3) is simpler. Formally, it is given as follows: Π1= (O, T, K, w1, w2, w3, E, syn, (s(i,j))(i,j)∈syn,(R(i,j))(i,j)∈syn, io), O={a, b}, T={a, b}, 208 K={s, s0, s00}, wi=λ, for all i= 1,2,3, E=O, syn ={(0,1),(1,2),(1,3)}, R(0,1) ={(s, a/λ, s),(s, a/λ, s0),(s0, b/λ, s0),(s0, b/λ, s00)}, R(1,2) ={(s, a/λ, s),(s, b/λ, s),(s, λ/a, s),(s, λ/b, s)}, R(1,3) ={(s, b/λ, s0),(s0, a/λ, s)}, io= 3. The system is pictorially given in Figure 1, with the synapses represented by arrows, having associated the initial states and the rules from the respective sets (the directionality of the arrows thus specifies the way the rules are applied); each cell has inside the initial multiset of objects and outside the label; the output cell, that with label 3, is indicated by having it doubly encircled. Figure 1. The system Π1(rules and initial configuration) ¹¸ º· ¹¸ º· ÁÀ ¿ ½¼ ¾» ? ?? 1 23 s ss λ λ λ (s, a/λ, s) (s, a/λ, s0) (s0, b/λ, s0) (s0, b/λ, s00) (s, a/λ, s) (s, b/λ, s) (s, λ/a, s) (s, λ/b, s) (s, b/λ, s0) (s0, a/λ, s) The functioning of the system Π1is rather clear: in state s, cell 1 brings inside n≥0 copies of object a, then the synapse (0,1) changes the state to s0when one further ain brought in; in state s0we bring in cell 1 a number m≥0 of copies of object b; the process is finished only by passing to state s00, hence at least one copy of bis introduced. Any copy of aand bcan oscillate forever among cells 1 and 2, hence the computation can stop only if all objects are moved to cell 3, the output one. The channel from cell 1 to cell 3 can be “open” only by a copy of b, which changes the state of this synapse to s0; in the presence of s0, a copy of ais moved from cell 1 to cell 3 and the state returns to s. Consequently, we can stop if and only if either the numbers of aand bintroduced in cell 1 were equal, or the number of copies of bis larger by 1 than the number of copies of a. That is, Ps(Π1) = {(n, n)|n≥1}∪{(n, n + 1) |n≥1}. It is worth noting that the previous system uses only uniport rules (only one object passes through a synapse, in either direction). 209 The functioning of the second example we discuss here, Π2, is much more intricated. Instead of giving this system in a formal manner, we present it pictorially, in Figure 2, following the same conventions as in Figure 1. The output cell is 1 and the only terminal object is a. Figure 2. The system Π2(rules and initial configuration) ¹¸ º· ¹¸ º· &% '$ "! #à ? ¾ 6 ¾ QQQQQQQQQQQ Q ? 1 2 3 s00 s0 s s s ab def # # (s0, g/def, s) (s, b/b0b0a3c, s0) (s, b/b0a2, s) (s, #/#, s) (s0, λ/def, s00) (s00, λ/b, s00) (s, c/λ, s0) (s0, b/#, s) (s0, λ/d, s) (s, c/λ, s) (s, λ/d, s) (s, λ/e, s0) (s0, b0/b, s0) (s0, b0/#, s0) (s0, b0/bf, s00) (s00, b0/#, s00) (s00, g/λ, s) (s, def/c, s) (s, b/λ, s) (s, b/λ, s0) (s, λ/g, s) This system computes the squares of natural numbers, in the following way. We start with objects abdef in cell 1. The objects def go along the synapse (0,1) and change its state to s, bringing gin cell 1; this object passes to cell 3, changing the state of the synapse to sand then exits through the synapse (0,3). Assume that we are in a configuration with all synapses in state s, with n2copies of object aand ncopies of bpresent in cell 1; initially, after the steps mentioned above, this is the case. Each copy of bis sent to the environment, in exchange of b0and two copies of a; the last copy of bfrom cell 1 is exchanged for two copies of b0and three copies of a. In this way, the number of copies of abecomes n2+ 2n+ 1 = (n+ 1)2. In the last step, also cis brought in cell 1; this object passes to cell 2, “opening” this synapse for object b; if any copy of bis still present in cell 1, then the trap-object # is brought in cell 1 and the computation never stops. From cell 2, cpasses to cell 3, and from here exits to the environment, bringing in cell 3 the objects def. The object dwill go to cell 2 and then to cell 1, restoring the state of the synapse (1,2) to s, while egoes to cell 1, changing the state of the synapse (1,3) to s0. This makes possible the exchange of each copy of b0from cell 1 with a copy of bfrom cell 3 (this last object is continuously brought in cell 3 from the environment – but the process can be finished by passing the synapse (0,3) to state s0; however, if this happens too early, 210 then the object # is moved from cell 3 to cell 1 and the computation will last forever). The exchange of b0with bcontinues until changing the state of the synapse (1,3) to s00, and also moving ffrom cell 3 to cell 1. This should complete the change of b0, otherwise again the trap-object is moved to cell 1. In this moment, all objects def are again in cell 1, as in the initial configuration, hence we can iterate the process (thus passing to the square of the next natural number). If, instead, we send def outside by means of the rule (s0, λ/def, s00), then the synapse (0,1) passes to state s00, which only allows the exit of all objects bfrom cell 1. In this way, only copies of object aremain in cell 1. The rule (s0, λ/def, s00) can be used also in the initial configuration, hence also the square of 1 is obtained. Consequently, Ps(Π2) = {n2|n≥1}. Note that in the halting configuration, only copies of the terminal object aare present in the output cell. As we will see soon, the same set of numbers can be computed by systems with a small number of cells or states, and with simpler rules. 4 Technical Prerequisites In the proofs from the next section we will use the register machines and the matrix grammars (without appearance checking), that is why we introduce here these computing devices. In what concerns the register machines, we refer to [10] for original definitions, and to [5], [14] for definitions like that we use in this paper. An n-register machine is a construct M= (n, R, l0, lh),where nis the number of registers, Ris a finite set of instructions injectively labelled with elements from a given set lab(M), l0is the initial/start label, and lhis the final label. The instructions are of the following forms: –l1: (add(r), l2), Add 1 to the contents of register rand proceed to the instruction (labelled with) l2. (We say that we have an ADD instruction.) –l1: (sub(r), l2, l3), If register ris not empty, then subtract 1 from its contents and go to instruction l2, otherwise proceed to instruction l3. (We say that we have a SUB instruction.) –lh:halt, Stop the machine. The final label lhis only assigned to this instruction. A register machine Mis said to recognize a vector (s1, . . . , sk) of natural numbers if, starting with the instruction with label l0, with the numbers s1, . . . , skplaced in the first k registers (and the other registers containing the number 0), the machine stops (it reaches the instruction lh:halt) with all registers containing the number 0. The register machines are know to be computationally universal, equal in power to Turing machines: they recognize exactly the sets of vectors of natural numbers which can be recognized/computed by Turing machines, that is, the family PsRE. Without loss of the generality, in the proofs from the following section we will assume that in each ADD instruction l1: (add(r), l2) and in each SUB instruction l1: (sub(r), l2, l3) the labels l1, l2, l3are mutually distinct. This goal can be easily achieved. For instance, 211 in the case of SUB instructions, we replace each instruction l1: (sub(r), l2, l3) with the instructions l1: (sub(r), l0 2, l00 3), l0 2: (add(n+ 1), l000 2), l000 2: (sub(n+ 1), l2, lh), l00 3: (add(n+ 1), liv 3), liv : (sub(n+1), l3, lh), where n+1 is a new register (the same for all starting SUB instructions), and all primed labels are distinct and different from the initial labels. We also use below the matrix grammars. For details, we refer to [3] and to the chapter of [13] devoted to regulated rewriting, and we introduce here only the particular case we need below. A matrix grammar (without appearance checking) is a construct G= (N, T, S, M), where N, T are disjoint alphabets, S∈N, and Mis a finite set of ordered 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); 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,wi=w0 iAiw00 i, wi+1 =w0 ixiw00 i, for some w0 i, w00 i∈(N∪T)∗. The language generated by Gis defined by L(G) =}w∈T∗|S=⇒∗w}. By MAT we denote the family of languages generated by matrix grammars. It is known that PsCF ⊂PsMAT ⊂PsRE (for instance, PsMAT contains non-semilinear sets of vectors, which is not the case with PsCF; on the other hand, the one-dimensional vectors from PsMAT are semilinear, while PsRE contains non-semilinear sets of numbers). The power of matrix grammars is not decreased if we only work with matrix grammars in the binary normal form (see [3]). A grammar G= (N, T, S, M) is in this form if it has N=N1∪N2∪ {S}, where these three sets are mutually disjoint, and each matrix in M is in one of the following forms: 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→λ, A →x), with X∈N1, A ∈N2,and x∈T∗,|x| ≤ 2. Moreover, there is only one matrix of type 1 and a matrix of type 3 is used only once, in the last step of a derivation. In the following we shall use a slightly different variant of this binary normal form by adding one new non-terminal findicating its unique final “state”, i.e., from a matrix grammar G= (N, T, S, M) in the binary normal form as above we construct the matrix grammar Gf= (N∪ {f}, T, S, Mf) in f-binary normal form with Mf= (M− {(X→λ, A →x)|(X→λ, A →x)∈M, X ∈N1, A ∈N2, x ∈T∗}) ∪ {(X→f, A →x)|(X→λ, A →x)∈M, X ∈N1, A ∈N2, x ∈T∗}) ∪ {(f→λ)}. Hence, Mfcontains rules of the following forms: 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→f, A →x), with X∈N1, A ∈N2,and x∈T∗,|x| ≤ 2, 4. (f→λ). 212 Moreover, there is only one matrix of type 1 and only one matrix of type 4, which is only used in the last step of a derivation yielding a terminal result.It is obvious that a usual tissue-like P system (without states) can be considered as having the same state associated with all synapses, never changing. Because P systems with one membrane and using antiport rules of weight at least two are universal in the case of maximally parallel use of rules (see, e.g., [7], [6]), it is expected that a similar result holds true also in our case. However, this does not happen: if we have only one cell, irrespective how many states and how complex rules we use, we get at most the Parikh images of matrix languages (without appearance checking). The explanation of this important difference between our results and those from [7], [6] lies in the difference between the way the two types of systems work: sequentially here, in a maximally parallel manner in the mentioned papers (as we have mentioned in the Introduction, the maximal parallelism together with the halting condition for defining the successful computations provides the necessary tools for simulating the appearance checking, which is not the case for the sequential use of rules; then, the appearance checking is exactly the difference between MAT and universality – matrix grammars with appearance checking are equivalent to Turing machines). However, universality can be obtained also in our case as soon as we use at least two cells. We start with the characterization of the Parikh images of matrix languages. Lemma 4.1 PsMAT ⊆PsOtP1(state∗, anti1). Proof. Let us consider a matrix grammar G= (N1∪N2∪ {S, f}, T, S, M) in the f-binary normal form. We construct the tissue-like P system Π=(O, T, K, A0Z, O, {(0,1)}, X0, R(0,1),1), O=N2∪T∪ {Z}, K=N1∪ {f} ∪ {hX, αi | X∈N1∪ {f}, α ∈N2∪T}, R(0,1) ={(X, α/A, Y )|(X→Y, A →α)∈M, X∈N1, Y ∈N1∪ {f}, A ∈N2, α ∈N2∪T∪ {λ}} ∪ {(X, α1/A, hY, α2i),(hY, α2i, α2/λ, Y )|(X→Y, A →α1α2)∈M, X∈N1, Y ∈N1∪ {f}, A ∈N2, α1, α2∈N2∪T} ∪ {(f, A/A, f)|A∈N2}∪{(f, λ/Z, f)} ∪ {(X, Z/Z, X)|X∈N1}, where (S→X0A0) is the initial matrix of M. The matrices (X→Y, A →x) of Mare simulated by simultaneously changing the state of the unique synapse and exchanging an internal object Afor the multiset x. If xconsists of at most one symbol, then the simulation is done in only one step. If x=α1α2, then the objects α1, α2are brought into the system in two consecutive steps. When the state fis introduced, we check whether the derivation in Gis terminal and only in the affirmative case we halt. As long as the state of the synapse (0,1) is not f, the computation continues, at least by a rule of the form (X, Z/Z, X) for some X∈N1. The auxiliary object Zis sent out by means of the rule (f, λ/Z, f) and then the computation stops. Consequently, ΨT(L(G)) = Ps(Π) and the proof is complete. 2 The number of states can be decreased to one if we can use more powerful rules. 213 Lemma 4.2 PsMAT ⊆PsOtP1(state1, anti2). Proof. Consider again a matrix grammar G= (N1∪N2∪ {S, f}, T, S, M) in the f-binary normal form and construct the tissue-like P system Π=(O, T, {s}, X0A0Z, O, {(0,1)}, s, R(0,1),1), O=N1∪ {f} ∪ N2∪T∪ {hX, αβi | X∈N1∪ {f}, α, β ∈N2∪T}, R(0,1) ={(s, Y x/XA, s)|(X→Y, A →x)∈M X∈N1, Y ∈N1∪ {f}, A ∈N2, x ∈N2∪T∪ {λ}} ∪ {(s, Y hY, α1α2i/XA, s),(s, α1α2/hY, α1α2i, s)|(X→Y, A →α1α2)∈M, X∈N1, Y ∈N1∪ {f}, A ∈N2, α1, α2∈N2∪T} ∪ {(s, α/α, s)|α∈N1∪N2} ∪ {(f, λ/Z, f)}, where (S→X0A0) is the initial matrix of M. The state plays no rˆole, the matrices of Mare simulated by the antiport rules. As long as at least a nonterminal from N1∪N2is present, the computation must continue. The equality ΨT(L(G)) = Ps(Π) is obvious and this completes the proof. 2 We pass now to considering the opposite inclusions, proving that one-cell systems cannot exceed the power of matrix grammars, irrespective how many states and how complex rules are used. Lemma 4.3 PsOtP1(state∗, anti∗)⊆PsMAT. Proof. Let Π = (O, T0, K, w1, E, {(0,1)}, s0, R(0,1),1) be a tissue-like P system. We construct the matrix grammar G= (N, T0, S, M) with N=K∪ {s0|s∈K}∪{a0|a∈O}∪{S}, T={s00 |s∈K} ∪ O, and the following matrices: 1. (S→s0h(w1)), 2. (s1→s2h(x)), for (s1, x/λ, s2)∈R(0,1), 3. (s1→s2, x0 1→λ, . . . , x0 k→λ), for (s1, λ/x, s2)∈R(0,1), for x=x1x2. . . xk,k≥1, with xi∈O, 1≤i≤k, 4. (s1→s2, y0 1→x, y0 2→λ, . . . , y0 k→λ), for (s1, x/y, s2)∈R(0,1), for y=y1y2. . . yk,k≥1, with yi∈O, 1≤i≤k, 5. (s→s0, a0→a), (s0→s0, a0→a),for s∈K, a ∈O, (s0→s00),for s∈K, where his the morphism which replaces each a∈Owith a0. In the presence of nonterminals from K, we simulate the rules from R(0,1); at any moment we can introduce a primed state, in the presence of which we transform each a0 214 # " à ! µ´ ¶³ µ´ ¶³ µ´ ¶³ µ´ ¶³ µ´ ¶³ HHHHHHHHHHHHH Hj ZZZZZZZZ Z~ CCCCCC CW ½ ½ ½ ½ ½ ½ ½ ½ ½= © © © © © © © © © © © © © ©¼ - - - - - - ? ? ? ? - µ´ ¶³ µ´ ¶³ µ´ ¶³ -6 - - ¾ ¾ ¾ µ´ ¶³ µ´ ¶³ µ´ ¶³ µ´ ¶³ µ´ ¶³ µ´ ¶³ - - ´ ´ ´ ´ ´+ - - - - Z Z Z Z Z} A A A A A AK l0 ssss 12ikk+ 1 s ss s s s . . . . . . s s s s s s add1 s # # # s addi s ... s ... s addu k+ 2 s s s sub1sub0 1 . . . s s subisub0 i s s ... s s subvsub0 v (s, ai/λ, s0) (s0, bi/λ, s) (s, ei/λ, s00 ) s (s, ei/λ, s0) (s0, l0/λ, s0) (s, ai/λ, s) (s, bi/λ, s) (s, l0/λ, s) (s, #/#, s) (s, λ/lh, s) #e #e #e (s, ar/λ, s) (s, l2/λ, s) (s, e/λ, s0) (s, l1/λ, s0) (s0, λ/ar, s00 ) (s00 , λ/l2, s) (s0, λ/#, s) (s00 , λ/#, s) (s, l1/λ, s0) (s0, ar/λ, s00 ) (s00 , λ/l2, s) (s00 , λ/#, s) (s0, λ/l3, s) (s, l2/e, s0) (s0, e/λ, s) (s, l3/λ, s) (s, l2/l1, s0) (s0, l3/λ, s) λ λ λ λ λ Figure 3. The structure of the system from the proof of Theorem 4.4 The SUB instruction subi, of the form l1: (sub(r), l2, l3), is simulated through the interaction of cell k+2 with the cells subiand sub0 i, in the following way. First, the object l1is sent from cell k+ 2 to cell subi, and the state of the synapse (k+ 2, subi) is changed to s0. In the next step, l1exits cell subi, being exchanged with l2, and the state of the synapse (0, subi) becomes s0. Simultaneously, if any copy of aris present in cell k+2, then the rule (s0, ar/λ, s00) is used, hence one copy of arleaves cell k+ 2 and the state of the synapse (k+ 2, subi) becomes s00. If no copy of arexists in cell k+ 2, then the state of the synapse remains s0and no rule is used here. In the third step, if the state of the synapse (k+ 2, subi) is s00, then l2passes from cell subito cell k+ 2, returning the state of this synapse to s(and making possible the simulation of another rule). At the same time, l3 enters cell subi, returning the state of the synapse (0, subi) to s. Instead of passing to cell k+ 2, the object l2can also pass to cell sub0 i, but in this case the trap-object should be 221 sent to cell k+ 2, by means of the rule (s00, λ/#, s), and the computation will never stop. If the simulation of the case when arexists is correct, hence l2enters cell k+ 2, then l3 will pass in the next step to cell sub0 i: the state of the synapse (subi, sub0 i) has remained s, hence the rule (s, l3/λ, s)∈R(subi,sub0 i)can be used. If no copy of aris present in cell k+2, then, after passing l1to cell subiand exchanging it with l2from the environment, l2must pass to cell sub0 i, in exchange with e, replacing state swith s0on the synapse (subi, sub0 i). At the same time, l3enters cell subi. In the next step, l3cannot go to cell sub0 i, because of the state s0of the synapse (subi, sub0 i), hence it will go to cell k+ 2, by means of the rule (s0, λ/l3, s) (the state of this synapse has remained s0, because no arhas changed s0into s00 as above). At the same time, the auxiliary object epasses back from cell subito cell sub0 i, returning the state of this synapse to s. The simulation of the SUB instruction is complete, the states of the synapses are again s, hence the simulation of instructions of Mcan continue. In this process, it is essential that the labels l1, l2, l3from each instruction l1: (sub(r), l2, l3) are mutually different. When the halt label lhis introduced in cell k+2, it exits by means of the rule (s, λ/lh, s) and the computation stops. We conclude that N(M) = Ps(Π) and this ends the proof. 2 5 Further Variants The previous systems work in the generative mode, using the rules in a sequential manner. Obvious variations are obtained by considering the accepting mode. A possibility is to designate a cell as the input one, and to start the computation by introducing a multiset in that cell; this multiset is accepted if and only if the computation halts. Because in the accepting mode we do not have to take care of the way the initial values of the register machine simulated by a P system as in Theorems 4.2, 4.3, 4.4 are introduced, we can save states in the constructions from the proofs of these theorems. This is especially of interest in the case of Theorem 4.3, where we use the two states only for introducing the input, and for the computation one state suffices; therefore, in the accepting case, the universality is obtained with only one state. Another possibility is to consider as accepted the sequence of objects taken from the environment during a halting computation (as in [2] and [4]) and in this way we obtain language recognizing devices. The first example from Section 3 works in a way for which this mode to define the recognized language is apparent – the language recognized by Π1 is non-regular. Then, of interest is to consider a parallel use of rules. In order to avoid conflicts in changing the labels, in each step, on each synapse, all rules leading from a state sto the same state s0should be considered. More specifically, “tables” of the form Ti,j(s, s0) = {(s, x/y, s0)|(s, x/y, s0)∈R(i,j)}can be defined, for each synapse (i, j) and for each pair (s, s0) of states; in each step one table is non-deterministically chosen and then used in a maximally parallel manner. All these possibilities remain to be investigated. In general, we believe that the tissuelike P systems deserve further research efforts, motivated both by the mathematical problems they raise and also by the interesting connections with inter-cell communication in 222 tissues (an important biological fact, see, e.g., [8]), neuron interaction in the brain, distributed computing (internet included). References [1] F. Bernardini, A. P˘aun, Universality of minimal symport/antiport: Five membranes suffice. In Aspects of Molecular Computing. Essays Dedicated to Tom Head on the Occasion of His 70th Birthday (N. Jonoska, Gh. P˘aun, G. Rozenberg, eds.), Lecture Notes in Computer Science LNCS 2950, Springer-Verlag, Berlin, 2004, 43–54. [2] E. Csuhaj-Varju, G. Vaszil, P automata or purely communicating accepting P systems. In [12], 219–233. [3] J. Dassow, Gh. P˘aun, Regulated Rewriting in Formal Language Theory. SpringerVerlag, Berlin, 1989. [4] R. Freund, M. Oswald, A short note on analysing P systems with antiport rules. Bulletin of the EATCS, 78 (October 2002), 231–236. [5] R. Freund, Gh. P˘aun, On the number of non-terminal symbols in graph-controlled, programmed and matrix grammars. Proc. Conf. Universal Machines and Computations, Chi¸sin˘au, 2001 (M. Margenstern, Y. Rogozhin, eds.), Lecture Notes in Computer Science 2055, Springer-Verlag, Berlin, 2001, 214–225. [6] R. Freund, Gh. P˘aun, On deterministic P systems. Submitted, 2003. [7] P. Frisco, H.J. Hoogeboom, Simulating counter automata by P systems with symport/antiport. In [12], 288–301. [8] W.R. Loewenstein: The Touchstone of Life. Molecular Information, Cell Communication, and the Foundations of Life. Oxford University Press, New York, Oxford, 1999. [9] C. Mart´ın-Vide, J. Pazos, Gh. P˘aun, A. Rodr´ıguez-Pat´on, Tissue P systems. Theoretical Computer Sci., 296, 2 (2003), 295–326. [10] M.L. Minsky, Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey, USA, 1967. [11] Gh. P˘aun, Computing with Membranes: An Introduction. Springer-Verlag, Berlin, 2002. [12] Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron, eds., Membrane Computing. International Workshop WMC 2002, Curtea de Arge¸s, Romania, Revised Papers.Lecture Notes in Computer Science 2597, Springer-Verlag, Berlin, 2003. [13] G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages (3 volumes), Springer-Verlag, Berlin, 1997. [14] P. Sosik, R. Freund, P systems without priorities are computationally universal. In [12], 400–409. 223