Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems

Vol.:(0123456789) 1 3 Journal of Membrane Computing (2019) 1:85–92 https://doi.org/10.1007/s41965-018-00004-9 REGULAR PAPER Minimal cooperation asaway toachieve theefficiency incell‑like membrane systems DavidOrellana‑Martín1 · LuisValencia‑Cabrera1· AgustínRiscos‑Núñez1· MarioJ.Pérez‑Jiménez1 Received: 13 July 2018 / Accepted: 14 December 2018 / Published online: 1 February 2019 © Springer Nature Singapore Pte Ltd. 2019 Abstract Cooperation is doubtless a relevant ingredient on rewriting rules based computing models. This paper provides an overview on both classical and newest results studying how cooperation among objects influences the ability of cell-like membrane systems to solve computationally hard problems in an efficient way. In this paper, two types of such membrane systems will be considered: (a) polarizationless Psystems with active membranes without dissolution rules when minimal cooperation is permitted in object evolution rules; and (b) cell-like Psystems with symport/antiport rules of minimal length. Specifically, assuming that P is not equal to NP, several frontiers of the efficiency are obtained in these two computing frameworks, in such manner that each borderline provides a tool to tackle the P versus NP problem. Keywords Minimal cooperation· Cell-like P systems· Computational complexity theory 1 Introduction Membrane Computing is a bio-inspired computational paradigm based in the structure and behaviour of living cells. Created in 1998 by Păun [15], it has been a very fruitful area from the point of view of the applications. From theoretical computer science, results within the fields of formal languages [16], computability theory [4] and computational complexity theory [19], to applications in biology [6], robotics [2] and fault diagnosis [27]. An extensive introduction of the area can be found in [5, 12, 14, 17, 29, 30], so these reference can be useful for readers interested in a further reading. Cooperation between cells is a widespread phenomenon in nature and generally has a cost for the cooperating cells. Cooperation and competition can play a role in achieving robust developmental processes in multicellular organisms [3]. In the framework of Membrane Computing, the dynamics of cell-like membrane systems is captured by means of rewriting rules that allow the evolution of objects. Any object, alone or together with more objects can be transformed into other objects, can pass through a membrane or can dissolve/divide/separate the membrane where it currently resides [15]. Non-cooperative systems contain rules abstracting proteins that transport only one solute across the membrane (for example, the glucose transporter in red blood cell membranes). Membranes are both separators and channels of communication, but they are passive participants to the process. However, from biochemistry view the membranes are not at all passive, the passing of a chemical compound through a membrane is often done by some kind of interaction with the membrane itself [18]. P systems with active membranes are interesting particular cases of non-coop- erative systems. In the first version of these systems [18], electrical charges from the set {+,−,0} are associated with membranes. Besides, each rule is associated with a membrane (labelled by h) and it is applicable to a configuration at an instant t if the object corresponding to its left-hand side is in such membrane of that configuration, and the membrane has the polarization prefixed in the rule. Even though on the left-hand side of the rule there is only one * David Orellana-Martín [email protected] Luis Valencia-Cabrera l[email protected] Agustín Riscos-Núñez [email protected] Mario J. Pérez-Jiménez mar[email protected] 1 Research Group onNatural Computing, Department ofComputer Science andArtificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012Seville, Spain 86 D.Orellana-Martín et al. 1 3 object, there exists, in some sense, a kind of cooperation (object/label/polarization) in order to trigger the rule. A particular case of cooperative system is cell-like P systems with symport/antiport rules [13] where there exist communication rules length at least two (more than one object are involved in the rules). In these systems, communication is implemented by means of symport/antiport rules abstracting trans-membrane transport of couples of chemical substances, in the same or in opposite directions. As it is stated by the so-called Milano theorem [28], no computationally hard problems can be solved in polynomial time without using rules allowing the generation of an exponential workspace (expressed in terms of the number of membranes and objects) in polynomial time, unless 𝐏=𝐍𝐏 holds. So, in order to achieve efficiency (the ability to provide polynomial-time solution to computationally hard problems), division rules (abstracting cell division process) and separation rules (abstracting membrane fission process) are also considered. It is worth pointing out that dissolution and division rules for non-elementary membranes (they have membrane inside) are not necessary/relevant to get the computational efficiency in (non-cooperative) P systems with active membranes. Nevertheless, if electrical charges are forbidden/removed, then dissolution rules start to play a relevant role in these systems from a computational complexity point of view. Only problems in class P can be efficiently solved by means of families of polarizationless Psystems with active membranes which make no use of dissolution rules, even in the case that division rules for non-elementary membranes are allowed [8]. The situation is similar for non-cooperative cell-like P systems with symport/antiport rules where only a single object is involved in any rule (so, only symport rules with length 1 are permitted). The main goal of this work is to present recent results concerning the efficiency of both computing frameworks: polarizationless P systems with active membranes and celllike P systems with symport/antiport rules when minimal cooperation is considered. The term “minimal cooperation” is used in the following sense: in the first case, the left-hand side of each rule has at most a couple of objects. In the second case, at most two objects are involved in each communication (symport/antiport) rules. The paper is organized as follows: first, concepts as presumed efficiency and techniques to tackle the P vs. NP problem are explained. Section3 is devoted to introduce the two frameworks we are going to work on. In the next section, three techniques to prove the non-efficiency of certain models will be provided. In Sect.5, the results obtained in the two frameworks will be exposed, as well as enough citations to give the reader an extensive bibliography to consult. Finally, some conclusions and open questions are stated. 2 Efficiency ofcomputing models Let us recall that P (respectively, NP) denotes the class of all decision problems which can be solved by a deterministic (resp. non-deterministic) Turing machine working in polynomial time with respect to the size of the input. Problems in class P are called tractable problems. NP- complete problems are the hardest problems within the class NP. It is unknown if they are non-tractable problems but it is widely believed that NP-complete problems are intractable. A computing model with the ability to provide polynomial-time solutions to intractable problems (respectively, NP-complete problems) is called an efficient (respectively, presumably efficient) computing model. In a non-efficient computing model, only problems in class P can be solved in polynomial time. Let M1 and M2 be two computing models such that M2 is obtained from M1 by adding some syntactic or semantic ingredients, and we denote it by M1⊆M2 . In this case, if M1 is a non-efficient computing model and M2 is a presumably efficient one, then we can say that passing from M1 to M2 amounts to passing from non-efficiency (only tractable problems can be efficiently solved) to presumed efficiency (presumably intractable problems can be efficiently solved). In this context, on the one hand in order to show that 𝐏=𝐍𝐏 , it is enough to find a polynomial-time solution to one NP-complete problem in M2 and translate it into a polynomial-time solution in M1 , that is, proving that the ingredients added to obtain M2 from M1 do not play a relevant role in that solution. On the other hand, in order to show that 𝐏≠𝐍𝐏 , it is enough to find one NP-complete problem that cannot be solved in polynomial time in M1 , that is, that the ingredients added to obtain M2 from M1 are crucial to obtain the presumed efficiency of computing model M2 , as visualized in Fig.1. In what follows, we assume that the reader is already familiar with the basic notions and terminology of P systems. For more details, see [15]. Fig. 1 Frontiers of efficiency between two computing models 87Minimal cooperation asaway toachieve theefficiency incell-like membrane systems 1 3 3 The computational frameworks In this section, the computational frameworks of membrane systems considered throughout this paper are introduced. 3.1 Polarizationless P system withactive membranes A polarizationless P system with active membranes (𝛤,𝜇, 1 ,…,q,,iout) of degree q≥1 , can be viewed as a set of q membranes, injectively labelled by elements of H={1, …,q} , arranged in a hierarchical structure 𝜇 given by a rooted tree, such that: (a) 1,…,q represent the finite multisets of objects (elements of the working alphabet 𝛤 ) initially placed in the q membranes of the system; (b)  is a finite set of rules over 𝛤 associated with the labels including division rules inspired from mitosis process; (c) iout ∈H∪{env} represents a distinguished zone which will encode the output of the system. We use the term zone i to refer to membrane i in the case i∈H and to refer to the environment in the case i=env . The leaves of 𝜇 are called elementary membranes; any other membrane is said to be non-elementary. Semantics of polarizationless P systems with active membranes are defined as it is usual in P systems with active membranes (see [9, 18] for details). A new kind of models can be considered when separation rules, inspired by the membrane fission process, and being used instead of division rules as a mechanism to produce an exponential number of membranes in linear time. These rules are associated with a (prefixed) partition {𝛤0,𝛤1} of the working alphabet 𝛤 and a (prefixed) partition {H0,H1} of the set of labels H. – Separation rules for elementary membranes [a]h → [𝛤0]h[𝛤1]h , for h ∈ H⧵ { iout} , a∈𝛤 and h is not the label of the root of 𝜇 . – Separation rules for non-elementary membranes [[ ] h0[] h1]h → [𝛤 0 [] h0]h[𝛤 1 [] h1]h , where h ∈ H⧵ { iout} is not the label of the root of 𝜇 , h0∈H0 and h1∈H1 . A separation rule [a]h → [𝛤0]h[𝛤1]h is applicable to a configuration t at an instant t, if there exists a membrane labelled by h in t such that it is an elementary membrane in t and contains object a. When applying such a rule, the membrane is separated into two membranes with the same label; at the same time, object a is consumed and the multiset of objects contained in membrane h is distributed as follows: the objects from 𝛤0 are placed in one membrane; those from 𝛤1 are placed in another one. A separation rule [[ ] h0[] h1]h → [𝛤 0 [] h0]h[𝛤 1 [] h1]h is applicable to a configuration t at an instant t, if there exists a membrane labelled by h in t such that it contains a membrane labelled by h0 and another membrane labelled by h1 . When applying such a separation rule to a membrane labelled by h in t , that membrane is separated into two membranes with the same label, in such a way that the contents (objects and inner membranes) are distributed as follows: The first membrane receives the objects from 𝛤0 and all inner membranes whose label belong to set H0 ; while the second membrane receives the objects from 𝛤1 and all inner membranes whose label belongs to set H1 . 3.1.1 Minimal cooperation inobject evolution rules Next, minimal cooperation in object evolution rules is introduced in the framework of polarizationless P systems with active membranes. In general, the term “minimal cooperation” associated with membrane systems is used when there is at least one rule in the system whose left-hand side consists of exactly two symbols. Definition 1 In the context of polarizationless P systems with active membranes, the following kinds of minimal cooperation in object evolution rules are considered. – Primary minimal cooperation (pmc)In this case, object evolution rules are of the form [u → v]h , where h∈H and u,v are multisets over the working alphabet 𝛤 such that 1≤|u|,|v|≤2 , but at least one such rule verifies |u|=2 . – Bounded minimal cooperation (bmc)In this case, object evolution rules are of the form [u → v]h , where h∈H and u,v are multisets over the working alphabet 𝛤 such that 1≤|v|≤|u|≤2 , but at least one such rule verifies |u|=2 . – Minimal cooperation and minimal production (mcmp)In this case, object evolution rules are of the form [a → b]h,[ab → c]h , where h∈H and a,b,c are symbols that belong to the working alphabet 𝛤 , but at least one such rule is of the second type. We denote by 0(𝛼,𝛽,𝛾,𝛿) (respectively, 0(𝛼 , 𝛽 , 𝛾 , 𝛿) ) the class of all polarizationless P systems with active membranes and with division rules (respectively, separation rules), where the meaning of parameters 𝛼 , 𝛽 , 𝛾 , 𝛿 is the following: – If 𝛼=pmc (resp. 𝛼=bmc or 𝛼=mcmp ) then primary minimal cooperation (resp. bounded minimal cooperation or minimal cooperation and minimal production) in object evolution rules are permitted. If 𝛼=+e then 88 D.Orellana-Martín et al. 1 3 only non-cooperative rules are permitted as object evolution rules. – 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 non-elementary membranes are permitted (resp. only division/separation rules for elementary membranes are permitted). In this context, counting membrane systems instead of recognizer membrane systems were considered in [23]. The output of these systems is natural numbers instead of yes or no. 3.2 Cell‑like P systems withsymport/antiport rules Cell-like P systems with symport/antiport rules were introduced in [13] aiming to abstract the biological phenomenon of trans-membrane transport of couples of chemical substances, in the same or in opposite directions. A P system with symport/antiport rules Π=(𝛤,,𝜇, 1 ,…,q, 1 ,…,q,iout) of degree q≥1 can be viewed as a set of q membranes, labelled by 1, …,q , arranged in a hierarchical structure 𝜇 given by a rooted tree whose root is called the skin membrane, such that: (a)  1 ,…,q represent the finite multisets of objects initially placed in the q membranes of the system; (b)  is the set of objects initially located in the environment of the system, all of them available in an arbitrary number of copies; (c)  1 ,…,q are finite sets of communication rules over 𝛤 ( i is associated with the membrane i of 𝜇 ); and (d) iout represents a distinguished zone which will encode the output of the system. We use the term zone i ( 0≤i≤q ) to refer to membrane i in the case 1≤i≤q and to refer to the environment in the case i=0 . The length of rule (u,out) or (u,in) (resp. (u,out;v,in)) is defined as |u| (resp. |u|+|v| ). In these models, division rules and separation rules are introduced in a similar way that in polarizationless P systems with active membranes, both in syntax and semantics. For each natural number k≥1 , we denote by (k) (respectively, (k) ) the class of P systems with symport/antiport rules and division rules (respectively, separation rules) such that the length of the communication rules is at most k. When division or separation also for non-elementary membranes is permitted, then we denote ne(k) and ne(k) , respectively. If the set  associated with the environment is the empty set, then we denote  (k) ,  (k) ,  ne ( k) and  ne ( k) , respectively. 4 Techniques toprove non‑efficiency To show the non-efficiency of computing models, three basic techniques have been used at the next section. – Dependency graphA directed graph (dependency graph) GΠ associated with a membrane system Π is considered in such a way that there exists an accepting computation of Π if and only if there exists a path between two distinguished nodes in the dependency graph associated with it. – Algorithmic techniqueA deterministic algorithm  working in polynomial time that receives as input a membrane system Π and an input multiset m of Π is considered in such a manner that algorithm  reproduces the behaviour of a single computation of the system Π with input multiset m. – Simulation techniqueA membrane system Π� simulating (in an efficient way) a given membrane system Π is constructed, in such a way that: (a) Π� is obtained from Π by removing some syntactic/semantic ingredients; and (b) there exists an efficient and injective correspondence between accepting computations of Π� and accepting computations of Π . 5 Non‑efficiency andpresumed efficiency ofmembrane systems The role of minimal cooperation is studied from the computational complexity point of view. In the case of polarizationless P systems with active membranes, object evolution rules whose left-hand side consists of a couple of objects are considered. In the case of cell-like P systems with symport–antiport rules, minimal cooperation that is expressed by the property of the length of communication (symport/antiport) rules equals to two. 5.1 Polarizationless P systems withactive membranes P systems with active membranes and electrical charges are (non-cooperative) presumably efficient computing models even though dissolution rules and division for non-elementary membranes are forbidden. However, if polarizations are removed the dissolution rules play a crucial role from complexity point of view. In fact, using the dependency graph technique it has been shown that families of non-cooperative polarizationless P systems with active membranes which make no use of dissolution rules can only solve tractable problems in an efficient way [8, 21]. 89Minimal cooperation asaway toachieve theefficiency incell-like membrane systems 1 3 Theorem1 𝐏=𝐏𝐌𝐂 0 (+e,+c,−d,+n)=𝐏𝐌𝐂 0 (+e,+c,−d,+n) . Nevertheless, when dissolution rules are allowed in that framework, the situation is quite different. If division rules for non-elementary membranes are also permitted, then PSPACE-complete problems can be solved in polynomial time [1]. Theorem2 𝚀𝚂𝙰𝚃 ∈𝐏𝐌𝐂 0 (+e,+c,+d,+n) . It is an open question what happens if division rules only for elementary membranes are permitted in polarizationless Psystems with active membranes and with dissolution rules (the so-called Păun’s conjecture). Open question: 𝐏𝐌𝐂 0 (+e,+c,+d,−n)=𝐏 ? The presumed efficiency of polarizationless P systems with active membranes and membrane division can be reached by considering bounded minimal cooperation, even in the case that dissolution rules and division rules for nonelementary membranes are forbidden [22]. Theorem3 𝚂𝙰𝚃 ∈𝐏𝐌𝐂 0 (bmc,+c,−d,−n) . However, if separation rules are used instead of division rules in polarizationless P systems with active membranes which make use of bounded minimal cooperation then, using the algorithmic technique, the limitation on the efficiency of these systems has been shown [24]. Theorem4 𝐏𝐌𝐂 0 (bmc,+c,−d,+n)=𝐏 . Families of polarizationless P systems with active membranes and membrane separation which use primary minimal cooperation in object evolution rules can solve NP-complete problems in polynomial time, even in the case that dissolution rules and division rules for non-elementary membranes are forbidden [21]. Theorem5 𝚂𝙰𝚃 ∈𝐏𝐌𝐂 0 (pmc,+c,−d,−n) . The result of Theorem3 has been improved in the sense that minimal cooperation in object evolution rules producing only a single object suffices to reach the efficiency of polarizationless P systems with active membranes [25]. Theorem6 𝚂𝙰𝚃 ∈𝐏𝐌𝐂 0 (mcmp,+c,−d,−n) . By considering the corresponding “counting version” of membrane systems from 0 ( mcmp ,+ c ,− d ,− n) , the previous result has been extended to the counting problem #SAT [23], which is a well-known # P-complete problem [11]. Bearing in mind that minimal cooperation with minimal production in object evolution rules is a particular case of bounded minimal cooperation, we deduce the following result: Theorem7 𝐏𝐌𝐂 0 (mcmp , +c , −d , +n)=𝐏 . Thus, the following borderlines between the non-efficiency and the presumed efficiency have been obtained in the framework of polarizationless P systems with active membranes. Non efficiency Presumed efficiency Frontier 0(+e , +c , −d , +n) 0(+e , +c , +d , +n) Dissolution rules 0(+e,+c,−d,−n) 0(bmc,+c,+d,−n) Bounded minimal cooperation 0(bmc,+c,−d,+n) 0 ( pmc ,+ c ,+ d ,+ n) Kind of minimal cooperation 0 ( mcmp ,+ c ,− d ,− n) 0 ( mcmp ,+ c ,+ d ,− n) Kind of rules Let us recall that each such frontier provides a tool to tackle the P versus NP problem. For instance, in the framework of polarizationless P systems with active membranes and membrane division ( 0(+e , +c , ??, +n) ), passing from forbidding the use of dissolution rules to permitting them amounts to passing from non-efficiency to presumed efficiency. 5.2 Cell‑like P systems withsymport/antiport rules From the complexity point of view, non-cooperative cell-like P systems with symport/antiport rules and polarizationless P systems with active membranes and without dissolution rules have some similarities. In particular, the dependency graph technique used to prove Theorem1 can be adapted to show that such non-cooperative systems are not efficient unless 𝐏=𝐍𝐏 holds. Theorem8 𝐏=𝐏𝐌𝐂ne ( 1 )=𝐏𝐌𝐂ne ( 1 ) . However, if minimal cooperation in communication rules is considered, then computational efficiency can be reached when membrane division rules are used [26]. Theorem9 𝙷𝙰𝙼 −𝙲𝚈𝙲𝙻𝙴 ∈ 𝐏𝐌𝐂(2) . 90 D.Orellana-Martín et al. 1 3 Concerning membrane separation rules, if the length of communication rules is at most two then, using the algorithmic technique, it can be shown that separation rules are not enough to provide polynomial-time solutions to computationally hard problems, assuming that 𝐏≠𝐍𝐏 . Nevertheless, P systems with symport/antiport rules with length at most three and with membrane separation are computationally efficient [10]. Theorem10 𝐏=𝐏𝐌𝐂(2)and 𝚂𝙰𝚃 ∈𝐏𝐌𝐂(3) . In [20], a polynomial-time solution for the QSAT problem, which is a well-known PSPACE-complete problem [7], has been given by means of a family of cell-like P systems with communication rules with length at most three which make use of division rules for non-elementary membranes. Theorem11 𝚀𝚂𝙰𝚃 ∈𝐏𝐌𝐂ne ( 3 ) . Next, the role of environment associated with P systems with symport/antiport rules is studied from the complexity point of view. Let us recall that in these systems environment provides an arbitrary large amount of objects at the initial configuration. First, it has been shown that the role of the environment is not relevant in Psystems with symport/antiport rules and membrane division using simulation technique. Theorem 12 For each k≥1 , we have 𝐏𝐌𝐂   ( k )= 𝐏𝐌𝐂  ( k ) . Second, it has been shown that P systems with symport/ antiport rules without environment and with membrane separation can only solve problems in class P in polynomial time [10] using algorithmic technique. Theorem13 For each k≥1 we have 𝐏=𝐏𝐌𝐂  (k) . Hence, in this kind of P systems the role of environment is important: 𝐏=𝐏𝐌𝐂  ( 3 ) and 𝚂𝙰𝚃 ∈𝐏𝐌𝐂( 3 ) . Thus, the following borderlines between the non-effi- ciency and the presumed efficiency have been obtained in the framework of polarizationless P systems with active membranes. Non efficiency Presumed efficiency Frontier (1) (2) Length of rules (2) (3) Length of rules (2) (2) (2) Length of rules Non efficiency Presumed efficiency Frontier  (2)  (2) Kind of rules    Environment 6 Conclusions In this work, an overview of the results related to the computational efficiency of membrane systems which make use of (minimal) cooperation is presented. Informally speaking, one could say that it is not surprising that in most cases models using cooperation prove to be more powerful than their non-cooperative counterparts, by setting an analogy with the existing gap between context-free and context-sensitive rules in the Chomsky hierarchy. This paper investigates the impact of (minimal) cooperation in the framework of cell-like membrane systems. That is, the goal is to restrict the cooperation to its limit, while minimizing the rest of ingredients of the model, in such a way that borderlines of efficiency (expressed in terms of the degree of cooperation) are unveiled. More precisely, the paper focuses on two case studies: allowing some “minimal” degree of cooperation in object evolution rules for polarizationless P systems with active membranes, and reducing symport/antiport rules to “minimal” length for cell-like P systems. There are many other P system models worth studying, which could probably benefit from the results gathered here by following analogous techniques but performing the corresponding adjustments. Recently, the computational efficiency of polarizationless P systems with active membranes and division rules which incorporates minimal cooperation with minimal production in communication rules (instead of in object evolution rules) has been studied. The results obtained are similar to the case of minimal cooperation in object evolution rules but with an important restriction: division rules for elementary and non-elementary membranes have been used. Moreover, it has been shown that efficiency can be reached using minimal cooperation with minimal production only in send-in rules (or only in send-out rules). – To reach the efficiency, can the use of division rules for non-elementary membranes be avoided? – What about the efficiency of polarizationless P systems with active membranes and separation rules which incorporates minimal cooperation with minimal production in communication rules? We conclude by presenting some additional open questions. 91Minimal cooperation asaway toachieve theefficiency incell-like membrane systems 1 3 – Is there a family of systems from 0 (mcmp , +c , −d , +n) (or from 0(mcmp , +c , −d , +n) ) providing a polynomial-time solution to the QSAT problem? – 𝚀𝚂𝙰𝚃 ∈𝐏𝐌𝐂  ne (2 ) ? – 𝚀𝚂𝙰𝚃 ∈𝐏𝐌𝐂  ne  ( 3 ) ? Acknowledgements This work is supported by the research project TIN2017-89842-P, cofinanced by Ministerio de Economía, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigación (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union. The authors also acknowledge the Grants No 61320106005 of the National Natural Science Foundation of China. References 1. Alhazov A, Pérez-Jiménez MJ. Uniform solution of QSAT using polarizationless active membranes. In Durand-Lose J, Margenstern M, editors. Machines, computations, and universality. Lecture notes in computer science, vol. 4664; 2007. pp. 122–33. 2. Pavel AB, Buiu C. Using enzymatic numerical P systems for modeling mobile robot controllers. Nat Comput. 2012;11(3):387–93. 3. Celiker H, Gore J. Cellular cooperation: insights from microbes. Trends Cell Biol Trends Cell Biol. 2013;23(1):9–15. 4. Freund R, Păun Gh. On the number of non-terminal symbols in graph-controlled, programmed and matrix grammars. In Margenstern M, Rogozhin Y, editors. Machines, computations, and universality, international conference on machines, computations, and universality. Berlin, Heidelberg: Springer; 2001. pp. 214–25. 5. Frisco P, Gheorghe M, Pérez-Jiménez MJ. Applications of membrane computing in systems and synthetic biology. Complexity and computation series: emergence. 2014. 6. García-Quismondo M, Graciani C, Riscos-Núñez A. Membrane computing as a modelling tool: looking back and forward from Sevilla. In Graciani C, Riscos-Núñez A, Păun Gh, Rozenberg Gr, Salomaa A, editors. Enjoying natural computing: essays dedicated to Mario de Jesús Pérez-Jiménez on the occasion of his 70th birthday. Springer International Publishing; 2018. pp. 114-29. 7. Garey MR, Johnson DS. Computers and intractability a guide to the theory of NP-completeness. Freeman and Company; 1979. 8. Gutiérrez-Naranjo MA, Pérez-Jiménez MJ, Riscos-Núñez A, Romero-Campero FJ. On the power of dissolution in P systems with active membranes. In Freund R, Păun Gh, Rozenberg Gr, Salomaa A, editors. Membrane computing, 6th international workshop, WMC 2005, Vienna, Austria, July 18–21, 2005. Revised Selected and Invited Papers. Lecture notes in computer science, vol. 3850; 2006. pp. 224–40. 9. Leporati A, Ferretti C, Mauri G, Pérez-Jiménez MJ, Zandron C. Complexity aspects of polarizationless membrane systems. Nat Comput. 2009;8(4):703–17. 10. Macías-Ramos LF, Song B, Valencia-Cabrera L, Pan L, Pérez- Jiménez MJ. Membrane fission: a computational complexity perspective. Complexity. 2016;21(6):321–34. 11. Papadimitriou CH. Computational complexity. Boston: Addison- Wesley Publishing Company; 1994. 12. Pan L, Păun Gh, Pérez-Jiménez MJ, Song T. Bio-inspired Computing: theories and applications. Communications in computer and information science series; 2014. 13. Păun A, Păun Gh. The power of communication: P systems with symport/antiport. N Gener Comput. 2002;20(3):295–305. 14. Păun Gh, Rozenberg G, Salomaa A. The Oxford handbook of membrane computing. Oxford: Oxford University Press; 2009. 15. Păun Gh. Computing with membranes. J Comput Syst Sci. 2000;61(1):108–43. 16. Păun Gh. Languages in membrane computing: some details for spiking neural P systems. In: Ibarra OH, Dang Z, editors. Developments in language theory. Berlin, Heidelberg: Springer; 2006. p. 20–35. 17. Păun Gh. Membrane computing: an introduction. New York: Springer Natural Computing Series; 2002. 18. Păun Gh. P systems with active membranes: attacking NP-com- plete problems. J Autom Lang Comb. 2001;6:75–90. 19. Pérez-Jiménez MJ, Romero-Jiménez Á, Sancho-Caparrini F. Complexity classes in models of cellular computing with membranes. Nat Comput. 2003;2(3):265–85. https ://doi.org/10.1023/A:10254 49224 520. 20. Song B, Pérez-Jiménez MJ, Pan L. Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division. Biosystems. 2015;130:51–8. 21. Valencia-Cabrera L, Orellana-Martín D, Martínez-del-Amor MA, Pérez-Jiménez MJ, Riscos-Núñez A. Computational efficiency of minimal cooperation and distribution in polarizationless P systems with active membranes. Fundam Inf. 2017;153(1–2):147–72. 22. Valencia-Cabrera L, Orellana-Martín D, Martínez-del-Amor MA, Pérez-Jiménez MJ, Riscos-Núñez A. Polarizationless P systems with active membranes: Computational complexity aspects. J Autom Lang Comb. 2016;21(1–2):107–23. 23. Valencia-Cabrera L, Orellana-Martín D, Riscos-Núñez A, Pérez- Jiménez MJ. Counting membrane systems. In: Proceedings of the Eighteenth International Conference on Membrane Computing (CMC18), July 24–28, 2017. Bradford; 2017. pp. 359–72. 24. Valencia-Cabrera L, Orellana-Martín D, Riscos-Núñez A, Pérez- Jiménez MJ. Minimal cooperation in polarizationless P systems with active membranes. In Graciani C, Păun Gh, Orellana-Martín D, Riscos-Núñez A, Valencia-Cabrera L, editors. Proceedings of the Fourteenth Brainstorming Week on Membrane Computing, 1-5 February, 2016. Sevilla; 2016. pp. 327–56. 25. Valencia-Cabrera L, Orellana-Martín D, Riscos-Núñez A, Pérez- Jiménez MJ. Reaching efficiency through complicity in membrane systems: dissolution, polarization and cooperation. Theor Comput Sci. 2017;701:226–34. 26. Valencia-Cabrera L, Song B, Macías-Ramos LF, Pan L, Riscos- Núñez A, Pérez-Jiménez MJ. Minimal cooperation in P systems with symport/antiport: a complexity approach. In Macías LF, Păun Gh, Riscos A, Valencia L, editors. Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 2–6 February, 2015. Sevilla; 2015. pp. 301–23. 27. Wang T, Zhang GX, Pérez-Jiménez MJ. Fuzzy membrane computing: theory and applications. Int J Comput Commun Control. 2015;10(6):904–35. 28. Zandron C, Ferretti C, Mauri G. Solving NPcomplete problems using P systems with active membranes. In: Antoniou I, Calude CS, Dinneen MJ, editors. Unconventional models of computation. Heidelberg: Springer; 2000. p. 289–301. 29. Zhang G, Pérez-Jiménez MJ, Gheorghe M. Real-life applications with Membrane Computing. Complexity and computation series: emergence; 2017. 30. http://ppage .psyst ems.eu/ 92 D.Orellana-Martín et al. 1 3 David Orellana‑Martín received his degree in Computer Engineering and his MSc degree in Logic, Computation and Artificial Intelligence from the University of Seville. He is pursuing his Ph.D. degree in Computer Science. He is a member of the Research Group on Natural Computing, where he has coauthored over 30 scientific publications, over 10 of them in ISI JCR indexed journals. His main research interests are Computational Complexity Theory, Natural Computing (specially Membrane Computing), as well as Cryptography, Machine Learning and High-Performance Computing. He is member of the Website Committee of the International Membrane Computing Society. Luis Valencia‑Cabrera received his degree in Computer Engineering, his MSc and his Ph.D. in Logic, Computation and Artificial Intelligence from the University of Seville, Seville, Spain. In the past, he was working for an IT Consultant company from 2005 to 2010, receiving professional certifications by Oracle and IFPUG and getting another MSc in Software Development of Enterprise Applications. He is currently an Assistant Professor in the Department of Computer Science and Artificial Intelligence. He received the Ph.D. Extraordinary award for his doctoral thesis, defended in 2015. He has supervised a number of MSc and BSc theses, a doctoral thesis, and is currently advising another one. His main research interests include complex systems modelling and simulation, natural computing (especially membrane computing), theoretical computer science, and software development. He has over 50 scientific contributions, including more than 20 papers in ISI JCR journals, plus others in book chapters, non-indexed journals, some invited talks and conference proceedings. He has participated in around ten research projects (at National, European and International level). Agustín Riscos‑Núñez obtained his degree in Mathematics and his Ph.D in Mathematics from the University of Seville. He is an Associate Professor at the Department of Computer Science and Artificial Intelligence of the University of Seville since 2011. His research interests include: Complexity Theory, Bioinspired models of computation (specially focusing on Membrane Computing), Computational modelling, and Artificial Intelligence. He has coauthored more than 90 scientific publications (including more than 40 papers published in recognised international journals). He is member of the Steering Committee of the International Conference on Membrane Computing, and one of the founder members of the International Membrane Computing Society. Mario J. Pérez‑Jiménez received his degree in Mathematics from the University of Barcelona and the doctoral degree in Mathematics from the University of Seville. In the past, he was a lecturer and teaching assistant at the University of Barcelona and currently is a full Professor in the Department of Computer Science and Artificial Intelligence. From 2005 to 2007, he was a Guest Professor of the Huazhong University of Science and Technology, Wuhan, China. He is a numerary member of the Academia Europaea (The Academy of Europe) in the Section of Informatics. In addition, he is the head of the Research Group on Natural Computing at the University of Sevilla. He has supervised fourteen doctoral theses. His main research interests include theory of computation, computational complexity theory, natural computing (DNA computing and membrane computing), bioinformatics, and computational modelling for complex systems. Prof. Pérez- Jiménez has published 19 books in computer science and mathematics, and over 300 scientific papers in international journals (collaborating with researchers worldwide) and he is a member of the Editorial Board of six ISI journals. He has been the first scientific awarded with "Important Contributions to Membrane Computing" under the auspices of the European Molecular Computing Consortium, Edinburgh, 2008. In 2014, he received the University of Sevilla FAMA award for his outstanding research career. He is the main researcher in various European, Asian, Spanish and Andalusian research grants. From 2003, he is an expert reviewer of the Prospective and Evaluation National Agency of Spain. From May 2006, he is a European Science Foundation peer reviewer, from July 2008 he is an expert reviewer from the Romanian National University Research Council, and from October 2015, he is an international expert from the Russian Science Foundation, invited by the Russian International Affairs Council.