A solution to the only one object problem with dissolution rules

Vol.:(0123456789) Journal of Membrane Computing (2024) 6:101–108 https://doi.org/10.1007/s41965-024-00150-3 RESEARCH PAPER A solution totheonlyone object problem withdissolution rules JulienCaselmann1· DavidOrellana‑Martín2,3 Received: 31 January 2024 / Accepted: 5 April 2024 / Published online: 1 May 2024 © The Author(s) 2024 Abstract In the framework of membrane computing, (non-)uniform families of recognizer membrane systems are usually defined to solve abstract decision problems. In this sense, the use of finite resources for each member of the family makes the difference with respect to Turing machines solving these problems. While keeping the finite nature of these systems, it is interesting to know which type of problems can be solved by means of a single membrane system. For this purpose, the complexity class PMC1p R was defined as the class of problems that can be solved by means of a single membrane system in polynomial time. Due to the polynomial-time encoding of the input, at least all the problems from P can be solved with a trivial system. To go below P, the class PMC1f R restricts the definition of this encoding. In this work, we study the capability of different types of membrane systems to solve the ONLY-ONE-OBJECT problem, while having the encoding restriction. Keywords Membrane computing· Computational complexity theory· Only one object problem 1 Introduction Membrane computing is a young field of computer science research whose produced devices are known as membrane systems or P systems, that are models of computation inspired by the behavior and structure of biological cells. From the first work[1], authors have studied different aspects of membrane systems. On the one hand, theoretical studies have ranged from the definition of new variants of P systems[2], studying their computational power[3] and their ability to solve presumably hard problems[4], also keeping the interaction with other models of computation[5]. On the other hand, several applications have been found to be approachable by these models of computation, such as molecular biology[6], ecology[7, 8], classification problems[9], information fusion[10], robot control[11–14] and fault diagnosis[15], among others[16]. It is interesting to remark the work of the community in the field of software simulation, developing from generalist sequential software simulators[17] to hardware simulators[18, 19], among others[20]. A comprehensive relation and study of the bibliography of the field of Membrane Computing can be found in[21]. Using membrane computing to tackle different problems in computational complexity theory has been a hot research topic from the very beginning of the area[22]. Recent results in this context have been published in[23, 24], where different types of membrane systems have been studied. Two main types of P systems are studied while working on computational complexity theory: cell-like membrane systems[22], taking the structure of a living cell and recreating its internal compartments as computing processors; and tissue-like membrane systems[25], that take the inspiration from how cells interact with each other and with the environment when they are disposed as a tissue. But they are not the only one to deal with different aspects of complexity classes. For instance, distributed P systems[26] have been investigated for solving presumably hard problems, and authors focus on minimizing the number of communications between the different components of the system. Usually, PMCR is defined as the class of problems that can be solved by means of a family of recognizer membrane systems from the class R . * David Orellana-Martín [email protected] Julien Caselmann [email protected] 1 Humboldt-Universität zu Berlin, Berlin, Germany 2 Research Group onNatural Computing, Department ofComputer Science andArtificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012Sevilla, Spain 3 SCORE Lab, I3US, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012Sevilla, Spain 102 J.Caselmann, D.Orellana-Martín Here, two main characteristics arise while using these families of recognizer membrane systems. Let u be an instance of the decision problem X. When giving the instance u to the membrane system Π that solves it, it must be transformed to a multiset of objects, obtained through the application of a function cod. This function is asked to be polynomial-time computable; that is, that there exists a Turing machine that can transform the input u into the multiset cod(u). Of course, since we can compute any function that can be polynomial-time computable, any problem that lies in P can also be solved in this sense. That is why P⊆PMCR for any reasonable type of P systems R . Thus, it is not possible to “look below” P with these models of computation, as there is no possibility to obtain less power than solving, at least, problems from P in polynomial time. In[27] and consequent studies, authors introduced the concept of C-uniformity, where C is a classical complexity class, and it represents the resources that can be used for providing the input of the system. In this context, it has been demonstrated that the power to solve all the problems from P for some types of P systems comes from the P-uniformity definition itself. Usually, all the studies concerning membrane systems solving computationally hard problems are made by defining uniform (respectively, non-uniform) families of recognizer P systems of any type, where each member of the family is able to solve all the instances of the same size (resp., only one instance of the problem). There are some differences between these families of membrane systems and non-deterministic Turing machines while solving decision problems. First, while a non-deterministic Turing machine needs at least one branch of computation to give an affirmative answer for accepting the instance, a recognizer membrane system (with the corresponding input encoded as a multiset) needs that all the computations return the same result, resulting in confluent systems. Second, Turing machines consist on an infinite tape, while all the elements of a family of recognizer membrane systems are restricted to be finite. Still, the number of elements in such a family is (usually) infinite, since there can be an infinite number of instances for a given decision problem. In[28–31], a new methodology for solving decision problems or demonstrating the non-solvability of a problem by means of a single membrane system is presented. On the one hand, a solution to the PARITY problem is given by means of a single membrane transition P system using dissolution rules and only two objects in the left-hand side of evolution rules. On the other hand, it is demonstrated that the ONLY-ONE-OBJECT problem cannot be solved by means of a single P system with active membranes without polarizations and without dissolution rules. It is easy to see that this problem belongs to P (in fact, it can be solved in constant time by a deterministic Turing machine), showing the low power of such systems when the resources used for the encoding are diminished. In this work, different ingredients such as dissolution and polarizations are used to solve the ONLY-ONE-OBJECT problem. In this sense, classical ingredients for reaching the presumed efficiency of systems are shown to incorporate computational power to them. The rest of the work is structured as follows. In the following section, we present some preliminaries about formal languages, set theory and decision problems. Section3 is devoted to introduce P systems with active membranes without division rules and we recall the definition of recognizer P systems. In Sect.4, we recall the definition of the complexity classes concerning single recognizer membrane systems solving problems. Next sections introduce solutions to the ONLY-ONE-OBJECT problem using dissolution rules and polarizations, respectively. We finish the paper with some conclusions and some interesting research lines open in this area. 2 Preliminaries In this section, we introduce some basic concepts for a better understanding of the rest of the paper. For deeper questions concerning formal languages and membrane systems, we refer the reader to[32, 33]. 2.1 Formal languages An alphabet Γ is a non-empty set and its elements are called symbols. A string u over Γ is an ordered finite sequence of symbols, that is, a mapping from a natural number n∈ℕ onto Γ . The number n is called the length of the string u and 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 Γ∗ . 2.2 Set theory A multiset over an alphabet Γ is an ordered pair (Γ,f) where f is a mapping from Γ onto the set of natural numbers ℕ . 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. Let m1= (Γ,f1) , m2= (Γ,f2) be multisets over Γ , then the union of m1 and m2 , denoted by m1+m2 , is the multiset (Γ,g) , where g(x)=f1(x)+f2(x) for each x∈Γ . We denote by M(Γ) the set of all multisets over Γ . 103A solution totheonlyone object problem withdissolution rules 2.3 Decision problems A decision problem X is an ordered triad X= (ΣX,IX,𝜃X) such that ΣX is the alphabet of the problem, IX is a set over Σ∗ X of instances of the problem, and 𝜃X is a function from IX onto {0, 1} , that represents the acceptance or the rejection of an instance. The ONLY-ONE-OBJECT problem is a decision problem (ΣOOO,IOOO,𝜃OOO) such that ΣOOO ={a} , IOOO ={a , aa , aaa , …} and 𝜃OOO(u)=1 if and only if u=a , being 0 for any other instance u∈IOOO . 3 P systems withactive membranes First presented in[1], a P system is a computational model inspired by a biological cell. Definition 1 A P system with active membranes without division rules of degree q ≥ 1 is a tuple where: • Γ is a finite (working) alphabet whose elements are called objects. • H is a finite alphabet such that H∩Γ=� whose elements are called labels. • q ≥ 1 is the degree of the system. • 𝜇 is a labelled rooted tree (called membrane structure) consisting of q nodes bijectively labelled by elements of H( the root of 𝜇 is labelled by r𝜇) . • M 1 ,…,Mq are multisets over Γ . • R is a finite set of rules, of the following forms: (a) [a → u]𝛼 h , where h∈H , 𝛼∈{0, +,−} , a∈Γ , u∈M(Γ) , (object evolution rules). (b) a [] 𝛼 h →[b] 𝛽h , where h∈H⧵{r𝜇} , 𝛼,𝛽∈{0, +,−} , a,b∈Γ (send-in communication rules). (c) [a]𝛼 h→ b[]𝛽h , where h∈H , 𝛼,𝛽∈{0, +,−} , a,b∈Γ (send-out communication rules). (d) [a]𝛼 h → b , where h∈H⧵{iout,r𝜇} , 𝛼∈{0, +,−} , a,b∈Γ (dissolution rules). • iout ∈H∪{env} . Π=(Γ ,H,𝜇, M1 , … , Mq , R ,i out) A P system with active membranes can be viewed as a set of q membranes, labelled by elements of H, arranged in a hierarchical structure 𝜇 given by a rooted tree (called membrane structure) whose root is called the skin membrane, such that: (a) M 1 ,…,Mq represent the finite multisets of objects initially placed in the q membranes of the system; (b) R is a finite set of rules over Γ associated with the labels; and (c) iout ∈ H ∪{ env } indicates the output region. We use the term region i to refer to membrane i in the case i∈H and to refer to the “environment” of the system in the case i=env . A membrane that does not have internal membranes (i.e. it is a leaf of the tree structure 𝜇 ) is called an elementary membrane. Otherwise, it is considered a non-elementary membrane. The membrane that surrounds the whole system is called skin membrane. A membrane has an associated polarization that can change through time by the application of rules. In the initial moment, the polarization of all the membranes is neutral or 0. An instantaneous description or a configuration Ct at an instant t of a P system with active membranes is described by the following elements: (a) the membrane structure at instant t, with the corresponding polarizations associated with each membrane, (b) all multisets of objects over Γ associated with all the membranes present in the system at that moment, and (c) the contents of the environment at that certain moment. The initial configuration of Π is described as C0=( 𝜇, M1 , … , Mq ; �) . We denote the contents of the region h in the moment t as Ct(h) . An object evolution rule [a → u]𝛼 h for h∈H , 𝛼∈{0, +,−} , a∈Γ , u∈M(Γ) is applicable to a configuration Ct at an instant t, if there exists a membrane labelled by h with polarization 𝛼 in Ct which contains object a. When applying such a rule, object a is consumed and objects from multiset u are produced in that membrane. A send-in communication rule a [] 𝛼 h →[b] 𝛽 h for h∈H⧵{r𝜇} , 𝛼,𝛽∈{0, +,−} , a,b∈Γ is applicable to a configuration Ct at an instant t, if there exists a membrane labelled by h with polarization 𝛼 in Ct such that h is not the label of the root of 𝜇 and its parent membrane contains object a. When applying such a rule, object a is consumed from the parent membrane and object b is produced in the corresponding membrane h, and it changes the polarization of such a membrane h to 𝛽 . A send-out communication rule [ a]𝛼 h →b [] 𝛽 h for h∈H , 𝛼,𝛽∈{0, +,−} , a,b∈Γ is applicable to a configuration Ct at an instant t, if there exists a membrane labelled by h with polarization 𝛼 in Ct such that it contains object a. When applying such a rule, object a is consumed from such membrane h and object b is produced in the parent Π=(Γ,H,𝜇,M 1 ,…,Mq,R,iout) 104 J.Caselmann, D.Orellana-Martín of such membrane, and it changes the polarization of such a membrane h to 𝛽 . A dissolution rule [a]𝛼 h → b for h∈H⧵{iout,r𝜇} , 𝛼∈{0, +,−} , a,b∈Γ is applicable to a configuration Ct at an instant t, if there exists a membrane labelled by h with polarization 𝛼 in Ct , different from the skin membrane and the output region, such that it contains object a. When applying such a rule, object a is consumed, membrane h is dissolved and its objects are sent to the parent (or the first ancestor that has not been dissolved). A computational step is made by the application of the aforementioned rules in the following way: • One object can fire only one rule; • Object evolution rules can fire in a maximal parallel way; that is, all the evolution rules that can be fired will be fired; • In each membrane, only one rule of the types (b), (c) or (d) can be fired in each computational step; • A computational step is divided in two microsteps: First, all the transformations of objects are made, and second, membranes that must be dissolved will be dissolved. If an object can fire more than one rule, then one of them will be selected in a non-deterministic way. Ct leads to Ct+1 if the latter can be obtained from the former by applying the rules in the previously explained way, and it is denoted by Ct ⇒ ΠCt+1 . A computation of the system is a sequence of configurations C=(C0,…,Cn) , where C0 is the initial configuration of the membrane system, and for each Ct , t ≥ 1 , Ct−1 ⇒ ΠCt . We say that the computation is finite if n∈ℕ . In[34, 35], a special type of membrane systems is introduced in order to solve decision problems, the wellknown recognizer membrane systems. A recognizer membrane system is a membrane system from any class of P systems (e.g., cell P systems, tissue P systems and so on) that has special requirements. Definition 2 A recognizer P system with active membranes without division rules of degree q≥1 is a tuple where: • Π=(Γ,H,𝜇,M 1 ,…,Mq,R,iout) is a P system with active membranes without division rules of degree q ≥ 1 where: – Γ has two special symbols, 𝚢𝚎𝚜 and 𝚗𝚘. – M 1 ,…,Mq are multisets over Γ⧵Σ . – iout =env is the environment of the system. (Π,Σ,iin) • Σ⊊Γ . • iin ∈H is the input membrane. Let m∈M(Σ) . We denote by Π+m the membrane system Π with input m; that is, the membrane system Π where the multiset m is introduced in the initial configuration in the input membrane iin . Then, the initial configuration of Π+m is C 0 =(𝜇,M 1 ,…,Miin +m,…,Mq;�) . We recall the concept of solvability of decision problems by means of recognizer membrane systems: Definition 3 Let X= (ΣX,IX,𝜃X) be a decision problem, and let cod ∶IX → M(Σ) be a function that transforms an instance of X to a multiset over Σ , that will be the input of Π . We say that Π solves an instance u∈IX of the decision problem X if: • The system Π+cod(u) sends only one object 𝚢𝚎𝚜 or one object 𝚗𝚘 , but not both, to the environment, and only in the last step of the computation; and • The system Π+cod(u) is confluent; that is, all the computations halt and return the same result. The class of recognizer P systems with active membranes is denoted by AM , and when division rules are not allowed, the notation NAM is used. We will use NAM0 to denote the class of recognizer polarizationless P systems with active membranes without division rules, where the polarizations are removed or, equivalently, only one polarization is used. We use NAM(+d) and NAM(−d) (respectively, NAM0(+d) and NAM0(−d) ) for recognizer P systems (resp., recognizer polarizationless P systems) without division rules where dissolution rules are allowed ( +d ) or forbidden ( −d ). 4 The complexity classes PMC1p R and PMC1f R We recall the definition of various computational complexity classes in the framework of membrane computing from [28, 31]. Definition 4 Let R be a class of recognizer membrane systems. Let X= (ΣX,IX,𝜃X) be a decision problem such that IX is a language over the finite alphabet ΣX . We say that problem X is solvable in polynomial time by a single membrane system Π from R with precomputed resources (respectively, free of external resources), denoted by X∈ PMC1p R (resp., PMC1f R ), if the following hold: 105A solution totheonlyone object problem withdissolution rules • The encoding of the input of the system of Π is provided by a “reasonable” encoding scheme given by a function cod (resp., the input alphabet is ΣX ). • The system Π is polynomially bounded, sound and complete with regard to X The term free of resources means that the input is directly introduced as a multiset from the instance, without “being encoded”. From these asserts, it is trivial to see that PMC1f R ⊆ PMC1p R ⊆ PMCR . In[28, 31], it was demonstrated that some problems cannot be solved while not providing precomputed resources, using the dependency graph technique in a very innovative way, and some solutions to problems below P when some ingredients are used. 5 Proposed solution fortheONLY-ONE-OBJECT problem using dissolution rules As demonstrated in[28, 31], the ONLY-ONE-OBJECT problem cannot be solved with a P system Π∈ NAM 0(−d) . However, if we allow the use of dissolution rules, the problem is solvable. Let Π be a recognizer P system of degree 3 such that such that 1. Γ=Σ ∪ {𝛽,𝛽�,𝛽��,𝛽���, #, 𝚢𝚎𝚜,𝚗𝚘} , 2. Σ={a} , 3. 𝜇=[[[ ] 3]2]1 , 4. M1=M3=� , M2={𝛽} , 5.  ={[ a]3→#, [𝛽→𝛽′]2,[𝛽′→𝛽′′ ]2,[𝛽′′ ]2→𝛽′′′,[a]2→#, [𝛽′′ ]2 →𝚗𝚘 [] 2, [𝛽′′′ ]→𝚢𝚎𝚜 [] 2 } , and 6. iin =3, iout =env . A graphical depiction of this system can be seen in Fig.1. The system takes a multiset {an},n∈ℕ+ as input in membrane 3 and outputs the answer to the problem ( 𝚢𝚎𝚜 or 𝚗𝚘 ) into the system’s environment. The system uses three dissolution rules: one in membrane 3 and two in membrane 2, two of these only activate themselves if there is an a present in the membrane. In the case n=1 , only membrane 3 will be dissolved by those rules, in the other case ( n>1 ), the membranes 3 and 2 are dissolved. Making use of the auxiliary element 𝛽 , we can now “count” the number of necessary computation steps to reach membrane 1. If there is more than one a, membranes 3 and 2 will be dissolved Π=(Γ,Σ,𝜇,M1,M2,M3,R,iin,iout ) in two computation steps, so the auxiliary element 𝛽′′ will be in membrane 1 and the system will output 𝚗𝚘 . On the other hand, if there is only one a, membrane 2 won’t be dissolved using the dissolution rule [a]2 → # , but using this one instead: [ 𝛽 ���]2 → # . So, if there is only one a, we can increment the auxiliary element 𝛽 until it reaches 𝛽′′′ . In the final step, if there is a 𝛽′′′ in membrane 1, we output 𝚢𝚎𝚜 . It is impossible by design that are a 𝛽′′ and a 𝛽′′′ at the same time in membrane 1, which means that the system will always output the same and the correct answer. Theorem1 𝙾𝙽𝙻𝚈 −𝙾𝙽𝙴 −𝙾𝙱𝙹𝙴𝙲𝚃 ∈PMC 1f NAM0 (+d) . Proof The system Π uses an input free of external resources. The number of resources is polynomial (more precisely, constant), and the number of steps for the computation is bounded by a constant number of steps (exactly 3 for an affirmative answer and 4 for a negative answer). ◻ Corollary 2 PMC1f NAM0 (−d) ⊊PMC 1f NAM0 (+d) . Proof It is enough to see that the ONLY-ONE-OBJECTcan be solved by a recognizer P system from NAM0(+d) but it cannot be solved by any P system from NAM0(−d) . ◻ 6 Proposed solution fortheONLY-ONE-OBJECT problem using polarizations In this section, we design a recognizer P system without division rules and without dissolution rules that solves the ONLY-ONE-OBJECT problem. Let Π be a recognizer P system of degree 2 such that Fig. 1 P system Π∈ NAM 0(+ d ) solving ONLY-ONE-OBJECT 106 J.Caselmann, D.Orellana-Martín such that 1. Γ=Σ ∪ {𝛽 , 𝛽� , 𝛽�� , #, 𝚢𝚎𝚜 , 𝚗𝚘} , 2. Σ={a} , 3. 𝜇=[ ] 1 , 4. M1={𝛽} , 5.  ={[a]1→ # [] + 1 , [a] + 1→ # [] − 1 , [𝛽→𝛽 ′ ]1 , [𝛽 ′ →𝛽 ′′ ] + 1 , [𝛽 ′′ ] + 1 →𝚢𝚎𝚜 [] − 1, [𝛽′′ ]− 1 →𝚗𝚘 [] − 1 } , and 6. iin =1, iout =env . A graphical depiction of this system can be seen in Fig.2. The system takes a multiset {an},n∈ ℕ + as input in membrane 1 and outputs the answer to the problem ( 𝚢𝚎𝚜 or 𝚗𝚘 ) into the system’s environment. The system works as follows: On the one hand, in the membrane labelled by 1 at least one object a exists, and it will be sent out changing the polarization to positive. In the second computational step, two different things can happen: If n=1 , then no more objects a will be present at this moment and the polarization will not change in this computational step; otherwise, another object a will change the polarization of the membrane 1 by the application of the rule [ a ]+ 1 →# [] − 1 . At the same time, object 𝛽 evolves into 𝛽′′ in two computational steps. In the following step, object 𝛽′′ will be sent to the environment as an object yes or an object no, depending on the polarization of such membrane being positive or negative, respectively. It is important to point out that the polarization of that membrane must not be taken back to neutral, since if more objects a are present, they could start the process again, and the system would not work correctly. The last two steps are devoted to send the object yes or the object no out to the environment. Theorem3 𝙾𝙽𝙻𝚈 −𝙾𝙽𝙴 −𝙾𝙱𝙹𝙴𝙲𝚃 ∈PMC 1f NAM (−d). Proof The system Π uses an input free of external resources. The number of resources is polynomial (more precisely, Π=(Γ,Σ,𝜇,M1,R,iin,iout ) constant), and the number of steps for the computation is bounded by a constant number of steps (exactly 3 computational steps for either affirmative or negative answers). ◻ Corollary 4 PMC1f NAM0 (−d) ⊊PMC 1f NAM(−d) . Proof It is enough to see that the ONLY-ONE-OBJECT problem can be solved by a recognizer P system from NAM(−d) but it cannot be solved by any P system from NAM0(−d) . ◻ 7 Conclusions In previous works, it has been shown that cooperation between objects, dissolution rules or polarizations are efficiency frontiers[36, 37] while allowing division rules. It is interesting to see that, when the precomputed resources are restricted, they are also a frontier in terms of what problems below P can be solved efficiently (or even solved). It would be interesting to look for more of these classical ingredients used for passing the presumed efficiency frontier that can be used for solving problems while the precomputed resources are restricted too. As introduced before, the dependency-graph technique has been used to demonstrate the unsolvability of problems by means of single membrane systems of some classes. We are planning on demonstrating the non-efficiency of other classes using this technique, and also to investigate new ways to demonstrate the unsolvability of new problems. Acknowledgements We would like to thank the suggestions given by the reviewers of the paper, that helped the paper to improve to the final state. Author contributions All authors were present in the whole preparation, research and writing of the manuscript. Funding Funding for open access publishing: Universidad de Sevilla/ CBUA. Availability of data and material No datasets were generated or analysed during the current study. Declarations Conflict of interest The authors declare no Conflict of interest. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in Fig. 2 P system Π∈NAM(− d ) solving ONLY-ONE-OBJECT 107A solution totheonlyone object problem withdissolution rules the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References 1. Păun, Gh. (2000). Computing with membranes. Journal of Computer and System Sciences, 61(1), 108–143. https:// doi. org/ 10. 1006/ jcss. 1999. 1693 2. Ionescu, M., Păun, Gh., & Yokomori, T. (2006). Spiking neural P systems. Fundamenta Informaticae 71(2-3), 279–308. 3. Peng, H., Bao, T., Luo, X., Wang, J., Song, X., Riscos-Núñez, A., & Pérez-Jiménez, M.J. (2020). Dendrite P systems. Neural Networks 127, 110–120 https:// doi. org/ 10. 1016/j. neunet. 2020. 04. 014. 4. Aman, B. (2023). Solving SAT with P systems with anti-mem- branes. Journal of Membrane Computing, 5(2), 100–107. 5. Alhazov, A., Aman, B., Freund, R., & Ivanov, S. (2017). Simulating R systems by P systems. In A. Leporati, G. Rozenberg, A. Salomaa, & C. Zandron (Eds.), Membrane computing (pp. 51–66). Springer. 6. Frisco, P., Gheorghe, M., & Pérez-Jiménez, M. J. (2014). Applications of membrane computing in systems and synthetic biology. Springer. 7. Duan, Y., Rong, H., Zhang, G., Gorbachev, S., Qi, D., Valencia- Cabrera, L., & Pérez-Jiménez, M. J. (2024). A review of computing models for studying population dynamics of giant panda ecosystems. Ecological Modelling, 487, 110543. 8. Duan, Y., Rong, H., Zhang, G., Qi, D., Valencia-Cabrera, L., & Pérez-Jiménez, M. J. (2023). Estimation of minimum viable population for giant panda ecosystems with membrane computing models. Natural Computing, 22(1), 69–93. 9. Zhang, G., Zhang, X., Rong, H., Paul, P., Zhu, M., Neri, F., & Ong, Y.-S. (2022). A layered spiking neural system for classification problems. International Journal of Neural Systems, 32(08), 2250023. 10. Zhang, G., Rong, H., Paul, P., He, Y., Neri, F., & Pérez-Jimé- nez, M. J. (2021). A complete arithmetic calculator constructed from spiking neural P systems and its application to information fusion. International Journal of Neural Systems, 31(01), 2050055. 11. Buiu, C., & Florea, A. G. (2019). Membrane computing models and robot controller design, current results and challenges. Journal of Membrane Computing, 1(4), 262–269. 12. Liu, X., Rong, H., Neri, F., Yu, Z., & Zhang, G. (2024). Entropy-weighted numerical gradient optimization spiking neural system for biped robot control. International Journal of Neural Systems. https:// doi. org/ 10. 1142/ S0129 06572 45003 08 13. Liu, X., Zhang, G., Mastoi, M. S., Neri, F., & Pu, Y. (2023). A human-simulated fuzzy membrane approach for the joint controller of walking biped robots. Integrated Computer-Aided Engineering, 30(2), 105–120. 14. Zhang, L., Xu, F., Xiao, D., Dong, J., Zhang, G., & Neri, F. (2022). Enzymatic numerical spiking neural membrane systems and their application in designing membrane controllers. International Journal of Neural Systems, 32(11), 2250055. 15. Liu, Y., Chen, Y., Paul, P., Fan, S., Ma, X., & Zhang, G. (2021). A review of power system fault diagnosis with spiking neural P systems. Applied Sciences. https:// doi. org/ 10. 3390/ app11 104376 16. Zhang, G., Pérez-Jiménez, M. J., & Gheorghe, M. (2017). Reallife applications with membrane computing (Vol. 25). Springer. 17. Pérez-Hurtado, I., Orellana-Martín, D., Martínez-del-Amor, M. A., Valencia-Cabrera, L., & Nez, A.R.-N. (2022). A new P-Lingua toolkit for agile development in membrane computing. Information Sciences, 587, 1–22. https:// doi. org/ 10. 1016/j. ins. 2021. 12. 003 18. Shang, Z., Wei, Z., Verlan, S., Li, J., & He, Z. (2023). An FPGA architecture for the RRT algorithm based on membrane computing. Electronics. https:// doi. org/ 10. 3390/ elect ronic s1212 2741 19. Zhang, G., Shang, Z., Verlan, S., Martínez-Del-Amor, M. Á., Yuan, C., Valencia-Cabrera, L., & Pérez-Jiménez, M. J. (2020). An overview of hardware implementation of membrane computing models. ACM Computing Surveys (CSUR), 53(4), 1–38. 20. Zhang, G., Pérez-Jiménez, M. J., Riscos-Núñez, A., Verlan, S., Konur, S., Hinze, T., & Gheorghe, M. (2021). Membrane computing models: Implementations (Vol. 10). Springer. 21. Rong, H., Duan, Y., & Zhang, G. (2022). A bibliometric analysis of membrane computing (1998–2019). Journal of Membrane Computing, 4(2), 177–207. 22. Păun, Gh. (2001). P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages, and Combinatorics, 6(1), 75–90. 23. Song, B., Li, K., Orellana-Martín, D., Pérez-Jiménez, M. J., & Pérez-Hurtado, I. (2021). A survey of nature-inspired computing: Membrane computing. ACM Computing Survey. https:// doi. org/ 10. 1145/ 34312 34 24. Mauri, G., Leporati, A., Manzoni, L., Porreca, A. E., & Zandron, C. (2015). Complexity classes for membrane systems: A survey. In A.-H. Dediu, E. Formenti, C. Martín-Vide, & B. Truthe (Eds.), Language and automata theory and applications (pp. 56–69). Springer. 25. Martín-Vide, C., Pă, Gh., Pazos, J., & Rodríguez-Patón, A. (2003) . Tissue P systems. Theoretical Computer Science 296(2), 295–326 https:// doi. org/ 10. 1016/ S0304- 3975(02) 00659-X. (Machines, Computations and Universality). 26. Buño, K., & Adorna, H. (2023). Solving 3-SAT in distributed P systems with string objects. Theoretical Computer Science, 964, 113976. https:// doi. org/ 10. 1016/j. tcs. 2023. 113976 27. Murphy, N., & Woods, D. (2008). A characterisation of NL using membrane systems without charges and dissolution. In C. S. Calude, J. F. Costa, R. Freund, M. Oswald, & G. Rozenberg (Eds.), Unconventional computing (pp. 164–176). Springer. 28. Orellana-Martín, D., Valencia-Cabrera, L., Riscos-Núñez, A., & Pérez-Jiménez, M.J. (2019). A new perspective on computational complexity theory in membrane computing. In: BWMC2019: 17th brainstorming week on membrane computing, pp. 117–126. 29. Orellana-Martín, D., Valencia-Cabrera, L., Riscos-Núñez, A., & Pérez-Jiménez, M.J. (2019). An apparently innocent problem in membrane computing. In: BWMC2019: 17th brainstorming week on membrane computing) (pp. 127–138). IMCS: International Membrane Computing Society. 30. Valencia-Cabrera, L., Orellana-Martín, D., Pérez-Hurtado, I., & Pérez-Jiménez, M.J. (2019). New applications for an old tool. In: BWMC2019: 17th brainstorming week on membrane computing (pp. 165–170). 31. Valencia-Cabrera, L., Orellana-Martín, D., Pérez-Hurtado, I., & Pérez-Jiménez, M.J. (2019). Dependency graph technique revisited. In: CMC20: 20th international conference on membrane computing (2019) (pp. 513–522). IMCS: International Membrane Computing Society. 32. Rozenberg, G., & Salomaa, A. (eds). (1997). Handbook of formal languages. 3 Vols. Springer 33. Păun, Gh., Rozenberg, G., & Salomaa, A. (2010). The Oxford handbook of membrane computing. Oxford University Press Inc. 34. Pérez-Jiménez, M., Romero-Jiménez, A., & Sancho-Capar- rini, F. (2003). Complexity classes in cellular computing with 108 J.Caselmann, D.Orellana-Martín membranes. Natural Computing, 2, 265–285. https:// doi. org/ 10. 1023/A: 10254 49224 520 35. Pérez-Jiménez, M. J., Romero-Jiménez, A., & Sancho-Capar- rini, F. (2003). Decision P systems and the P ≠ NP conjecture. In G. Păun, G. Rozenberg, A. Salomaa, & C. Zandron (Eds.), Membrane computing (pp. 388–399). Springer. 36. Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A., & Romero-Campero, F. J. (2006). On the power of dissolution in P systems with active membranes. In R. Freund, Gh. Păun, G. Rozenberg, & A. Salomaa (Eds.), Membrane Computing (pp. 224–240). Springer. 37. Valencia-Cabrera, L., Orellana-Martín, D., Martínez-del-Amor, M. A., Nez, A.R.-N., & Pérez-Jiménez, M. J. (2017). Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation. Theoretical Computer Science, 701, 226–234. https:// doi. org/ 10. 1016/j. tcs. 2017. 04. 015. (At the intersection of computer science with biology, chemistry and physics - In Memory of Solomon Marcus). Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Julien Caselmann received his B.Sc. degree in Mathematics in 2020 at TU Munich and is currently writing his Master’s Thesis to obtain his M.Sc. degree in Computer Science at Humboldt- University zu Berlin. His main research interests are process and workflow automation, human– computer interaction and software verification. David Orellana‑Martín received his B.Sc. degree in 2014, his M.Sc. degree in 2016, and his Ph.D. degree in 2019 at the University of Seville. He received the Best Ph.D. thesis of 2019 Award from the International Membrane Computing Society. He was an ERCIM fellow at NTNU (Norway) from 2019 to 2021, a postdoctoral fellow at the University of Seville from 2021 to 2023, and currently, he is an assistant professor at the University of Seville. His main research interests are computational complexity theory, unconventional computing (especially membrane computing), and machine learning and high-performance computing. He is a member of the Website Committee of the International Membrane Computing Society.