P Systems with Active Cells

P Systems with Active Cells David Orellana-Mart´ın Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad of Sevilla [email protected] Summary. P systems with active membranes is a widely studied framework within the field of Membrane Computing since the creation of the discipline. The abstraction of the structure and behavior of living cells is reflected in the tree-like hierarchy and the kinds of rules that can be used in these kinds of systems. Resembling the organization and communication between cells within tissues that form organs, tissue-like P systems were defined as their abstractions, using symport/antiport rules, that is, moving and exchanging elements from one cell to another one. All the cells are located in an environment where there exist an arbitrary number of some elements. Lately, symport/antiport rules have been used in the framework of cell-like membrane systems in order to study their computational power. Interesting results have been reached, since they act similarly to their counterparts in the framework of tissue P systems. Here, the use of the former defined rules (that is, evolution, communication, dissolution and division/separation rules) is considered, but not working with a tree-like structure. Some remarks about choosing good semantics are given. Key words: Membrane Computing, Active cells, Computational Complexity, P versus NP problem. 1 Introduction Membrane Computing is a distributed parallel computing paradigm inspired by the way the living cells process chemical substances, energy and information. The processor units in the basic model are abstractions of biological membranes, selectively permeable barriers which give cells their outer boundaries (plasma membranes) and their inner compartments (organelles). They control the flow of information between cells and the movement of substances into and out of cells and they are also involved in the capture and release of energy. Biological membranes play an active part in the life of the cell. In fact, the passing of a chemical substance 176 D. Orellana-Mart´ın through a biological membrane is often implemented by an interaction between the membrane itself and the protein channels present in it. During this interaction, the chemical substance and the membrane itself can be modified at least locally. P systems with active membranes [7] include rules inspired on the behavior of the proteins inside the cells. Recalling, evolution rules are the abstraction of the mutation of the chemical compounds within singular organelles, communication rules give us the idea of the transport of the proteins through the membranes of the cells, dissolution rules remember the process of apoptosis, which makes the cell to “kill itself” (in this case, we take the inspiration and apply it to membranes). At last, division and separation rules are the rules that can create an exponential workspace in polynomial time. These are inspired by the asexual and sexual cell processes, that give birth to new cells. All of those rules can be successfully applied in the framework of tissue-like P systems. Moreover, it would be a more natural way to describe the functioning of these rules at the cells that in the membranes. As an analogy to P systems with active membranes, we are going to call them P systems with active cells The paper is organized as follows. Next section briefly introduces some preliminaries needed to make the work self-contained. Section 3 will be devoted to present both syntax and semantics of tissue-like P systems with active cells, letting Section 4 dedicated to present some results concerning the computational complexity classes reached by this kind of membrane systems. The paper ends with some open problems and concluding remarks. 2 Preliminaries An alphabet Γis a non-empty set and their elements are called symbols. A string u over Γis an ordered finite sequence of symbols, that is, a mapping from a natural number of n∈Nonto Γ. The number nis called the length of the string uand it is denoted by |u|. The empty string (with length 0) is denoted by λ. The set of all strings over an alphabet Γis denoted by Γ∗. A language over Γis a subset of Γ∗. A multiset over an alphabet Γis an ordered pair (Γ, f) where fis a mapping from Γonto the set of natural numbers N. The support of a multiset m= (Γ, f) is defined as supp(m) = {x∈Γ|f(x)>0}. A multiset is finite (respectively, empty) if its support is a finite (respectively, empty) set. We denote by ∅the empty multiset. We denote by Mf(Γ) the set of all finite multisets over Γ. The cardinal of a finite multiset mis defined as ∑ x∈Γ m(x). Let m1= (Γ, f1), m2= (Γ, f2) be multisets over Γ, then the union of m1and m2, denoted by m1+m2, is the multiset (Γ, g), where g(x) = f1(x) + f2(x) for each x∈Γ. We say that m1is contained in m2and we denote it by m1⊆m2, if f1(x)≤f2(x) for each x∈Γ. The relative complement of m2in m1, denoted by m1\m2, is the multiset (Γ, g), where g(x) = f1(x)−f2(x) if f1(x)≥f2(x), and g(x) = 0 otherwise. P Systems with Active Cells 177 Arooted tree is a connected, acyclic, undirected graph in which one of the vertices (called the root of the tree) is distinguished from the others. Given a node x(different from the root) in a rooted tree, if the last edge on the (unique) path from the root to the node xis {x, y}(so x=y), then yis the parent of node x and xis achild of node y. We denote it by y=p(x) and x∈ch(y). The root is the only node in the tree with no parent. A node with no children is called a leaf (see [2] for details). Let us recall that the pair function ⟨n, m⟩= ((n+m)(n+m+ 1)/2) + nis a polynomial-time computable function which is also a primitive recursive and bijective function from N×Nto N. Adecision problem Xis one whose solution is either “yes” or “no”. This can be formally defined by an ordered pair (IX, θX), where IXis a language over a finite alphabet and θXis a total boolean function over IX. The elements of IXare called instances of the problem X. 2.1 Recognizer membrane systems In this section, a membrane system designates any variant of P system. Recognizer membrane systems were introduced in [4] and they provide a natural framework to solve decision problems by means of devices in Membrane Computing. Definition 1. A membrane system Πis a recognizer membrane system if the following holds: 1. The working alphabet Γof Πhas two distinguished objects yes and no. 2. There exists an (input) alphabet Σstrictly contained in Γ. 3. The initial multisets M1, . . . , Mqof Πare multisets over Γ\Σ. 4. There exists a distinguished membrane called the input membrane. 5. The output region iout is the environment. 6. All computations halt. 7. If Cis a computation of Π, then either object yes or object no (but not both) must have been released into the environment, and only at the last step of the computation. In recognizer membrane systems any computation is either an accepting computation (when object yes is released into the environment at the last step). For each finite multiset mover the input alphabet Σ, the computation of the system Πwith input mstarts from the configuration obtained by adding the input multiset mto the contents of the input membrane, in the initial configuration of Π. Therefore, in this kind of systems we have an initial configuration associated with each input miltiset m(over the input alphabet Σ). We denote Π+mthe membrane system Πwith input multiset m. 178 D. Orellana-Mart´ın 2.2 Polynomial complexity classes of recognizer membrane systems Next, let us recall the concept of efficient solvability by means of a family of recognizer membrane systems (see [4] for more details). Definition 2. A decision problem X= (IX, θX)is solvable in polynomial time by a family Π={Π(n)|n∈N}of recognizer membrane systems from a class R, in a uniform way, denoted by X∈PMCR, if the following statements hold: •the family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(n)from n∈N; •there exists a pair (cod, s)of polynomial-time computable functions over the set IXsuch that: – for each instance u∈IX,s(u)is a natural number and cod(u)is the input multiset of the system Π(s(u)); – for each n∈N,s−1(n)is a finite set; – the family Πis polynomially bounded with regard to (X, cod, s), that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(s(u)) + cod(u)is halting and it performs at most p(|u|); – the family Πis sound with regard to (X, cod, s), that is, for each u∈IX, if there exists an accepting computation of Π(s(u))+cod(u), then θX(u) = 1; – the family Πis complete with regard to (X, cod, s), that is, for each u∈IX, if θX(u) = 1, then every computation of Π(s(u)) + cod(u)is an accepting one. The polynomial complexity class PMCRis closed under polynomial-time reduction and under complement [5]. 3 Tissue-like P Systems with Active Cells This new kind of P systems keeps the inspiration keeps the foundations of classical tissue P systems, that is, the exchange of elements between the cells. Here, instead of the use of symport/antiport rules, we are going to introduce the application of the rules typically used in cell-like P systems with active membranes. 3.1 Syntax Definition 3. A tissue-like P system with active membranes and separation rules of degree q≥1is a tuple (Γ, Γ0, Γ1, H, H0, H1, µ, M1, . . . , Mq,R, iout), where: •Γis a finite alphabet and H={1, . . . , q}; • {Γ0, Γ1}is a partition of Γand {H0, H1}is a partition of H; • M1, . . . , Mqare finite multisets over Γ; • R is a finite set of rules over Γof the following forms: P Systems with Active Cells 179 (a) [a→u]α hfor h∈H, α ∈ {+,−,0}, a ∈Γ, u ∈Mf(Γ)(object evolution rules). (b) a[ ]α1 h→[b]α2 hfor h∈H, α1, α2∈ {+,−,0}, a, b ∈Γ(send-in communication rules). (c) [a]α1 h→b[ ]α2 hfor h∈H, α1, α2∈ {+,−,0}, a, b ∈Γ(send-out communication rules). (d) [a]α h→bfor h∈H, α ∈ {+,−,0}, a, b ∈Γ(dissolution rules). (e) [a]α1 h→[b]α2 h[c]α3 hfor h∈H, α1, α2, α3∈ {+,−,0}, a, b, c ∈Γ(division rules for elementary membranes). (e) [a]α1 h→[Γ0]α2 h[Γ1]α3 hfor h∈H, α1, α2, α3∈ {+,−,0}, a ∈Γ(separation rules for elementary membranes). (f) [[ ]α1 h0[ ]α2 h1]α h→[[ ]α3 h0]α5 h[[ ]α4 h1]α6 hfor h, h0, h1∈H, α, α1, α2, α3, α4, α5, α6∈ {+,−,0}(division rules for non-elementary membranes). (f) [[ ]α1 h0[ ]α2 h1]α h→[Γ0[ ]α3 h0]α5 h[Γ1[ ]α4 h1]α6 hfor h∈H, h0∈H0, h1∈H1, α, α1, α2, α3, α4, α5, α6∈ {+,−,0}(separation rules for non-elementary membranes). •iout ∈H∪ {env}, where env ∈ Γ∪H. A tissue-like P system with active cells of degre q≥1 can be viewed as a set of qcells, labelled by elements of H, arranged in a directed structure µgiven by a directed graph (the cell structure) whose nodes hthat have outdegree(h) = 0 are called elementary cells, such that: (a) M1, . . . , Mqrepresent the finite multisets of objects (symbols of the working alphabet Γ) initially placed in the qcells of the system; (b) Ris a finite set of rules over Γassociated with the system; and (c) iout ∈H∪ {env}indicates the output region. We use the term region ito refer to cell iin the case i∈Hand to refer to the “environment” of the system in the case i=env. If the membrane system makes no use of separation rules for nonelementary cells, then sets H0and H1will be omited. If separation rules either for elementary and non-elementary cells are not used, then we can omit either the sets H0and H1and Γ0and Γ1. The length of a rule is the number of objects involved in it (for instance, the length of the object evolution rule [ a→u]α his 1 + |u|. Let us notice that in this framework we can change (classical) object evolution rules by cooperative evolution rules (see [11] for more details). For each cell hdifferent for cells hwith indegree(h)= 0, we denote p(h) the label of the parent of hin µ. By convention, the “parent” of cells hwith indegree(h) = 0 is the environment of the system 3.2 Semantics An instantaneous description or a configuration Ctat an instant tof a P system with active cells is described by the cell structure at instant tand all multisets of objects over Γassociated with all the membranes present in the system at the moment. 180 D. Orellana-Mart´ın An object evolution rule [a→u]α his applicable to a configuration Ctat an instant t, if there exists a cell labelled by hwith polarization αin Ctwhich contains object a. When applying such a rule, object ais consumed and all objects from multiset uare produced in that membrane. A send-in communication rule a[ ]α1 h→[b]α2 his applicable to a configuration Ctat an instant t, if there exists a cell labelled by hwith polarization α1in Ctsuch that indegree(h)>0 and its parent one of its parent cells contain object a. When applying such a rule, object ais consumed from the selected parent cell and object bis produced in the corresponding cell h, and the polarization of cell hchanges to α2. A send-out communication rule [ a]α1 h→b[ ]α2 his applicable to a configuration Ctat an instant t, if there exists a cell labelled by hwith polarization α1in Ct such that it contains object a. When applying such a rule, object ais consumed from such cell and object bis produced in the one of its parent cells chosen in a non-deterministic way, and the polarization of cell hchanges to α2. A dissolution rule [ a]α h→bis applicable to a configuration Ctat an instant t, if there exists a cell labelled by hwith polarization αin Ct, different from the output region, such that it contains object a. When applying such a rule, object a is consumed, cell his dissolved and its objects are sent to one of the parents cells, chosen non-deterministically (or ancestors that have not been dissolved). For all h′such that f(h′) = hand h′′ such that f(h) = h′′, when his dissolved, then new edges from all h′′ to all h′are created, and edges from h′′ to hand from hto h′ are removed. A division rule [ a]α1 h→[b]α2 h[c]α3 his applicable to a configuration Ctat an instant t, if there exists a cell labelled by hwith polarization α1in Ct, different from the output region, such that it is an elementary cell and contains object a. When applying such a rule, the cell is divided into two cells with the same label, one with polarization α1and the other one with polarization α2; at the same time, object ais consumed and object bappears in the first cell, and cin the second one, and the remaining objects get duplicated in the two created cells. For all h′ such that f(h′) = hand h′′ such that f(h) = h′′, when his dissolved, then edges from all h′′ to hand from hto h′are duplicated. A separation rule [ a]α1 h→[Γ0]α2 h[Γ1]α3 his applicable to a configuration Ctat an instant t, if there exists a cell labelled by hwith polarization α1in Ct, different from the output region, such that it is an elementary cell and contains object a. When applying such a rule, the cell is separated into two cells with the same label, one with polarization α1and the other one with polarization α2; at the same time, object ais consumed and the multiset of objects contained in membrane h get distributed: the objects from Γ0are placed in one cell, those from Γ1are placed in the second one. For all h′such that f(h′) = hand h′′ such that f(h) = h′′, when his dissolved, then edges from all h′′ to hand from hto h′are duplicated. A division rule [[ ]α1 h0[ ]α2 h1]α h→[[ ]α3 h0]α5 h[[ ]α4 h1]α6 his applicable to a configuration Ctat an instant t, if there exists a cell labelled by hwith polarization αin Ct, different from the output region, such that it is the parent of a cell labelled by P Systems with Active Cells 181 h0with polarization α1and of another cell labelled by h1with polarization α2. When applying such a division rule to a cell labelled by hin a configuration Ct, that cell is divided into two cells with the same label with polarizations α5and α6, in such a way that the contents (multiset of objects) and relations (children and parent cells) are duplicated into the two new cells, except from cells labelled by h0, that becomes a child cell of the first one, with polarization α3, and h1, that becomes a child cell of the second one, with polarization α4. For all h′such that f(h′) = hand h′′ such that f(h) = h′′, when his dissolved, then edges from all h′′ to hand from hto h′are duplicated (except for edges from hto h0and h1, which ones remains one for each new created cell). A separation rule [[ ]α1 h0[ ]α2 h1]α h→[Γ0[ ]α3 h0]α5 h[Γ1[ ]α4 h1]α6 his applicable to a configuration Ctat an instant t, if there exists a cell labelled by hwith polarization αin Ct, different from the output region, such that it is the parent of a cell labelled by h0with polarization α1and of another cell labelled by h1with polarization α2. When applying such a separation rule to a cell labelled by hin a configuration Ct, that cell is separated into two cells with the same label with polarizations α5and α6, in such a way that the contents (multisets of objects) and relations (children cells) are distributed as follows: The first cell receives the multiset of objects from Γ0, and all child cells whose label belongs to H0; and the second cell receives the multiset of objects from Γ1, and all child cells whose label belongs to H1. For all h′ such that f(h′) = hand h′′ such that f(h) = h′′, when his dissolved, then edges from all h′′ to hare duplicated, and edges from hto h′are distributed depending on whether they belong to H0or H1. In tissue-like P systems with active cells, the rules are applied according to the following principles: •The rules associated with membranes labelled with hare used for all copies of this membrane. •At one transition step, one object can be used by only one rule (chosen in a non-deterministic way). •At one transition step, a cell can be subject of only one rule of types (b)–(f), and then it is applied at most once. •Object evolution rules can be simultaneously applied to a cell with one rule of types (b)–(f). Object evolution rules are applied in a maximally parallel manner. •If at the same time a membrane labelled with his divided/separated by a rule of type (e) or (f) and there are objects in this cells which evolve by means of rules of type (a), then we suppose that first the evolution rules of type (a) are used, changing the objects, and then the separation is produced. Of course, this process takes only one transition step. •Output cell can never get divided, separated, nor dissolved. Let us consider a tissue-like P systems with active cells ΠWe say that configuration Ctyields configuration Ct+1 in one transition step, denoted by Ct⇒ΠCt+1, if we can pass from Ctto Ct+1 by applying the rules from the system following the 182 D. Orellana-Mart´ın previous remarks. A computation of Πis a (finite or infinite) sequence of configurations such that: (a) the first term is the initial configuration of the system; (b) for each n≥1, the n-th configuration of the sequence is obtained from the previous configuration in one transition step; and (c) if the sequence is finite (called halting computation) then the last term is a halting configuration (a configuration where no rule of the system is applicable to it). All computations start from an initial configuration and proceed as stated above; only halting computations give a result, which is encoded by the objects present in the output region iout associated with the halting configuration. If C={Ct}t<r+1 of Π(r∈N) is a halting computation, then the length of C, denoted by |C|, is r, that is, |C| is the number of non-initial configurations which appear in the finite sequence C. For each i(1 ≤i≤q) we denote by Ct(i) the finite multiset of objects over Γcontained in all cells labelled by i(by applying division or separation rules different cells with the same label can be created) at configuration Ct. 3.3 Families of tissue-like P systems with active cells We use the following notations: • NAC(α, β, δ), where α∈ {+e, −e},β∈ {+c, −c}and δ∈ {+d, −d}, is the class of all recognizer P systems with active cells without using division nor separation rules. • DAC(α, β, δ, γ), where α∈ {+e, −e},β∈ {+c, −c},δ∈ {+d, −d}and α∈ {+n, −n},is the class of all recognizer P systems with active cells and division rules. • SAC(α, β, δ, γ), where α∈ {+e, −e},β∈ {+c, −c},δ∈ {+d, −d}and α∈ {+n, −n},is the class of all recognizer P systems with active cells and separation rules. The meaning of parameters is the following: •if α= +e(resp., −e) then evolution rules are permitted (resp., forbidden). •if α= +c(resp., −c) then communication rules are permitted (resp., forbidden). •if α= +d(resp., −d) then dissolution rules are permitted (resp., forbidden). •if α= +n(resp., −n) then division/separation rules for elementary and nonelementary cells are permitted (resp., only division/separation rules for elementary cells are permitted). 3.4 Another (not so relevant) approach One question discussed when this framework was being created was: In tissue-like membrane systems, the natural definition would be the one where when we do a communication rule, the cell interacts the environment (objects go P Systems with Active Cells 183 to the environment in send-out communication rules and comes from it in send-in communication rules. The same goes to dissolution rules, that is, when a cell dissolves, its contents go to the environment. This definition seems the best in order to capture the behavior of tissue P systems. But because of the simple structure created, it has little interest regarding the computational complexity of these systems. If this kind of systems is defined, we can suppose that there are qcells disposed in the environment, and they can interact with it through communication and dissolution rules. But we can simulate this behavior with P systems with active membranes with q+1 membranes, where qmembranes are situated within one that acts as the environment in the previous system. So complexity classes where these families of P systems were involved in would be weaker than classical P systems with active membranes, therefore it will not be considered. 4 Some Results About Computational Complexity First of all, it is easy to see that every P system with active cells is at least as powerful as its active membranes counterpart. It can be proved because every P system with active membranes structure is defined by a rooted tree µ. A tree is a particular case of a graph, where cycles are not allowed. For every P system with active membranes, we can define a P system with active cells that simulates its behavior. Let Π= (Γ, Γ0, Γ1, H, H0, H1, µ, M1, . . . , Mq,R, iout) a P system with active membranes. We can create (in polynomial time) a P system with active membrane that simulates its behavior. Let Π′= (Γ, Γ0, Γ1, H, H0, H1, µ′,M1, . . . , Mq,R, iout) be the P system with active cells that simulates its behavior. µ′is constructed as follows: •Let µ′be a single node h, where his the label of the skin membrane of Π. •For every membrane h′situated within another membrane hin Π, we create a node h′in µ′and add an edge from hto h′. The directed graph obtained has the shape of a directed rooted tree, and as it has the same set of rules, semantics of the system makes Π′simulate the behavior of Π′. We can conclude with: Theorem 1. PMCAM(α,β,δ,γ)⊆PMCAC(α,β,δ,γ), no matter which kinds of rules we are using. 4.1 Some complexity classes As it happened with P systems with active membranes, we can use the Milano Theorem [14] to state that no computationally hard problems can be solved in polynomial time without using rules allowing the generation of an exponential number of membranes/cells in polynomial time. Then: