Polarizationless P Systems with One Active Membrane

Polarizationless P Systems with One Active Membrane Artiom Alhazov1, Rudolf Freund2 1Institute of Mathematics and Computer Science, Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova E-mail: [email protected] 2Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria E-mail: [email protected] Summary. The aim of this paper is to study the computational power of P systems with one active membrane without polarizations. For P systems with active membranes, it is known that computational completeness can be obtained with either of the following combinations of features: 1)two polarizations, 2)membrane creation and dissolution, 3)four membranes with three labels, membrane division and dissolution, 4)seven membranes with two labels, membrane division and dissolution. Clearly, with one membrane only object evolution rules and send-out rules are permitted. Two variants are considered: external output and internal output. 1 Introduction Membrane computing is a theoretical framework of parallel distributed multiset processing. It has been introduced by Gheorghe P˘aun in 1998, and has been an active research area since then, see [10] for the comprehensive bibliography and [6],[8] for a systematic survey. Membrane systems are also called P systems. It has been shown in [4] (some results being improvements of the results from [1] and [3]) that the following P systems with active membranes are computationally complete: 1) with one membrane and two polarizations, as acceptors, 2) polarizationless ones with membrane creation and dissolution, 3) polarizationless ones starting with four membranes and three labels, 4) polarizationless ones starting with seven membranes and two labels. The object of study of this paper is the family of P systems with one active membrane without polarizations. Similar questions for non-cooperative transitional P systems without any additional features have been addressed in [2]. 10 A. Alhazov, R. Freund 2 Definitions 2.1 Formal Language Preliminaries Consider a finite set V. The set of all words over Vis denoted by V∗, the concatenation operation is denoted by •(which is written only when necessary) and the empty word is denoted by λ. Any set L⊆V∗is called a language. For a word w∈V∗and a symbol a∈V, the number of occurrences of ain wis written as |w|a. The permutations of a word w∈V∗are Perm(w) = {x∈V∗| |x|a=|w|afor all a ∈V}. We denote the set of all permutations of the words in Lby Perm(L), and we extend this notation to families of languages. We use F IN,REG,LIN,CF ,MAT ,CS,RE to denote finite, regular, linear, context-free, matrix without appearance checking and with erasing rules, context-sensitive, and recursively enumerable families of languages, respectively. The family of languages generated by extended (tabled) interactionless L systems is denoted by E(T)0L. The family of sets of numbers generated by forbidden random context multiset grammars is denoted by NfRC. For more formal language preliminaries, we refer the reader to [9]. Throughout this paper we use string notation to denote the multisets. When speaking about membrane systems, keep in mind that the order in which symbols are written is irrelevant, unless we speak about the symbols sent to the environment. In particular, speaking about the contents of some membrane, when we write an1 1· · · anm m(or any permutation of it), we mean a multiset consisting of niinstances of symbol ai, 1 ≤i≤m. 2.2 P systems with One (Active) Membrane We present the definition of a P system with active membranes, simplified for studying the generative power in case of one membrane. Π= (O, µ = [ ]1, w1, R1, i0),where Ois a finite set of objects, w1is the initial multiset in region 1, R1is the set of rules associated to membrane 1, i0is the output region; when languages are considered, i0= 0 is assumed. The rules of a membrane system have the forms (a0) [ a→u]1(evolution of an object), and (c0) [ a]1→[ ]1b(sending an object out, possibly renaming it), where a, b ∈Oand u∈O∗. The rules are applied in maximally parallel way: no further rule should be applicable to the idle objects, except rules of type (c0) may be applied to at most one object at any step. Acatalytic P system (with one membrane) is a construct Π= (O, C, µ = [ ]1, w1, R1, i0),where Ois a finite set of objects, Cis a special subset of Owhose elements are called catalysts, w1is the initial multiset in region 1, R1is the set of rules associated to membrane 1, i0is the output region; when languages are considered, i0= 0 is assumed. Polarizationless P Systems with One Active Membrane 11 The rules in Rare either non-cooperative rules of the form a→(b1, tar1)· · · (bk, tark) with aand the bi, 1 ≤i≤k, being from O\Cand the tari∈ {here, out}being the targets for the corresponding symbols bi, or catalytic rules of the form ca → c(b1, tar1)· · · (bk, tark) with c∈C. A configuration of a P system is a construct which contains the information about the contents of the skin membrane as well as the sequence of objects sent out. A sequence of transitions between the configurations is called a computation. The computation halts when such a configuration is reached that no rules are applicable. In case of external output (i0= 0), as the result of a (halting) computation we may consider the sequence of objects sent to the environment; we denote it by L(Π). Both in case of internal output (i0= 1) and in case of external output, we may consider as the result the vector of multiplicities of objects in region i0, we denote it by P s(Π), or the total number of objects in region i0, which we denote by N(Π). The family of P systems with one polarizationless active membrane may be denoted by OP1(a0, c0). The class of sets of numbers/vectors/words generated by a family Fof P system is denoted by NF,P sFand LF, respectively. We use a superscript int or ext when speaking about internal and external output, respectively, and we may omit subscript ext in the case of generating languages, i.e., external output is assumed for LF. Moreover, we may use a subscript Tto denote terminal filtering of the result; in this case, a subset T⊂Ois additionally specified for Π, and the objects not belonging to Tare not considered in the result. For example, the family of sets of vectors of non-negative integers generated internally by P systems with one polarizationless active membrane with terminal filtering are denoted by P sint TOP1(a0, c0). Example 1. To illustrate generation, consider the following P system: Π= (O={S, a, b, c, d, f}, µ = [ ]1, w1=a, R1, i0), R1={[S→Sabcd ]1,[S→f]1, [a]1→[ ]1a, [b]1→[ ]1b, [c]1→[ ]1c}. Object Sproduces objects a,b,c,din arbitrary but equal amounts. Objects a,b,care sent out in arbitrary order. Hence, if i0= 1 then N(Π) = N1(i.e., the set of all positive integers), and if i0= 0 then L(Π) = Sn≥0Perm(anbncn) = {w∈ {a, b, c}∗| |w|a= |w|b=|w|c}. P systems can be also viewed as acceptors. In that case, an input subalphabet Σis additionally specified in the tuple defining P system before µ, and i0= 1 is the input region. An input multiset over Σis additionally placed inside the membrane before the computation starts, and it is accepted if and only if the computation halts. The result P sacc(Π) is the set of all accepted inputs, and the family of vector sets accepted by P systems with one active membrane is P saccOP1(a0, c0). 3 Comparison with a Transitional Model: Catalytic P Systems with One Catalyst The model of P systems with active membranes, for the case of one membrane, can be compared to the following case of transitional P systems: non-distributed P systems 12 A. Alhazov, R. Freund with one catalyst. Indeed, for each P system with one active membrane, there exists a 1-catalytic non-distributed P system with the same behavior, as non-cooperative rules work equivalently in both models: [ A→u]his equivalent to A→u, and sending out corresponds to particular rules with one catalyst, i.e., [ A]h→[ ]hacorresponds with cA →c(a, out), or, if without restricting generality we assume the set of symbols that may appear inside the system to be disjoint from the set of symbols that may be sent to the environment, simply with cA →c(a, here). Notice that for P system with external output, we may ignore the objects remaining inside the system when it halts (as explained in the next section), while for P systems with internal output, we should ignore the objects sent out. In this way, for the case of internal output, sending out corresponds to a catalytic erasing, while for the case of external output sending out corresponds to a catalytic renaming of a non-terminal symbol into a terminal symbol. Hence, we can immediately conclude that Xα βOP1(a0, c0)⊆XβOP1(ncoo, cat1) for X∈ {N, P s, L}, α ∈ {int, ext}, β ∈ {−, T }, where β=−stands for not specifying a subscript. One-catalytic P systems were investigated in [5], where some subclasses of P systems with one catalyst are defined and certain results on their generative power are presented. In particular, it was shown in [5] that N−cOP1(wsepcat1) = NREG and N−cOP1(complcat1)⊆NfRC. Clearly, the corresponding restrictions might also be considered for polarizationless P systems with one active membrane, and such results can be claimed as upper bounds for the corresponding restrictions, e.g., NOP1(wsep(a0, c0)) = NREG, where the restriction of the weak separation can be reformulated for the model with active membranes as follows: the set Oof objects is divided into three disjoint subsets O0,O00 and O000, such that •objects a∈O0have no associated rules (they cannot evolve or be sent out, so if they are produced, they remain idle inside the system), •objects a∈O00 have associated send-out rules, but no evolution rules, •objects a∈O000 have associated evolution rules, but no send-out rules. It is worth mentioning that the additional requirement from [5] that the objects produced by a catalytic rule cannot undergo a non-cooperative rule is automatically satisfied after translation into the active membrane case, so the only restriction remaining in the case of weak separation is that a rule of type (a0) and a rule of type (c0) are not allowed to compete for the same object. This restriction means, for instance, that all objects that have associated send-out rules cannot evolve inside the system, they simply wait there until they are chosen to be sent out. A different restriction considered in [5] is complete P systems (mentioned above as complcat1). It can be reformulated in the model of polarizationless P systems with active membranes as follows: there is no object having associated rules of type (c0) and no rules of type (a0). This restriction means that no object is allowed to be temporarily idle; if it is not sent out, then it either evolves immediately, or remains idle throughout the computation. It follows that NREG ⊆NOP1(compl(a0, c0)) ⊆NfRC. Polarizationless P Systems with One Active Membrane 13 It is interesting to note that weak separation and completeness are, in some sense, two opposite requirements. While the latter one requires that all objects which can be sent out must evolve if they are not chosen to be sent out, the first special case requires that no objects which can be sent out are allowed to evolve. Of course, in the most general case there can be both kinds of objects which can be sent out. 4 External output The first goal of this section is to present a reduction of any P system with one active membrane without polarizations and external output to an equivalent normal form. Then we will use this normal form to prove an upper bound result. We require the normal form mentioned above to satisfy the following conditions: •Every object appears on the left side of some rule. •The only erasing rule allowed is for the initial object; if so, the initial object does not appear on the right side of any rule. (If we have an initial multiset w, then we add the rule S→wwhere Sis a new symbol now being the initial object.) We approach this goal in a few stages. First, we remark that, without restricting generality, we may assume that no objects may remain inside the system when it halts. Indeed, let Oλbe the set of all objects that do not have associated rules. By adding rules Rλ={[a→λ]1|a∈Oλ}, we make sure that there are no objects that do not have associated rules. On the other side, adding rules Rλdoes not affect the result of a P system with external output, since preserving/erasing objects from Oλhas no alternatives, and it does not affect the environment. Second, we remark that, without restricting generality, we may assume that the initial multiset consists of only one object, say S, which does not appear in the right side of any rule. Indeed, for a P system starting with a multiset (represented by) w, consider an equivalent P system starting with a multiset consisting of a new object S, and adding RS={[S→w]1}to R1. Third, we claim that for any P system satisfying the assumptions mentioned above, there exists a P system without erasing rules (except, possibly, for S). Proof. Indeed, let us first add rules Rt={[a→# ]1|([ a→λ]1)∈R1or a= #}, where # is a new symbol, shared for all such reductions, so if it appears in a configuration, the system will never halt, and will therefore not produce any result. This transformation will certainly not affect the result of the system, since every new computation branch will not be productive, while the existing branches will not be affected (since by construction, one can always apply some other rule to ainstead of trapping). Second, compute the set Oλof erasable objects as follows: •Set Oλto {a∈O|[a→λ]1∈R1, •If [ a→u]1is in R1and u∈O∗ λ, then add ato Oλ, •Iterate the previous procedure until no more elements can be added to Oλ. Third, replace each rule [ a→u]1by rules [ a→u0]1, where the u0are obtained from uby removing (in all possible combinations) some objects from Oλ. This will again yield an equivalent system, because every symbol that could eventually be deleted does not have to be produced in the first place. 14 A. Alhazov, R. Freund Fourth, remove all erasing rules. We claim that the resulting P system is still equivalent to the original P system. Indeed, any object (other than S) that should be erased, could be “pre-erased” by not producing it in the first place. However, any object that should evolve can evolve by other rules, and any object that should be sent out can be sent out (unless some competing object is sent out, in which case the simulation would not be correct, so the computation is discarded by producing symbol #).  Corollary 1. LOP1(a0, c0)⊆CS. Proof. Indeed, the total number of objects (inside and outside the membrane) never decreases throughout the computation (except, possibly, for the empty word, generated in one step), and the length of the result matches the total number of objects when the system halts.  We now proceed with the lower bound result. Theorem 1. LOP1(a0, c0)⊇REG •Perm(REG). Proof. Consider an alphabet Tand two arbitrary regular languages over T. Then there exist reduced regular grammars G1= (N1, T, P1, S1) and G2= (N2, T, P2, S2) generating them, such as N1∩N2=∅. We construct the following P system: Π= (O=N1∪N2∪T∪T0, µ = [ ]1, w1=S1, R1), T0={a0|a∈T}, R1={[A→aB ]1|(A→aB)∈P1} ∪ {[A→S2]1|(A→λ)∈P1} ∪ {[A→a0B]1|(A→aB)∈P2} ∪ {[A→λ]1|(A→λ)∈P2} ∪ {[a0→a0]1|a∈T} ∪ {[a]1→[ ]1a, [a0]1→[ ]1a|a∈T}. The P system constructed above generates L(G1)•L(G2), except the symbols generated by the second grammars are produced in a primed form, and may undergo trivial rewriting for an arbitrarily long time before they are sent out, which ensures that after generating a word from L(G1), any permutation of a word from L(G2) may be generated.  We now present a few closure properties. Lemma 1. The family LOP1(a0, c0)is closed under renaming morphisms. Proof. The statement follows from applying the renaming morphism to the send-out rules.  Theorem 2. LOP1(a0, c0)is closed under union. Proof. The closure under union follows from adding a new axiom and productions of non-deterministic choice between multiple axioms.  Polarizationless P Systems with One Active Membrane 15 5 Internal output In this case the environment is no longer relevant: it does not matter which symbol is written in the right side of a send-out rule. The object sent out no longer affects the result, so sending out is equivalent to a sequential version of erasing. Of course, we can generate P sREG with rules of type (a0) corresponding to the rules of a reduced regular grammar. Hence, P sintOP1(a0, c0)⊇P sREG. Is it an open question whether non-semilinear number sets can be generated, see also the partial results transferred from the one-catalytic model, recalled in Section 3. 6 P systems with input In this section we show that, not very surprisingly, for P systems with one polarizationless active membrane, their accepting power is even smaller than their generative power. More exactly, unless such a P system accepts all allowed inputs, it only accepts specific finite sets. We start by establishing some useful facts (we remind that we use ⊆to denote the submultiset relation, ∪to denote the union of multisets, and \to denote the difference of multisets). Lemma 2. Let Π∈OP1(a0, c0)be a P system with alphabet O, let [u]1⇒[v]1α in Π(α∈O∪ {λ}) Then for every multiset u0⊆u, either [u0]1is already a halting configuration, or there exists a multiset v0⊆vand β∈O∪{λ}such that [u0]1⇒[v0]1β in Π. Proof. In a transition [ u]1⇒[v]1α, one of three possible cases happen for every (copy of) object ain u: •ais rewritten by some rule of Πinto a (possibly empty) multiset, contributing to v; •ais sent out by some rule of Πas α; •aremains idle, contributing to v. Note that vconsists exactly of the resulting objects from the first case and the objects of the third case. More precisely, let the union of multisets of the right side rules for all copies of rewritten objects be vr, and let the multiset of idle objects be vi; then, v=vr∪vi. By definition of the model, the second case was applied to at most one (copy of) an object in u. Also by definition of the model, for each object in the third case, there exist no rules to evolve it, except, possibly, send-out rules, in which case α6=λ. We recall that u0may be obtained from uby erasing some (copies) of objects. Fix some correspondence of (copies of) objects in u0to objects in u, and consider a transition from u0by the same behavior of objects in u0as of objects in u: •rewritten objects will yield some submultiset v0 rof vr; •β0will be produced in the environment, β0=αor β0=λ; •idle objects will yield some submultiset v0 iof vi. 16 A. Alhazov, R. Freund It is obvious that these rules are applicable, and that v0 r∪v0 i⊆v. Maximality also holds, except in one special situation: when α6=λ, but it was produced from a (copy of) an object not in u0, while there exists at least one object bthat was idle in a transition [u]1⇒[v]1α. In this situation, one object b, instead of being idle, should be sent out as β, and the resulting multiset in the skin is v0=v0 r∪v0 i\b(if this situation does not happen, we take β=β0and v0=v0 r∪v0 i). Therefore, [ u0]1⇒[v0]1βin Πif at least one (copy) of object from u0fell into the first or the second case, and otherwise [ u0]1is already a halting configuration.  Lemma 3. If n∈N(Π), then also n0∈N(Π)for any non-negative integer n0≤n. Proof. Let the alphabet of Πbe O, let the initial contents of the skin membrane of Πbe w1, and let the input subalphabet of Πbe Σ. By definition of acceptance, a number n is accepted if there exists a halting computation in Πstarting from configuration [ u]1, for some u∈w1Σn. Consider the “sub-input” of only n0objects, i.e., u0∈w1Σnsuch that u0⊆u. If [u]1is already halting, then so is [ u0]1, so the statement of the lemma holds; now we assume the contrary: [ u]1⇒[v]1α. By the previous lemma, in one step, either the computation with u0in the skin will immediately halt (and the statement of the lemma again holds), or there is a one-step transition [ u0]1⇒[v0]1βwith v0⊆v. Iterating the application of the previous lemma, by induction, we conclude that there exists a computation starting from [ u0]1that will halt in at most as many step as the halting computation starting from [ u]1that we considered. Hence n0∈N(Π).  It follows that the accepted set of numbers is either N, or empty, or it contains all integers less than or equal to the maximal accepted number, so accepting P systems with one polarizationless active membrane cannot be computationally complete, and P systems with one polarizationless active membrane are obviously weaker as acceptors than as generators: NaccOP1(a0, c0)⊆ {∅,N} ∪ {{k|0≤k≤n} | n∈N}. In the rest of the section we show, by all necessary examples, that this inclusion is an equality: Π∅= (O={a}, Σ ={a}, µ = [ ]1, w1=a, R1={[a→a]1}, i0= 1). ΠN= (O={a}, Σ ={a}, µ = [ ]1, w1=λ, R1={[a→λ]1}, i0= 1). Πn= (O={ai|0≤i≤n}, Σ ={a0}, µ = [ ]1, w1=λ, R1, i0= 1),where R1={[ai→ai+1 ]1,[ai]1→[ ]1a0|0≤i < n} ∪ {[an→an]1}. Clearly, Π∅accepts nothing, since with any input it starts with at least one object, and carries out an infinite computation. On the other end of the spectrum, system ΠNaccepts any input, by erasing it in one step and halting. Finally, we claim that system Πnaccepts exactly set {k|0≤k≤n}. Indeed, any object increments its index every step, unless the object is sent out, or the index reaches n(forcing an infinite computation). It is easy to see that at most ninput objects may be sent out in this way; the system with input (a0)khas a halting computation if and only if k≤n. Polarizationless P Systems with One Active Membrane 17 Overall, we have established the following results: REG •Perm(REG)⊆LOP1(a0, c0)⊆CS, P sintOP1(a0, c0)⊆P sREG, NαOP1(wsep(a0, c0)) = NREG, α ∈ {int, ext}, NREG ⊆NαOP1(compl(a0, c0)) ⊆NfRC, α ∈ {int, ext}, NaccOP1(a0, c0) = {{k|0≤k≤n} | n∈N} ∪ {∅,N}. 7 Conclusions In this paper we have considered the family of languages generated by polarizationless P systems with one active membrane. A normal form was given for external output case. It was than shown that the family of generated languages lies between REG •Perm(REG) and CS, and is closed under union and renaming morphisms. The exact characterization is an open question, but polarizationless P systems with one active membrane can be simulated by (and are, therefore, at most as powerful as) P systems with one catalyst, transferring two results on the generative power of two restricted classes, independently from the output region. Then we also considered sets of vectors or numbers generated internally, as well as sets of vectors or numbers accepted by polarizationless P systems with one active membrane. Several questions about the families of these sets are still open, too. Another possible generalization that can be considered is to also allow rules of type (b0) to bring objects from the environment back to the skin. Note that such systems would still correspond to a subclass of 1-catalytic P systems, but some definitions would have to be revised, as well as all related results. We have proved that accepting P systems with one polarizationless active membrane are not computationally complete, unlike those with two polarizations or like those with membrane creation and dissolution, or with multiple membranes and membrane dissolution. The questions about the computational power of polarizationless P systems with active membranes with 2 and 3 membranes in the initial configuration are still open, as well as of polarizationless systems with less than 7 membranes and two labels, or of all polarizationless systems with only one label. References 1. A. Alhazov: P Systems without Multiplicities of Symbol-Objects. Information Processing Letters 100, 3, 2006, 124–129. 2. A. Alhazov, C. Ciubotaru, Yu. Rogozhin, S. Ivanov: The Family of Languages Generated by Non-Cooperative Membrane Systems. In: Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, G. Rozenberg, A. Salomaa: Membrane Computing, 11th International Conference, CMC11, Jena, Revised Selected Papers, Lecture Notes in Computer Science 6501, 2011, 65–79.