Partial Versus Total Halting in P Systems

Partial Versus Total Halting in P Systems Artiom Alhazov1, Rudolf Freund2, Marion Oswald2, Sergey Verlan3 1Department of Information Technologies Abo Akademi University Turku Center for Computer Science FIN-20520 Turku, Finland [email protected] and Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD-2028, Moldova [email protected] 2Faculty of Informatics Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria {rudi,marion}@emcc.at 3LACL, D´epartement Informatique UFR Sciences et Technologie Universit´e Paris XII 61, av. G´en´eral de Gaulle 94010 Cr´eteil, France [email protected] Summary. We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems working in different derivation modes. 1 Introduction In the seeding papers of Gheorghe P˘aun (e.g., see [19], [9]) introducing membrane computing, membrane systems were introduced as systems with a hierarchical (tree-like) structure and the rules being applied in a maximally parallel manner; the results were taken as the contents of a specified output membrane in the final configurations of halting computations, i.e., at the end of computations to which no rule was applicable anymore. In this paper, we investigate a new variant of halting – partial halting –, see [13], i.e., we consider a computation to halt as soon 2 A. Alhazov, R. Freund, M. Oswald, S. Verlan as not for all membranes a rule is applicable anymore at the same time. Moreover, we especially also consider the derivation mode of minimal parallelism (e.g., see [7]), i.e., for each membrane, at least one rule – if possible – has to be applied, but it is not required to use a maximal multiset of rules. Finally, in the asynchronous derivation mode an arbitrary number of rules can be applied in parallel, and in the sequential derivation mode exactly one rule has to be applied in each computation step. The paper is organized as follows: We first recall some well-known definitions, notions, and results for matrix grammars and register machines and then define a special model of P systems – P systems with permitting contexts – that covers a lot of variants known from the literature such as antiport P systems, P systems with conditional uniport rules, evolution/communication P systems, and P systems with boundary rules. For establishing our results, we especially consider the new stopping mode of partial halting; we first state some general result and then show that P systems using membrane rules with permitting contexts working in the minimally parallel mode and with partial halting can only generate matrix languages. On the other hand, we improve or newly establish results showing that specific variants of P systems with permitting contexts such as antiport P systems, P systems with conditional uniport rules, and evolution/communication P systems together with the newly introduced variant of minimal parallelism and with total halting are computationally complete. 2 Definitions In this section, we first recall some basic notions and notations and then give precise definitions for matrix grammars, register machines, and a general model of P systems using membrane rules with permitting contexts as they are considered in this paper; moreover, we show how several well-known models of P systems (P systems with symport/antiport rules, P systems with conditional uniport rules, evolution/communication P systems, P systems with boundary rules) can be interpreted as special variants of this general model. 2.1 Preliminaries For the basic elements of formal language theory needed in the following, we refer to [8] and [23]. We just list a few notions and notations: Ndenotes the set of nonnegative integers. V∗is the free monoid generated by the alphabet Vunder the operation of concatenation and the empty string, denoted by λ, as unit element; by NRE and NREG we denote the family of recursively enumerable sets and regular sets of non-negative integers, respectively. 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, ..., an) is |x|a1, ..., |x|an. The Parikh image of a language Lover (a1, ..., an) Partial Versus Total Halting in P Systems 3 is the set of all Parikh vectors of strings in L. For a family of languages F, the family of Parikh images of languages in Fis denoted by P sF. A (finite) multiset hm1, a1i... hmn, aniwith mi∈N, 1 ≤i≤n, can be represented by any string xthe Parikh vector of which with respect to (a1, ..., an) is (m1, ..., mn); if mi= 1 for all 1≤i≤n, then xcan also be represented by the corresponding set {m1, ..., mn}. The family of recursively enumerable languages is denoted by RE, the family of context-free and regular languages by CF and REG, respectively. The corresponding families of languages over a k-letter alphabet are denoted by X(k), X∈ {RE, CF, REG}; for k= 1 we obtain PsX (1) = NX and, moreover, NREG =NCF. 2.2 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. The family of languages generated by matrix grammars without appearance checking (over a one-letter alphabet) is denoted by MAT λ(MATλ(1)). It is known that CF ⊂MAT λ⊂RE as well as P sCF ⊂P sMAT λ⊂PsRE, and especially NREG =NCF =P sMAT λ(1) ⊂NRE. For further details about matrix grammars we refer to [8] and to [23]. 2.3 Register Machines The proofs of the results establishing computational completeness in the area of P systems often are based on the simulation of register machines; we refer to [17] for original definitions, and to [11] for definitions like those we use in this paper: An n-register machine is a construct M= (n, B, P, p0, ph),where nis the number of registers, Bis a set of labels for injectively labelling the instructions in P,p0is the initial/start label, and phis the final label. The instructions are of the following forms: –p: (A(r), q, s) (ADD instruction) Add 1 to the contents of register rand proceed to one of the instructions (labelled with) qand s. 4 A. Alhazov, R. Freund, M. Oswald, S. Verlan –p: (S(r), q, s) (SUB instruction) If register ris not empty, then subtract 1 from its contents and go to instruction q, otherwise proceed to instruction s. –ph:halt (HALT instruction) Stop the machine. The final label lhis only assigned to this instruction. A (non-deterministic) register machine Mis said to generate a vector (n1, ..., nβ) of natural numbers if, starting with the instruction with label p0and all registers containing the number 0, the machine stops (it reaches the instruction ph:halt) with the first βregisters containing the numbers n1, ..., nβ(and all other registers being empty). Without loss of generality, in the succeeding proofs we will assume that for non-deterministic register machines in each ADD instruction p: (A(r), q, s)∈P and in each SUB instruction p: (S(r), q, s)∈Pthe labels p, q, s are mutually distinct (for a proof see [16]). A register machine is called deterministic if and only if in every ADD instruction p: (A(r), q, s)∈Pwe have q=s; in this case we also write p: (A(r), q) instead. A deterministic register machine Mis said to accept a vector (n1, ..., nβ) of natural numbers if, starting with the instruction with label p0and registers 1 to βcontaining the numbers n1, ..., nβ, the machine stops (it reaches the instruction ph:halt) with the all registers being empty. The register machines are known to be computationally complete, equal in power to (non-deterministic) Turing machines: they generate exactly the sets of vectors of non-negative integers which can be generated by Turing machines, i.e., the family PsRE. The results proved in [10] (based on the results established in [17]) and [11], [14] immediately lead to the following results: Proposition 1. For any recursively enumerable set L⊆Nβof vectors of nonnegative integers there exists a non-deterministic (β+ 2)-register machine Mgenerating Lin such a way that, when starting with all registers 1to β+2 being empty, Mnon-deterministically computes and halts with niin registers i, 1≤i≤β, and registers β+ 1 and β+ 2 being empty if and only if (n1, ..., nβ)∈L. Moreover, the registers 1to βare never decremented. Proposition 2. For any recursively enumerable set L⊆Nβof vectors of nonnegative integers there exists a deterministic (β+ 2)-register machine Maccepting Lin such a way that, when starting with n1, ..., nβin registers 1to βand with register β+ 1 and β+ 2 being empty, Mhalts with all registers being empty if and only if (n1, ..., nβ)∈L. 2.4 A General Model of P Systems with Permitting Contexts We now introduce a general model of P systems with permitting contexts covering the most important models of communication P systems as well as evolution/communication P systems. For the state of the art in the P systems area, we refer to the P systems web page [25]. Partial Versus Total Halting in P Systems 5 AP system (of degree d, d ≥1) with permitting contexts (in the following also called P system for short) is a construct Π= (V, T, E, µ, w0, w1, . . . , wd, R1, . . . , Rd, io) where 1. Vis an alphabet; its elements are called objects; 2. T⊆Vis an alphabet of terminal objects; 3. E⊆Vis the set of objects occurring in an unbounded number in the environment; 4. µis a membrane structure consisting of dmembranes (usually labelled with i and represented by corresponding brackets [iand ]i,1≤i≤d); 5. wi,1≤i≤d, are strings over Vassociated with the regions 1,2, . . . , d of µ; they represent multisets of objects initially present in the regions of µ;w0represents the multiset of objects from VrEinitially present in the environment (in the following we usually shall assume w0=λ); 6. Ri,1≤i≤d, are finite sets of membrane rules with permitting contexts over Vassociated with the membranes 1,2, . . . , d of µ; these evolution rules in Ri are of the form u w[x z→v w[y z, where w, z ∈V∗are the contexts in the region outside membrane iand inside membrane i, respectively, uoutside membrane iis replaced by vand xinside membrane iis replaced by y; 7. iois a number between 1 and dand it specifies the output membrane of Π. The rule u w[x z→v w[y zfrom Riis applicable if and only if the multiset uw occurs in the region outside membrane i(in the following also denoted by ˆı) and the multiset xz occurs in the region inside membrane i. The application of this rule results in subtracting the multiset identified by ufrom the multiset in ˆıand adding vinstead as well as subtracting xand adding yin the region inside membrane i. The permitting contexts wand zthemselves or subsets of wand zcan be (part of) permitting contexts in other rules and, moreover, even be modified by another rule in the same derivation step. On the other hand, any object can be modified, i.e., be part of uor xin a rule u w[x z→v w[y z, by only one application of one rule in each derivation step. The rules to be applied in parallel and the objects to be modified by these rules are chosen in a non-deterministic way. Instead of writing u w[x z→v w[y z∈Riwe can also write u w[i x z→v w[i y zand in this way collect all rules from the Ri, 1 ≤i≤d, in one single set of rules R=u w[i x z→v w[i y z|u w[x z→v w[y z∈Ri. The membrane structure and the multisets represented by wi,0≤i≤d, in Π constitute the initial configuration of the system. In the maximally parallel derivation mode, a transition from one configuration to another one is obtained by the application of a maximal multiset of rules, i.e., no additional rules could be applied anymore to the objects occurring in the current configuration. The system continues maximally parallel derivation steps until there remain no applicable rules in any region of Π; then the system halts (total halting). We consider the number of objects from Tcontained in the output membrane ioat the moment when the system halts as the result of the underlying 6 A. Alhazov, R. Freund, M. Oswald, S. Verlan computation of Πyielding a vector of non-negative integers for the numbers of terminal symbols in the output membrane i0; observe that here we do not count the non-terminal objects present in the output membrane. The set of results of all halting computations possible in Πis denoted by P s (Π), respectively. Below, we shall consider variants of P systems using only rules of very restricted types α. The family of all sets of vectors of non-negative integers computable by P systems with dmembranes and using rules of type αis denoted by P sgOPd(α, max, H). When using the minimally parallel derivation mode, in each derivation step we choose a multiset of rules from the Riin such way that to this chosen multiset no rule from a set Rjfrom which no rule has been taken so far, could be added anymore to be applied in parallel with the rules already chosen. In the asynchronous and the sequential derivation mode, in each derivation step we apply an arbitrary number of rules/ exactly one rule, respectively. The corresponding families of sets of vectors of non-negative integers generated by P systems with dmembranes and using rules of type αare denoted by P sgOPd(α, X, H), X∈ {min, asyn, sequ}. If instead of the total halting we take partial halting, i.e., computations halting as soon as in at least from one set of rules no rule is applicable anymore, the corresponding families are denoted by P sgOPd(α, X, h), X∈ {max, min, asyn, sequ}. All these variants of P systems can also be considered as accepting devices, the input being given as the numbers of objects in the distinguished membrane i0. The corresponding families of sets of vectors of non-negative integers accepted by P systems with dmembranes and using rules of type αare denoted by P saOPd(α, X, Y ), X ∈ {max, min, asyn, sequ},Y∈ {H, h}. In this case, it also makes sense to consider deterministic P systems, i.e., systems where for each configuration obtained in this system we can derive at most one configuration. The corresponding families are denoted by DP saOPd(α, X, Y ). If we only count the number of terminal objects and do not distinguish between different (terminal) objects, in all the definitions given above, we replace P s by N. When the parameter dis not bounded, it is replaced by ∗. In the following, we now consider several restricted variants of membrane rules with permitting contexts well known from the literature. P systems with symport/antiport rules For definitions and results concerning P systems with symport/antiport rules, we refer to the original paper [18] as well as to the overview given in [22]. An antiport rule is a rule of the form u[x→x[uusually written as (x, out;u, in), ux 6=λ. Asymport rule is of the form [x→x[ or u[→[uusually written as (x, out), x6=λ, or (u, in), u6=λ, respectively. The weight of the antiport rule (x, out;u, in) is defined as max {|x|,|u|}. Using only antiport rules with weight kinduces the type αusually written as antik. The weight of a symport rule (x, out) or (u, in) is defined as |x|or |u|, respectively. Using only symport rules with weight kinduces the type αusually written as Partial Versus Total Halting in P Systems 7 symk. If only antiport rules (x, out;u, in) of weight ≤2 and with |x|+|u| ≤ 3 as well as symport rules of weight 1 are used, we shall write anti20. P systems with conditional uniport rules Aconditional uniport rule is a rule of one of the forms ab [→b[a, [ab →a[b, a[b→[ab ,b[a→ab [ , with a, b ∈V; in every case, the object ais moved across the membrane, whereas the object bstays where it is. Using only rules of that kind induces the type uni1,1. Conditional uniport rules were first considered in [24] for the case of tissue P systems, showing computational completeness with maximal parallelism and total halting (using 24 cells). P systems with boundary rules and evolution/communication P systems In P systems with boundary rules as defined in [4], evolution rules as well as communication rules with permitting contexts are considered. Usually, we only consider evolution rules that are non-cooperative, i.e., of the form a→vwith a∈Vand v∈V∗; a rule a→v∈Ricorresponds to [a→[v∈Riin our general notation. The communication rules are symport or antiport rules with permitting contexts, i.e., of the form u w[x z→x w[u z. In [5], boundary rules of the form u[x→v[yare considered, i.e., rewriting on both sides of the membrane. In evolution/communication P systems as introduced in [6], we allow non-cooperative evolution rules as well as antiport (of weight k) and symport rules (of weight l), and we denote this type of rules by (ncoo, antik, syml). 3 Results After recalling some general results for the new variant of partial halting already established in [13], which immediately yield comparable computational completeness results in the case of antiport P systems for total and partial halting, we prove that P systems with permitting contexts working in the sequential, in the asynchronous or even in the minimally parallel derivation mode and with partial halting can only generate Parikh sets of matrix languages (regular sets of non-negative integers). On the other hand, specific variants of P systems with permitting context such as P systems with antiport rules, P systems with symport rules, P systems with conditional uniport rules, and evolution/communication P systems together with the newly introduced variant of minimal parallelism and with total halting are computationally complete. 3.1 General Observations Looking carefully into the definitions of the derivation modes as well as the halting modes explained above, we observe the following general results already established in [13]: 8 A. Alhazov, R. Freund, M. Oswald, S. Verlan Theorem 1. Any variant of P systems yielding a family of sets of non-negative integers Fwhen working in the derivation mode X,X∈ {max, min, asyn, sequ}, with only one set of rules assigned to a single membrane and stopping with total halting yields the same family Fwhen working in the derivation mode Xwith only one set of rules assigned to a single membrane when stopping with partial halting, too. Theorem 2. Any variant of P systems yielding a family of sets of non-negative integers Fwhen working in the derivation mode X,X∈ {asyn, sequ}, with only one set of rules assigned to a single membrane and stopping with total or partial halting, respectively, yields the same family Fwhen working in the minimally parallel derivation mode and stopping with the corresponding halting mode, too. For any P system using rules of type α, with a derivation mode X,X∈ {min, asyn, sequ}, and partial halting, we only get Parikh sets of matrix languages (regular sets of non-negative integers): Theorem 3. For every X∈ {min, asyn, sequ}, PsgOP∗(α, X, h)⊆PsMAT λand NgOP∗(α, X, h)⊆NREG. Proof. We only prove P sgOP∗(α, X, h)⊆P sMAT λ; the second inequality NgOP∗(α, X, h)⊆NREG is a direct consequence of the first one, having in mind that NREG =PsMAT λ(1). Hence, let us start with a P system Π= (V, T, E, µ, w1, . . . , wd, R1, . . . , Rd, io) using rules of a specific type α, working with the derivation mode X. The stopping condition h– partial halting – then guarantees that in order to continue a derivation there must exist a sequence of rules hr1, . . . , rdiwith ri∈Ri, 1 ≤i≤d, such that all these rules are applicable in parallel. We now consider all functions δwith δ(i, r)∈ {0,1}and δ(i, r) = 1 if and only if the rule r∈Ri, 1 ≤i≤d, is assumed to be applicable to the current sentential form in a matrix grammar GM=VM, T, S, Mgenerating representations of all possible configurations computable in the given P system Πwith the representation of an object ain membrane ias (i, a). We start with the matrix (S→Kh (w)) where h(w) is a representation of the initial configuration. A derivation step in Πthen is simulated in GMas follows: (i) We non-deterministically choose some δas described above and use the matrix (K→K(δ)). Afterwards, we use the matrix (K(δ)→K0(δ), s1, ..., sm) where each subsequence sj, 1 ≤j≤m, checks the applicability of a rule r∈Riwith δ(i, r) = 1. For checking the applicability of u w[x z→v w[y z∈Ri, we have to check for the appearance of uw in membrane ˆı(the outer region of membrane i) and for the appearance of xz in the (inner) region of membrane i. This can be done by the subsequence ((ˆı, uw)→(ˆı, uw),(ˆı, uw)→(ˆı, uw),(i, xz)→(i, xz),(i, xz)→(i, xz)), where (i, v)→(i, v), for v=v1...vh,vj∈V, 1 ≤j≤h,h≥0, is a shortcut for the sequence ((i, v1)→(i, v1), ..., (i, vh)→(i, vh)) etc. (ii) After that, we non-deterministically guess a sequence of rules hr1, . . . , rdi with ri∈Ri,ri=u(i) w(i)[x(i) z(i)→v(i) w(i)[y(i) z(i), and δ(i, ri) = 1, 1 ≤ Partial Versus Total Halting in P Systems 9 i≤d, such that all these rules are applicable in parallel. This can be checked by the corresponding matrix (K0(δ)→K00 (δ), t1, ..., td, t0 1, ..., t0 d) with the subsequences ti,t0 i, 1 ≤i≤d, being defined (in the shortcut notation as above) by ti=(ˆı, u (i)) →ˆı, u (i),(i, x (i)) →i, x (i) and t0 1= ˆı, u (i)→(ˆı, u (i)) ,i, x (i)→(i, x (i)). Observe that only the objects in u(i) and x(i) are assigned to the rule ri, whereas the permitting contexts w(i) and z(i) may be contexts for another rule or be affected themselves by another rule, and, moreover, that the applicability of the rules themselves has already been checked in (i). (iii) Finally, we take different matrices depending on the derivation mode: 1. In the sequential derivation mode, we only have to take all possible matrices simulating the application of one rule u w[x z→v w[y z∈Riwith δ(i, r) = 1: (K00 (δ)→Khˆı(v)hi(y),(ˆı, u)→λ, (i, x)→λ), where the morphisms hjare defined by hj(a) = (j, a), 0 ≤j≤d,a∈V, except h0(a) = λfor a∈E (these symbols, by definition, are available in an unbounded number in the environment). 2. In the asynchronous derivation mode, we have to allow an arbitrary number of rules to be applied in parallel; we simulate the application of rules sequentially, priming the results such that they cannot be used immediately. Finally, if for the current derivation step, the application of no further rule is intended, we can deprime the result symbols to be available for the simulation of the next derivation step. In sum, we use the matrices (K00 (δ)→K000 (δ)), (K000 (δ)→K000 (δ)h0 ˆı(v)h0 i(y),(ˆı, u)→λ, (i, x)→λ) – where the morphisms h0 jare defined by h0 j(a) = (j, a0), 0 ≤j≤d,a∈V, except h0 0(a) = λfor a∈E – for every rule u w[x z→v w[y z∈Riwith δ(i, r) = 1, as well as K000 (δ)→K(δ), K(δ)→K(δ),(j, a0)→(j, a), 0 ≤j≤d,a∈V, and finally K(δ)→K. 3. For the minimally parallel mode, instead of (K00 (δ)→K000 (δ)) as in 2, we simulate the application of a sequence of rules hr1, . . . , rdiwith ri∈Ri, 1 ≤i≤d,ri=u(i) w(i)[x(i) z(i)→v(i) w(i)[y(i) z(i), and δ(i, ri) = 1 such that all these rules are applicable in parallel, which is accomplished by the matrix K00 (δ)→K000 (δ)h0 ˆ 1(v)h0 1(y)...h0 ˆ d(v)h0 d(y), ˆ 1, u (1)→λ, (1, x (1)) →λ, ..., ˆ d, u (d)→λ, (d, x (d)) →λ. As a technical detail we have to mention that it does not matter whether all the primed symbols are deprimed again, this would just make them unavailable during the next steps. Any sentential form containing primed symbols is considered to be non-terminal, hence, it cannot contribute to L(GM). Moreover, we have to point out that every symbol e∈Efrom the environment being available there in an unbounded number neither needs to be checked for appearance in ˆ 1 ( = 0) nor to be generated/eliminated or primed/deprimed, i.e., rules like (0, e)→λ, (0, e)→(0, e), (0, e)→(0, e) have to be omitted. 16 A. Alhazov, R. Freund, M. Oswald, S. Verlan The simulation of a SUB instruction p: (A(r), q, s) is performed by the following rules: I. (M0 p, p; 1,5; 2) II. (Mp, A; 3,1; 8) III. (q, M0 p; 5,1; 50) IV. (s, M0 p; 5,1; 50) V. (Mp, q; 1,3; 2) 1.(8, p, 3) 2.(6, Mp→3, p) 3.(6, M0 p→3, p) 4.(3, M0 p[Mp],6) 5.(3, Mp→6, M0 p) 6.(7, Ar→3, Mp) 7.(3, Mp[p],1) 8.(3, p →1, M0 p) 9.(1, M0 p,3) 10.(1, s →3, Mp) 11.(1, Ar[Mp],0) 12.(3, q[Mp],8) 13.(3, s[Mp],8) 14.(3, p, 7) 15.(7, p, 70) 16.(70, p, 7) The simulation usually starts with object pin membrane 8,whereas Mp, M0 p are found in membrane 6, q, x in membrane 5, and Arpossibly in membrane 7. Symbol pfirst goes from membrane 8 to membrane 3 and after that brings there symbol M0 p. After that it moves symbol M0 pto membrane 1 and brings symbol Mpto membrane 3. Further, pmoves to membrane 1 and Mpmay bring a symbol Arto membrane 3. If it succeeds, then both symbols Mpand Armove to membrane 1 and after that symbol Aris sent out. In the meanwhile pand M0 p move to membrane 5. From there, M0 pbrings either qor sto membrane 1. Now if it brought qand the register was not zero (Mpis in membrane 1) then Mpwill bring qto membrane 8. Otherwise, qwill be trapped in membrane 2. If swas brought into membrane 1 by M0 p, and the value of register was zero, then this s will move to membrane 3 and further to membrane 8. It is easy to observe that the symbols Mpand M0 preturn to membrane 6 by themselves. They can do this at any moment of the computation, but only after the state symbol qor shas returned to membrane 8 they can do this without provoking an infinite computation. 3.4 Results for Evolution/Communication P Systems For evolution/communication P systems, the constructions from [2], Theorems 1 and 2, and from [3], Theorems 4.3.1 and 4.3.2, already show the computational completeness, using two membranes, for the minimally parallel setup (when working in the maximally parallel way, the system never applies simultaneously more than one rule from the same set of rules assigned to a membrane): Corollary 4. For X∈ {min, max}, PsgOP2((ncoo, anti1, sym1), X, H) = P sRE,X∈ {min, max}. Partial Versus Total Halting in P Systems 17 We can extend these results by showing that deterministic evolutioncommunication P systems with non-cooperative evolution rules and communication rules of weight one (also see [1]) are computationally complete, using three membranes. Theorem 11. For X∈ {min, max}, DP saOP3((ncoo, sym1, anti1), X, H) = PsRE. Proof. Consider a deterministic register machine M= (n, B, P, p0, ph). Let us denote the set of labels of SUB instructions by B−. Π=V, T, V, [1[2]2[3]3]1, p0, λ, λ, R1, R2, R3,1, V=B∪ {lj|l∈B−,0≤j≤7}∪{q} ∪ {Ai|1≤i≤n}∪{ij|1≤i≤n, 1≤j≤3}, T={Ai|1≤i≤k}, R1={l→Ail0|(l:A(i), l0)∈P}∪{lj→lj+1 |l∈B−, j ∈ {0,1,2,5,6}} ∪ {l→l0i1, l4→l5q, l7→l00 |l: (S(i), l0, l00)∈P}, R2={i1→i2, i3→λ|1≤i≤n}∪{l3→l4|l∈B−}, ∪ {(i1, in),(i2, out;Ai, in),(i3, in)|1≤i≤n} ∪ {(i2, out;l3, in),(l4, out)|l: (S(i), l0, l00 )∈P}, R3={i2→i3|1≤i≤n}∪{q→λ}∪{l3→l0|l∈B−} ∪ {(i2, in),(i3, out;q, in)|1≤i≤n} ∪ {(i3, out;l3, in),(l0, out)|l: (S(i), l0, l00 )∈P}. An ADD instruction l: (A(i), l0)∈Pis implemented by the single noncooperative evolution rule l→Ail0. The simulation of a SUB instruction l: (S(i), l0, l00 )∈Pis described in a depictive way in the following tables. Decrementing register iworks as follows: step 0 1 2 3 4 region 2i1i2ai rules 2 (i1, in)i1→i2(i2, out;Ai, in) region 1lAil0i1Ail1Ail2Ail3i2 rules 1l→l0i1l0→l1l1→l2l2→l3 region 3 rules 3 (i2, in) step 5 6 7 8 region 2i3 rules 2 (i3, in)i3→λ region 1l3l3i3l0 rules 1 region 3i2i3l3l0 rules 3i2→i3(i3, out;l3, in)l3→l0(l0, out) If register iis empty, i.e., if there is no object Ai, the simulation works as follows: 18 A. Alhazov, R. Freund, M. Oswald, S. Verlan step 0 1 2 3 4 region 2i1i2i2 rules 2 (i1, in)i1→i2(i2, out;l3, in) region 1l l0i1l1l2l3 rules 1l→l0i1l0→l1l1→l2l2→l3 region 3 rules 3 step 5 6 7 8 9 10 region 2l3l4i3 rules 2l3→l4(l4, out) (i3, in)i3→λ region 1i2l4l5q l6i3l7 rules 1l4→l5q l5→l6l6→l7l7→l00 region 3i2i3i3q rules 3 (i2, in)i2→i3(i3, out;q, in)q→λ The main idea of the construction is similar to that in [1]: if the object Aiis present in region 2, it is exchanged with object i2while object l2changes to l3; otherwise object l3is exchanged with i2in the next step. The trajectory of object i2is the same in both cases: it enters membrane 3, is renamed, exits and enters membrane 2, where it is erased. The behavior of object l3indirectly depends on the presence of Aivia i2or i3: in the decrement case it enters membrane 3, is renamed to l0and returns to region 1, while in the zero-case it enters membrane 2, is renamed to l4, exits, and produces two objects; one of them helps i3, while the other one produces l00, thus finishing the simulation. 4 Conclusion In this paper, we have investigated a new variant of halting – we call it partial halting – in membrane systems where all membranes are required to allow for the application of a rule at the same time in order to keep a computation alive. Obviously, for systems with only one membrane this way of halting is equivalent with the original one where a system halts if and only if no rule is applicable anymore in the whole system – we also call this total halting. Besides this general result, we also have shown that P systems working in the minimally parallel mode, the asynchronous or the sequential derivation mode and with partial halting can only generate Parikh sets of matrix languages/regular sets, the same what we obtain with the sequential and the asynchronous derivation mode and total halting. Comparing the results for total and partial halting for the minimally parallel derivation mode elaborated above, we realize that for any of the specific restricted variants αof P systems with permitting contexts we have PsgOP∗(α, min, h)⊆P sMAT λ$P sRE =PsgOP∗(α, min, H) and NgOP∗(α, min, h) = NREG $NRE =NgOP∗(α, min, H), Partial Versus Total Halting in P Systems 19 i.e., in the case of the minimally parallel derivation mode the halting condition –total in contrast to partial halting – makes the difference. Intuitively speaking, the requirement for a computation to continue only if for every membrane a rule is applicable, together with the minimally parallel derivation mode means that we do not have the possibility of appearance checking and therefore cannot simulate the zero test for register machines, hence, we cannot obtain computational completeness. In the future, the new variant of partial halting should also be investigated for other variants of P systems working in the different derivation modes, with multisets of objects, but also with strings, arrays, etc. Acknowledgements. Artiom Alhazov gratefully acknowledges support by the Academy of Finland, project 203667; he also acknowledges the project 06.411.03.04P from the Supreme Council for Science and Technological Development of the Academy of Sciences of Moldova. The work of Marion Oswald was supported by FWF-project T225-N04. 2006. References 1. A. Alhazov: On determinism of evolution-communication P systems, Journal of Universal Computer Science 10, 5, 2004, 502–508. 2. A. Alhazov, Number of protons/bi-stable catalysts and membranes in P systems. Time-freeness. In: [15], 79–95. 3. A. Alhazov: Communication in Membrane Systems with Symbol Objects, Ph.D. Thesis, Tarragona, Spain, 2006. 4. F. Bernardini, V. Manca: P systems with boundary rules. In: [21], 107–118. 5. F. Bernardini, F. J. Romero-Campero, M. Gheorghe, M.J. P´erez-Jim´enez, M. Margenstern, S. Verlan, N. Krasnogor: On P systems with bounded parallelism. In: G. Ciobanu, Gh. P˘aun (Eds.): Pre-Proc. of First International Workshop on Theory and Application of P Systems, Timisoara, Romania, September 26–27, 2005, 31–36. 6. M. Cavaliere: Evolution-communication P systems. In: [21], 134–145. 7. G. Ciobanu, Linqiang Pan, Gh. P˘aun, M.J. P´erez-Jim´enez: P systems with minimal parallelism, accepted for TCS. 8. J. Dassow, Gh. P˘aun: Regulated Rewriting in Formal Language Theory, SpringerVerlag, Berlin, 1989. 9. J. Dassow, Gh. P˘aun: On the power of membrane computing, Journal of Universal Computer Science 5(2) (1999), 33–49. 10. R. Freund, M. Oswald: GP Systems with Forbidding Context. Fundamenta Informaticae 49, 1–3 (2002), 81–102. 11. R. Freund, M. Oswald: P Systems with activated/prohibited membrane channels. In: [21], 261–268. 12. R. Freund, M. Oswald: P systems with conditional communication rules assigned to membranes, Journal of Automata, Languages and Combinatorics 9, 4 (2004), 387– 397. 20 A. Alhazov, R. Freund, M. Oswald, S. Verlan 13. R. Freund, M. Oswald: P systems with partial halting, submitted, 2007. 14. R. Freund, Gh. P˘aun: From Regulated Rewriting to Computing with Membranes: Collapsing Hierarchies. Theoretical Computer Science 312 (2004), 143–188. 15. R. Freund, Gh. P˘aun, G. Rozenberg, A. Salomaa (Eds.): Membrane Computing. 6th International Workshop WMC 2005, Vienna, Austria, Lecture Notes in Computer Science 3850, Springer-Verlag, 2006. 16. R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez: Tissue-like P systems with channel states. Theoretical Computer Science 330 (2005), 101–116. 17. M.L. Minsky: Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey, USA, 1967. 18. A. P˘aun, Gh. P˘aun: The power of communication: P systems with symport/ antiport, New Generation Computing 20, 3 (2002), 295–306. 19. Gh. P˘aun: Computing with membranes, J. of Computer and System Sciences 61, 1 (2000), 108–143, and TUCS Research Report 208 (1998) (http://www.tucs.fi). 20. Gh. P˘aun: Computing with Membranes: An Introduction, Springer-Verlag, Berlin, 2002. 21. Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron (Eds.): Membrane Computing. International Workshop WMC 2002, Curte˘a de Arge¸s, Romania, Revised Papers. Lecture Notes in Computer Science 2597, Springer-Verlag, Berlin (2003). 22. Y. Rogozhin, A. Alhazov, R. Freund: Computational power of symport/antiport: history, advances, and open problems. In: [15], 1–30. 23. G. Rozenberg, A. Salomaa (Eds.): Handbook of Formal Languages (3 volumes), Springer-Verlag, Berlin, 1997. 24. S. Verlan, F. Bernardini, M. Gheorghe, M. Margenstern: On communication in tissue P systems: conditional uniport. Pre-proceedings of Membrane Computing. International Workshop, WMC7, Leiden, The Netherlands, 2006, 507–521 25. The P Systems Web Page: http://psystems.disco.unimib.it.