Constant-Space P Systems with Active Membranes

Constant-Space P Systems with Active Membranes Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy {leporati,luca.manzoni,mauri,porreca,zandron}@disco.unimib.it Summary. We continue the investigation of the computational power of spaceconstrained P systems. We show that only a constant amount of space is needed in order to simulate a polynomial-space bounded Turing machine. Due to this result, we propose an alternative definition of space complexity for P systems, where the amount of information contained in individual objects and membrane labels is also taken into account. Finally, we prove that, when less than a logarithmic number of membrane labels is available, moving the input objects around the membrane structure without rewriting them is not enough to even distinguish inputs of the same length. 1 Introduction This paper continues the recent investigations of the computational power of P systems with active membranes by looking at the problems that they are able to solve while working in constant space. It is already known that a super-polynomial amount of space is needed to solve problems outside PSPACE [6]. Recently [2], it has been shown that logarithmic space suffices to simulate a polynomial spacebounded Turing machine (TM). Here we show that the constant space is sufficient and, trivially, necessary to solve all problems in PSPACE. This result challenges our intuition about space. How can we even be able to remember, for example, the position of the TM head when we have less than a logarithmic number of bits of information? We discuss the implication of this result and how the current definition of space in P systems can be changed in order to better represent out intuition about “space”. With the new definition all the known results involving polynomial (or larger) amount of space, according to the old definition, still hold. Only in the case of P systems with severely tight bounds on space the new definition makes a difference. Finally, we show a result highlighting the importance of membranes for P systems. In fact, when only movement rules, i.e., send-in, send-out, and dissolution 244 A. Leporati et al. without rewriting, are allowed on the input symbols and less than a logarithmic number of membrane labels are present, there is no possibility of correctly determining even if two inputs are distinct, unless the ordering of the symbols is discarded. The paper is organised as follows. The basic notions necessary for the rest of the paper are presented in Section 2. The main result, that is, the simulation of a polynomial space-bounded TM, is described in Section 3. The current definition of space in P systems is discussed and an alternative definition is proposed in Section 4. In Section 5 we examine the limitations arising when only movement but no rewriting is possible for the input symbols. Finally, in Section 6 we present a brief summary of the results and some possible future research directions. 2 Basic Notions We recall the basic definitions related to P systems with active membranes with input alphabet [7]. Definition 1. AP system with (elementary) active membranes of initial degree d≥1is a tuple Π= (Γ, ∆, Λ, µ, wh1, . . . , whd, R), where: •Γis an alphabet, i.e., a finite non-empty set of symbols, usually called objects; •∆is another alphabet, disjoint from Γ, called the input alphabet; •Λis a finite set of labels for the membranes; •µis a membrane structure (i.e., a rooted unordered tree, usually represented by nested brackets) consisting of dmembranes labelled by elements of Λin a one-to-one way; •wh1, . . . , whd, with h1, . . . , hd∈Λ, are strings over Γ, describing the initial multisets of objects placed in the dregions of µ; •Ris a finite set of rules over Γ∪∆. Each membrane possesses, besides its label and position in µ, another attribute called electrical charge, which can be either neutral (0), positive (+) or negative (−) and is always neutral before the beginning of the computation. A description of the available kinds of rule follows. This description differs from the original definition [4] only in that new input objects may not be created during the computation. •Object evolution rules, of the form [a→w]α h They can be applied inside a membrane labelled by h, having charge αand containing an occurrence of the object a; the object ais rewritten into the multiset w(i.e., ais removed from the multiset in hand replaced by the objects in w). At most one input object b∈∆may appear in w, and only if it also appears on the left-hand side of the rule (i.e., if b=a). Constant-Space P Systems with Active Membranes 245 •Send-in communication rules, of the form a[ ]α h→[b]β h They can be applied to a membrane labelled by h, having charge αand such that the external region contains an occurrence of the object a; the object ais sent into hbecoming band, simultaneously, the charge of his changed to β. If b∈∆then a=bmust hold. •Send-out communication rules, of the form [a]α h→[ ]β hb They can be applied to a membrane labelled by h, having charge αand containing an occurrence of the object a; the object ais sent out from hto the outside region becoming band, simultaneously, the charge of his changed to β. If b∈∆then a=bmust hold. •Dissolution rules, of the form [a]α h→b They can be applied to a membrane labelled by h, having charge αand containing an occurrence of the object a; the membrane his dissolved and its contents are left in the surrounding region unaltered, except that an occurrence of a becomes b. If b∈∆then a=bmust hold. •Elementary division rules, of the form [a]α h→[b]β h[c]γ h They can be applied to a membrane labelled by h, having charge α, containing an occurrence of the object abut having no other membrane inside (an elementary membrane); the membrane is divided into two membranes having label hand charges βand γ; the object ais replaced, respectively, by band c while the other objects in the initial multiset are copied to both membranes. If b∈∆(resp., c∈∆) then a=band c /∈∆(resp., a=cand b /∈∆) must hold. Each instantaneous configuration of a P system with active membranes is described by the current membrane structure, including the electrical charges, together with the multisets located in the corresponding regions. A computation step changes the current configuration according to the following set of principles: •Each object and membrane can be subject to at most one rule per step, except for object evolution rules (inside each membrane several evolution rules can be applied simultaneously). •The application of rules is maximally parallel: each object appearing on the left-hand side of evolution, communication, dissolution or elementary division rules must be subject to exactly one of them (unless the current charge of the membrane prohibits it). The same principle applies to each membrane that can be involved to communication, dissolution, or elementary division rules. In other words, the only objects and membranes that do not evolve are those associated with no rule, or only to rules that are not applicable due to the electrical charges. •When several conflicting rules can be applied at the same time, a nondeterministic choice is performed; this implies that, in general, multiple possible configurations can be reached after a computation step. •In each computation step, all the chosen rules are applied simultaneously (in an atomic way). However, in order to clarify the operational semantics, each computation step is conventionally described as a sequence of micro-steps as follows. 246 A. Leporati et al. First, all evolution rules are applied inside the elementary membranes, followed by all communication, dissolution and division rules involving the membranes themselves; this process is then repeated to the membranes containing them, and so on towards the root (outermost membrane). In other words, the membranes evolve only after their internal configuration has been updated. For instance, before a membrane division occurs, all chosen object evolution rules must be applied inside it; this way, the objects that are duplicated during the division are already the final ones. •The outermost membrane cannot be divided or dissolved, and any object sent out from it cannot re-enter the system again. Ahalting computation of the P system Πis a finite sequence of configurations C= (C0, . . . , Ck), where C0is the initial configuration, every Ci+1 is reachable from Civia a single computation step, and no rules of Πare applicable in Ck. A non-halting computation C= (Ci:i∈N) consists of infinitely many configurations, again starting from the initial one and generated by successive computation steps, where the applicable rules are never exhausted. P systems can be used as language recognisers by employing two distinguished objects yes and no; exactly one of these must be sent out from the outermost membrane in the last step of each computation, in order to signal acceptance or rejection, respectively; we also assume that all computations are halting. If all computations starting from the same initial configuration are accepting, or all are rejecting, the P system is said to be confluent. If this is not necessarily the case, then we have a non-confluent P system, and the overall result is established as for nondeterministic Turing machines: it is acceptance iff an accepting computation exists. Unless otherwise specified, the P systems in this paper are to be considered confluent. In order to solve decision problems (i.e., decide languages), we use families of recogniser P systems Π={Πx:x∈Σ⋆}. Each input xis associated with a P system Πxthat decides the membership of xin the language L⊆Σ⋆by accepting or rejecting. The mapping x7→ Πxmust be efficiently computable for each input length [3]. Definition 2. Let E,Fbe classes of functions over strings. A family of P systems Π={Πx:x∈Σ⋆}is said to be (E,F)-uniform if the mapping x7→ Πxcan be described by two functions F∈ F (for “family”) and E∈ E (for “encoding”) as follows: •F(1n) = Πn, where nis the length of the input xand Πnis a common P system for all inputs of length nwith a distinguished input membrane. •E(x) = wx, where wxis a multiset encoding the specific input x. •Finally, Πxis simply Πnwith wxadded to the multiset placed inside its input membrane. In particular, a family Πis said to be (L,L)-uniform if the functions Eand F can be computed by a deterministic Turing machine in logarithmic space. Constant-Space P Systems with Active Membranes 247 Any explicit encoding of Πxis allowed as output of the construction, as long as the number of membranes and objects represented by it does not exceed the length of the whole description, and the rules are listed one by one. This restriction is enforced in order to mimic a (hypothetical) realistic process of construction of the P systems, where membranes and objects are presumably placed in a constant amount during each construction step, and require actual physical space proportional to their number; see also [3] for further details on the encoding of P systems. Finally, we describe how space complexity for families of recogniser P systems is measured, and the related complexity classes [5, 7]. Definition 3. Let Cbe a configuration of a P system Π. The size |C| of Cis defined as the sum of the number of membranes in the current membrane structure and the total number of objects from Γ(i.e, the non-input objects) they contain. If C= (C0, . . . , Ck)is a computation of Π, then the space required by Cis defined as |C| = max{|C0|, . . . , |Ck|} The space required by Πitself is then |Π|= sup{|C| :Cis a computation of Π}. Finally, let Π={Πx:x∈Σ⋆}be a family of recogniser P systems, and let s:N→ N. We say that Πoperates within space bound siff |Πx| ≤ s(|x|)for each x∈Σ⋆. Definition 4. We denote by (L,L)-MCSPACEAM(f(n)) the class of languages decidable by (L,L)-uniform families of confluent P systems with active membranes within space bound f. In particular, (L,L)-MCSPACEAM(O(1)) denotes the class of languages decidable in constant space. 3 Simulating Polynomial-Space Turing Machines The idea behind the simulation of a polynomial-space bounded TM using only constant space in the P system is to use the input objects as a way to store the status of the TM tape. Since by rewriting more than a constant number of input symbols the amount of space would be non-constant, the only way to use them to store the state of the TM tape is to track the position of the symbols inside the membranes. We will use a tape alphabet consisting of two symbols, aand b; the construction presented here immediately generalises to alphabets of any size. The simulation relies on two main ideas in order to store and retrieve the content of the simulated TM tape. The first idea is that, apart from a short initialisation procedure, the only relevant part of an input object σjis its subscript, that is, the position jin the TM tape. We will then have two membranes, named aand b, in which the input objects will be distributed. The interpretation of the fact that an object σjis in membrane ais that the j-th cell of the TM contains 248 A. Leporati et al. the symbol a. Notice that σ=ais not required, since this information is not used after the initial phase of the simulation. The second idea is that it is possible to “read” a subscript of an input object σjwithout rewriting it and by using only a constant number of additional objects and membranes. An input object σjcan use an evolution rule to generate a timer that, after jtime steps, changes the charge of a membrane. Any other object that was observing that same membrane, i.e., it was counting together with the timer, is able to obtain the value jof the subscript of σj. The two ideas intuitively presented here, to be formalised in the construction below, allow us to store and retrieve the content of the tape of a TM using only a constant number of additional objects and membranes by “moving around” the input objects. The simulation is divided into three phases. The first one is the initialisation, in which the input objects are distributed across the membranes of the systems. The second phase is simulation of a step of the TM, which requires the third phase, where the P system is reset in order to simulate the next step. 3.1 Membrane structure The membrane structure consists of six membranes: 0 T 0 I 0 R 0 a 0 b 0 e Each of these membranes has a specific semantics: •Tis a “temporary storage”. It will contain objects that are not needed in that particular stage of the computation, and, then it will be emptied and the object contained will be moved to one of the other membranes. It also serves as the input membrane. •Iis used only during the initialisation, acting as a container for the “dispatching machinery” that moves an input object to the correct membrane. •Ris a membrane used to check the subscript of a specific input symbol. The input object σjgenerates a timer that changes the charge of the membrane after jtime steps. •Membrane a(resp. b) contains all input objects σjsuch that, in the currently simulated step of the TM, the j-th cell of the tape contains the symbol a(resp. b). •eis the external membrane, containing all the others. If the tape alphabet contains more than two symbols, it is possible to add more membranes inside e, one for each symbol. Constant-Space P Systems with Active Membranes 249 3.2 Initialisation The initial configuration of the P system contains all the input objects in membrane Tand one auxiliary object move in membrane e. The initialisation procedure moves each input object aj(resp., bj) to membrane a(resp., b) and generates an object q0,a, where qis the initial state of the TM, 0 indicates the position of the TM on the tape, and aindicates the fact that the P system simulating the TM will check if the symbol on the TM tape at position 0 is a. An example of the movement of one object to the correct membrane is shown in Fig. 1. In the description of the simulation we assume that nis the size of the input and p(n) is the length of the tape of the TM, which is polynomial in n. The following set of rules uses the object move to transport an input object outside of membrane Tor, if the membrane is empty, to start the simulation of the first step of the TM. move [ ]0 T→[move]− T [move →move′]− T [move′]0 T→[ ]0 Topen [ai]− T→[ ]0 Tai0≤i < p(n) [bi]− T→[ ]0 Tbi0≤i < p(n) [move′]− T→[ ]0 Tq0,a The next set of rules is used to move an input object from membrane eto I: open [ ]0 I→[open]+ I [open]0 I→[ ]− Iwait ai[ ]+ I→[ai]0 I0≤i < p(n) bi[ ]+ I→[bi]0 I0≤i < p(n) The following rules move an input object ai(resp., bi) to membrane a(resp., b): [ai→aigotoa]0 I0≤i < p(n) (1) [bi→aigotob]0 I0≤i < p(n) (2) [gotoa]0 I→[ ]− Igotoa [gotob]0 I→[ ]− Igotob [ai]− I→[ ]0 Iai0≤i < p(n) [bi]− I→[ ]0 Ibi0≤i < p(n) gotoa[ ]0 a→[gotoa]+ a gotob[ ]0 b→[gotob]+ b [gotoa→ϵ]+ a 250 A. Leporati et al. a0b1b2 a3 0 T 0 I 0 R move 0 a 0 b 0 e a0b1b2 a3move − T 0 I 0 R 0 a 0 b 0 e a0b2 a3move′ 0 T 0 I 0 R b1 0 a 0 b 0 e a0b2 a3 0 T 0 I 0 R b1open 0 a 0 b 0 e a0b2 a3 0 T open + I 0 R b1 0 a 0 b 0 e a0b2 a3 0 T open b1 0 I 0 R 0 a 0 b 0 e a0b2 a3 0 T gotob b1 − I 0 R wait 0 a 0 b 0 e a0b2 a3 0 T gotob 0 I 0 R wait′b1 0 a 0 b 0 e a0b2 a3 0 T 0 I 0 R wait′′ b1gotob 0 a + b 0 e a0b2 a3 0 T 0 I 0 R wait′′′ b1 0 a gotob + b 0 e a0b2 a3 0 T 0 I 0 R move 0 a b1 0 b 0 e Fig. 1. The movement of an input symbol to the correct membrane during the initialisation phase. Constant-Space P Systems with Active Membranes 251 [gotob→ϵ]+ b ai[ ]+ a→[ai]0 a0≤i < p(n) bi[ ]+ b→[bi]0 b0≤i < p(n) (3) Finally, the auxiliary object in membrane ehas to wait for three steps before moving another input object outside of membrane T: [wait →wait′]0 e [wait′→wait′′]0 e [wait′′ →wait′′′]0 e [wait′′′ →move]0 e After the initialisation phase, all the input objects of the form ai(resp., bi) are located in membrane a(resp., b), and the actual simulation of the TM can start. 3.3 Simulation of a Step of the Turing Machine To simulate a step of the TM we first define how its configuration is encoded as a configuration of the P system. Let c0, c1, . . . , cp(n)−1, with ci∈ {a, b}, be the tape of the TM at the current time step, and σ0, . . . , σn−1the initial content of the tape. Then the P system contains, in membrane a, all σjsuch that cj=a and, in membrane b, all the input objects σjsuch that cj=b. Notice that this allows a complete reconstruction of the tape of the TM. The state qof the TM and the position iof the head are encoded in an object qi,τ in membrane e, where τ∈ {a, b}indicates that the P system will check if the symbol in position iof the tape is τ. The simulation proceeds as follows: •The object qi,τ moves an object σjfrom membrane τ, i.e., either aor b, to membrane R. •In membrane Rthe object σjproduces a timer that counts from jto 0, while qi,τ counts from ito 0. When the first timer stops, it changes the charge of R, that is immediately changed again by the object σjexiting from R. This makes it possible to determine if i=j. In that case, the symbol on the tape of the TM in position iis actually τ, and it is possible to perform a step of the simulated machine. In the other case, i.e., i=j, the object σjis moved into membrane Tand we return to the previous step. •When membrane τis empty, or the correct input object was found in the previous step, it is necessary to move back the objects from Tto membrane τ. The search for the input object having subscript iwill then proceed in membrane b(when τ=a) or a(when τ=b). We will now detail the rules necessary to formally define the previous algorithm. In order to shorten the notation, in the following description we are going to write only half of the rules, those involving a. The missing half is obtained by swapping aand b. 258 A. Leporati et al. Theorem 2. Let Πbe a family of (E,F)-uniform, possibly non-confluent P systems with active membranes, where Fis unrestricted, and Eis the class of simple encodings. Suppose that the only rules involving input symbols are send-in communication, send-out communication and membrane dissolution, that these rules never rewrite the input symbol, and that the family uses o(log n)membrane labels. Then, there exists n0∈Nsuch that, for each string x=x0· · · xn−1∈Σ⋆ with |x| ≥ n0, there exist i<j<nsuch that xcan be written as u·xi·v·xj·w and x∈L(Π)if and only if u·xj·v·xi·w∈L(Π). Proof. Let Πbe a family of P systems as defined in the statement of the theorem, let F∈ F be its “family” function, and let F(1n) = Πn= (Γ, ∆, Λ, µ, wh1, . . . , whd, R). Assume that the objects in ∆have, in R, only rules of type send-in, send-out, and dissolution not rewriting them. We impose no restriction on rules involving objects in Γ. Let us consider the possible rules applicable to a fixed object a∈∆ and respecting the imposed restrictions: •There are at most 32|Λ|send-in rules of the form a[ ]α h→[a]β h, since it is possible to choose the label of the membrane and the two charges. •Similarly, there are at most 32|Λ|send-out rules of the form [a]α h→[ ]β ha. •The number of dissolution rules of the form [a]α h→ais at most 3|Λ|, since, contrarily to the last two cases, there is no charge on the right-hand side of the rule. Thus, there are 21|Λ|possible rules per input object and 221|Λ|possible sets of rules involving each input object. Since the encoding of the input string is simple, each input object has the form σifor some σ∈A; hence, for each position iin the input multiset there are (221|Λ|)|A|= 221|Λ||A|possible sets of rules. A necessary condition to distinguish two input objects a, b ∈∆is that the set of rules involving bcannot be simply obtained by replacing awith bin the set of rules involving a(i.e., their sets of rules are not isomorphic); otherwise, replacing a with bin the input multiset would not change the result of the computation of Π. In particular, this holds for the first ninput objects x0,0, . . . , xn−1,n−1, obtained by indexing x=x0···xn−1∈Σn. In order to be able to distinguish these ninput objects it is necessary that 221|Λ||Σ|≥n that is, that the sets of rules associated with the first nobjects are pairwise non isomorphic. This means that |Λ| ≥ log n 21|Σ| But |Λ|is o(log n); hence, the inequality does not hold for large enough n. Instead, there exists n0such that, for each n≥n0, there are two indistinguishable positions iand jwith 0 ≤i < j < n: for each x=u·xi·v·xj·w∈Σn, either x and u·xj·v·xi·ware both accepted, or they are both rejected. ⊓⊔ Constant-Space P Systems with Active Membranes 259 6 Final Remarks In this paper we have solved the problem of determining the computational power of P systems working in constant space, by showing that they can simulate polynomial-space bounded Turing machines. The simulation is also efficient, in the sense that it is only polynomially slower than the original machine. The solution of this problem raised some interesting questions about the ability of the current definition of space to capture our intuitions about the size of P systems. We have challenged the existing definition by considering also the number of bits necessary to encode the auxiliary objects and the labels of the membranes. While the new definition does not change any result involving an amount of space polynomial or larger, it changes the current result and, according to the new definition, our simulation requires logarithmic space. Finally, we have shown that rewriting input objects, while not exploited in other simulations [2], is essential when less than a logarithmic number of membrane labels is present. In fact, distinguishing two inputs is not possible when the input objects are only moved around in the membrane structure, even when no restriction on the space are present. In the future we plan to investigate the relationship between the size of the set of objects Γand the set of membrane labels Λ. It would be interesting to understand if we can easily exchange the way the information is distributed between the two sets according to the new definition of space (Definition 5). References 1. Alhazov, A., Leporati, A., Mauri, G., Porreca, A.E., Zandron, C.: Space complexity equivalence of P systems with active membranes and Turing machines. Theoretical Computer Science 529, 69–81 (2014) 2. Leporati, A., Mauri, G., Porreca, A.E., Zandron, C.: A gap in the space hierarchy of P systems with active membranes (2014), submitted 3. Murphy, N., Woods, D.: The computational power of membrane systems under tight uniformity conditions. Natural Computing 10(1), 613–632 (2011) 4. P˘aun, Gh.: P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages and Combinatorics 6(1), 75–90 (2001) 5. Porreca, A.E., Leporati, A., Mauri, G., Zandron, C.: Introducing a space complexity measure for P systems. International Journal of Computers, Communications & Control 4(3), 301–310 (2009) 6. Porreca, A.E., Leporati, A., Mauri, G., Zandron, C.: P systems with active membranes working in polynomial space. International Journal of Foundations of Computer Science 22(1), 65–73 (2011) 7. Porreca, A.E., Leporati, A., Mauri, G., Zandron, C.: Sublinear-space P systems with active membranes. In: Csuhaj-Varj´u, E., Gheorghe, M., Rozenberg, G., Salomaa, A., Vaszil, G. (eds.) Membrane Computing, 13th International Conference, CMC 2012, Lecture Notes in Computer Science, vol. 7762, pp. 342–357. Springer (2013)