14th Brainstorming Week on Membrane Computing Sevilla, February 1 - 5, 2016 : RGNC Report 1/2016

14th Brainstorming Week on Membrane Computing Sevilla, February 1 – 5, 2016 Carmen Graciani David Orellana-Mart´ın Agust´ın Riscos-N´u˜nez ´ Alvaro Romero-Jim´enez Luis Valencia-Cabrera Editors 14th Brainstorming Week on Membrane Computing Sevilla, February 1 – 5, 2016 Carmen Graciani David Orellana-Mart´ın Agust´ın Riscos-N´u˜nez ´ Alvaro Romero-Jim´enez Luis Valencia-Cabrera Editors RGNC REPORT 1/2016 Research Group on Natural Computing Universidad de Sevilla F´enix Editora, Sevilla, 2016 c Autores ISBN: ?????? Dep´osito Legal: SE-????–06 Edita: F´enix Editora Avda. de C´adiz, 7 – 1C 41004 Sevilla [email protected] Telf. 954 41 29 91 Preface The 14th Brainstorming Week on Membrane Computing (BWMC) was held in Sevilla, from February 1 to February 5, 2016, in the organization of the Research Group on Natural Computing (RGNC) from the Department of Computer Science and Artificial Intelligence of Universidad de Sevilla. The first edition of BWMC was organized at the beginning of February 2003 in Rovira i Virgili University, Tarragona, and all the next editions took place in Sevilla at the beginning of February, each year. In the style of previous meetings in this series, the 14th edition of BWMC was conceived as a period of active interaction among the participants, with the emphasis on exchanging ideas and cooperation. Several “provocative” talks were delivered, mainly devoted to open problems, research topics, conjectures waiting for proofs, followed by an intense cooperation among the 40 participants – see the list in the end of this preface. The efficiency of this type of meetings was again proved to be very high and the present volume illustrates this assertion. The 2016 edition of the Brainstorming enjoyed a special visit from a group of undergraduate Physics students, under the initiative of Prof. Ricardo Graciani- D´ıaz, from the University of Barcelona. Their presence and interest was a powerful catalyst for many interactions, which have given rise to a couple of papers in this volume. In addition, each student wrote a short note on his/her experience. The papers included in this volume, arranged in the alphabetic order of the authors, were collected in the form available at a short time after the brainstorming; several of them are still under elaboration. The idea is that the proceedings are a working instrument, part of the interaction started during the stay of authors in Sevilla, meant to make possible a further cooperation, this time having a written support. A selection of papers from this volume will be considered for publication in special issues of Theoretical Computer Science, which will also contain a selection of papers from ACMC 2016 (the Asian Conference on Membrane Computing, to be held at Universiti Kebangsaan, in November 14th-16th). vi Preface After each BWMC, one or two special issues of various international journals were published. Here is their list: •BWMC 2003: Natural Computing – volume 2, number 3, 2003, and New Generation Computing – volume 22, number 4, 2004; •BWMC 2004: Journal of Universal Computer Science – volume 10, number 5, 2004, and Soft Computing – volume 9, number 5, 2005; •BWMC 2005: International Journal of Foundations of Computer Science – volume 17, number 1, 2006); •BWMC 2006: Theoretical Computer Science – volume 372, numbers 2-3, 2007; •BWMC 2007: International Journal of Unconventional Computing – volume 5, number 5, 2009; •BWMC 2008: Fundamenta Informaticae – volume 87, number 1, 2008; •BWMC 2009: International Journal of Computers, Control and Communication – volume 4, number 3, 2009; •BWMC 2010: Romanian Journal of Information Science and Technology – volume 13, number 2, 2010; •BWMC 2011: International Journal of Natural Computing Research – volume 2, numbers 2-3, 2011; •BWMC 2012: International Journal of Computer Mathematics – volume 99, number 4, 2013; •BWMC 2013: Romanian Journal of Information Science and Technology, vol. 17, nr. 1, 2014; •BWMC 2014: Fundamenta Informaticae, volume 134, numbers 1-2, 2014; •BWMC 2015: Natural Computing – 2016. Other papers elaborated during the fourteenth BWMC will be submitted to other journals or to suitable conferences. The reader interested in the final version of these papers is advised to check the current bibliography of membrane computing available in the domain website http://ppage.psystems.eu. *** The list of participants as well as their email addresses are given below, with the aim of facilitating the further communication and interaction: 1. Mar´ıa Arazo-S´anchez, University of Barcelona (Spain) [email protected] 2. Fernando Arroyo-Montoro, Universidad Polit´ecnica de Madrid (Spain) [email protected] 3. Marc Barroso-Mancha, University of Barcelona (Spain) [email protected] 4. Diego R. Cabrera-Mendieta, Univ. Polit´ecnica Salesiana (Ecuador) [email protected] 5. Juan B. Castellanos-Pe˜nuelas, Universidad Polit´ecnica de Madrid (Spain) [email protected] Preface vii 6. Rodica Ceterchi, University of Bucharest (Romania) [email protected] 7. Erzs´ebet Csuhaj-Varj´u, E¨otv¨os Lor´and University (Hungary) [email protected] 8. Rudolf Freund, TU Wien (Austria) [email protected] 9. Zsolt Gazdag, E¨otv¨os Lor´and University (Hungary) [email protected] 10. Marian Gheorghe, University of Bradford (UK) [email protected] 11. Carmen Graciani, Universidad de Sevilla (Spain) [email protected] 12. Ricardo Graciani-D´ıaz, University of Barcelona (Spain) [email protected] 13. Jos´e Luis Guisado-Lizar, Universidad de Sevilla (Spain) [email protected] 14. Miguel ´ Angel Guti´errez-Naranjo, Universidad de Sevilla (Spain) [email protected] 15. Sergiu Ivanov, Universit´e Paris Est (France) [email protected] 16. Krist´of K´antor, University of Debrecen (Hungary) [email protected] 17. G´abor Kolonits, E¨otv¨os Lor´and University (Hungary) [email protected] 18. Alberto Leporati, Universit`a degli Studi di Milano-Bicocca (Italy) [email protected] 19. Luis Felipe Mac´ıas-Ramos, Universidad de Sevilla (Spain) [email protected] 20. Luca Manzoni, Universit`a degli Studi di Milano-Bicocca (Italy) [email protected] 21. Giancarlo Mauri, Universit`a degli Studi di Milano-Bicocca (Italy) [email protected] 22. V´ıctor M´endez-Mu˜noz, Autonomous University of Barcelona (Spain) [email protected] 23. Alejandro Mill´an-Calder´on, Universidad de Sevilla (Spain) [email protected] 24. Laura Moreno-Valero, University of Barcelona (Spain) [email protected] 25. David Orellana-Mart´ın, Universidad de Sevilla (Spain) [email protected] 26. Gheorghe P˘aun, Universidad de Sevilla (Spain) and Institute of Mathematics of the Romanian Academy (Romania) [email protected] viii Preface 27. Mario de Jes´us P´erez-Jim´enez, Universidad de Sevilla (Spain) [email protected] 28. Antonio E. Porreca, Universit`a degli Studi di Milano-Bicocca (Italy) [email protected] 29. Ariadna Ribes-Metidieri, University of Barcelona (Spain) [email protected] 30. Patricia Ribes-Metidieri,University of Barcelona (Spain) [email protected] 31. Agust´ın Riscos-N´u˜nez, Universidad de Sevilla (Spain) [email protected] 32. G´abor Rom´an, E¨otv¨os Lor´and University (Hungary) [email protected] 33. ´ Alvaro Romero-Jim´enez, Universidad de Sevilla (Spain) [email protected] 34. Jos´e Mar´ıa Sempere-Luna, Polytechnic University of Valencia (Spain) [email protected] 35. Petr Sos´ık, University of Opava (Czech Republic) [email protected] 36. ´ Oscar de la Torre P´erez, University of Barcelona (Spain) [email protected] 37. Luis Valencia-Cabrera, Universidad de Sevilla (Spain) [email protected] 38. Gy¨orgy Vaszil, University of Debrecen (Hungary) [email protected] 39. Ana Ventura-Barroso, University of Barcelona (Spain) [email protected] 40. Juli´an Viejo-Cort´es, Universidad de Sevilla (Spain) [email protected] As mentioned above, the meeting was organized by the Research Group on Natural Computing from Universidad de Sevilla (http://www.gcn.us.es)– and all the members of this group were enthusiastically involved in this (not always easy) work. We acknowledge the support obtained from the Department of Computer Science and Artificial Intelligence, as well as from “Vicerrectorado de Investigaci´on” (V Plan Propio de Investigaci´on), both of them from Universidad de Sevilla. Mario J. P´erez-Jim´enez Agust´ın Riscos-N´u˜nez (August 2016) Contents Complexity of simulating R systems by P systems A. Alhazov, B. Aman, R. Freund, S. Ivanov .............................. 1 Purely catalytic P systems over integers and their generative power A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron ............................................................. 15 Semilinear sets, register machines, and integer vector addition (P) systems A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron ............................................................. 27 Extended SNP systems with states A. Alhazov, R. Freund, S. Ivanov ....................................... 43 Computational completeness of P systems using maximal variants of the Set derivation mode A. Alhazov, R. Freund, S. Verlan ....................................... 59 Verifying P systems with costs by using priced-time Maude B. Aman, G. Ciobanu................................................... 85 On the 14th BWMC M. Arazo ............................................................... 97 Stern-Gerlach Experiment M. Arazo, M. Barroso, O. De la Torre, L. Moreno, A. Ribes, P. Ribes, A. Ventura, D. Orellana ............................................... 101 Uranium-238 decay chain M. Arazo, M. Barroso, O. De la Torre, L. Moreno, A. Ribes, P. Ribes, A. Ventura, D. Orellana ............................................... 113 On the cellular automata P systems and chain reactions M. Barroso Mancha ................................................... 131 4 A. Alhazov, B. Aman, R. Freund, S. Ivanov 3.2 Triples of symbols We start with the simplest case - when the elements of triples describing the rules are single elements. Consider such an R system Swith alphabet Vand rules {(ai, bi, ci)|1≤i≤n}. We construct a P system Π1simulating S, where the initial configuration w1matches the initial configuration of S, and the following rules, the simulation taking only 2 steps: Π1= (O, µ = [ ]1, w1, R1) where O=V∪ {a0|a∈V}∪{di|1≤i≤n}, R1={a→a0Y1≤i≤n,ai=adi|a∈V} ∪ {di→ci|¬(bi)0, di→λ|(bi)0|1≤i≤n}∪{a0→λ|a∈V}. The simulation task here is simple for two reasons: we took the simpler model of R systems, and using promoters besides inhibitors makes it possible to remove unneeded objects easily. We also note that the number of objects and rules can be decreased by not producing a0when aparticipates in the left side of any rule, and using dmin{j|1≤j≤n, aj=b}instead of b0as promoter and inhibitor. If |V|=k, then |O|= 2k+nand |R1|= 2k+ 2n. Moreover, the optimization described in the previous paragraph decreases both |O|and |R1|by the number of symbols appearing on the left side of some rule of S. The multiplicities of symbols may grow. When the same symbol is produced simultaneously by multiple rules, the multiplicative effect happens. It is, however, fairly easy to reset the multiplicities of objects in Vto one, at a cost of one more step, 2k+ 3 additional symbols in Oand 3k+ 3 additional rules, also using an additional object I1in the initial configuration: Π2= (O, µ = [ ]1, w1, R1=Ri∪Rii ∪Riii) where O=V∪ {a0, a00, a |a∈V}∪{di|1≤i≤n},∪{I1, I2, I3} Ri={a→a0Y1≤i≤n,ai=adi|a∈V}∪{I1→I2}, Rii ={di→(ci)00|¬(bi)0, di→λ|(bi)0|1≤i≤n} ∪ {a0→λ|a∈V}∪{I2→I3Ya∈Va}, Riii ={a→a|a00 , a →λ|¬a00 , a00 →λ|a∈V}∪{I3→I1}. 3.3 Triples of sets Now the task is more complicated. While generating a set Ciinstead of symbol ciis straightforward, instead of verifying that aiis present and biis absent, rule applicability is defined as presence of all symbols from set Aiand absence of all symbols from set Bi. We recall that our task is a constant-time solution. Notice Complexity of Simulating R Systems by P Systems 5 that the rule is not applicable if and only if some symbol from Aiis absent or some symbol from Biis present. Consider such an R system Swith alphabet Vand rules {(Ai, Bi, Ci)|1≤ i≤n}. We construct a P system Π3simulating S, where the initial configuration matches the initial configuration of S, plus an additional object I1, and the following rules, the simulation taking only 3 steps: Π3= (O, µ = [ ]1, w1, R1) where O=V∪ {di|1≤i≤n}∪{I1, I2, I3}, R1={I1→d1· · · dnI2} ∪ {di→λ|¬a, di→λ|b|a∈Ai, b ∈Bi,1≤i≤n}∪{I2→I3} ∪ {di→Yc∈Ci c|I3|1≤i≤n}∪{a→λ|I3|a∈V}∪{I3→I1}. If |V|=k, then |O|=k+n+ 3 and |R1|=k+n+ 3 + P1≤i≤k(|Ai|+|Bi|). Notice also that, besides objects from V, no object ever appears in multiple copies. As for each object from V, its multiplicity represents the number of rules in S that has produced it in the last simulated step. Unlike the construction from the previous section, the multiplicative effect does not carry over to the next step of computation of S, since each object from V(except the instances in the starting configuration) is produced from some object di, produced in one copy, effectively resetting the multiplicities of the previous step. However, producing objects in V in a single copy requires additional overhead. Similarly to obtaining Π2from Π1, we can obtain Π4from Π3, at the price of one more step, 2k+1 additional symbols in Oand 3k+ 1 additional rules. We skip the details. 3.4 Using only promoters It should not be any surprise that (in the maximally parallel mode) the effect of inhibitors can be obtained by non-cooperative rules with promoters only. Informally, to verify that some object bis absent, we first check if bis present by some rule a→a0|b, and it suffices to check in the next step whether ais unchanged. The reverse, i.e. replacing promoters with inhibitors, is even easier to see, since promoting a rule by bcan be modeled by inhibiting a rule by some immediately-erased object b0, creation of which is inhibited by b. We still think it is interesting to consider the use of only promoters or only inhibitors, for two reasons. First, the reduction of promoters/inhibitors in the general case of P systems is too complicated, and second, we would like to explore how little overhead in terms of slowdown and descriptional complexity would suffice to achieve our task. First, as an exercise, we construct a P system for an R system Swith triples of symbols {(ai, bi, ci)}as rules. The initial configuration matches the initial configuration of S, plus an additional object I1. 6 A. Alhazov, B. Aman, R. Freund, S. Ivanov Π5= (O, µ = [ ]1, w1, R1) where O=V∪ {a0|a∈V}∪{di|1≤i≤n}∪{I1, I2, I3}, R1={I1→I2}∪{a→a0Y1≤i≤n,ai=adi|a∈V} ∪ {I2→I3}∪{di→λ|(bi)0|1≤i≤n}∪{a0→λ|a∈V} ∪ {I3→I1}∪{di→ci|I3,|1≤i≤n}. This construction is obtained from the first one with promoters and inhibitors, implementing the group of rules with inhibitors (contrasted with existing rules with the same objects as promoters) in the next step, promoted by “timer” I3. We also note, similarly to Π1, that the number of objects and rules can be decreased by not producing a0when aparticipates in the left side of any rule, and using dmin{j|1≤j≤n, aj=b}instead of b0as promoter. Once again, this simulation has multiplicative effect, and the multiplicities can be reset to one, at the price of one more step, 2k+ 1 additional symbols in Oand 3k+ 1 additional rules. Let us call the obtained system Π6. We omit the details, only mentioning that instead of rules a→λ|¬a00 as in Π2, we can erase these symbols in the next step by rules a→λ|I1. Now consider the general case of simulating an R system Swith alphabet V and rules {(Ai, Bi, Ci)|1≤i≤n}. The simulating P system below has the initial configuration which matches the initial configuration of S, plus additional objects I1and a0for each a∈V. Π7= (O, µ = [ ]1, w1, R1=Ri∪Rii ∪Riii) where O=V∪ {a0|a∈V}∪{di|1≤i≤n}∪{I1, I2, I3}, Ri={I1→d1· · · dnI2}∪{a0→λ|a|a∈V}, Rii ={di→λ|a0, di→λ|b|a∈Ai, b ∈Bi,1≤i≤n} ∪ {a→λ|I2, a0→λ|I2|a∈V}∪{I2→I3}, Riii ={di→Yc∈Ci c|I3|1≤i≤n}∪{I3→I1Ya∈Va0}. This construction is obtained from the second one with promoters and inhibitors, as follows. The role of objects a0is to survive for one step if and only if the corresponding object ais present, to be used as a promoter instead of inhibitor a; objects a0are recreated in the last step, for the next simulation cycle. Moreover, as now objects from Vare no longer used as inhibitors, they can be removed one step earlier. The system above needs only 3 steps to simulate a step of S, and if |V|=k, then |O|= 2k+n+ 3 and |R1|= 3 + 3k+n+P1≤i≤n(|Ai|+|Bi|). Of course, alternatively, objects a0could be created from one additional initial object, at a price of an additional step and a few extra rules, but we currently focus on constructions that are efficient in time and descriptional complexity. We again comment that, although this construction has no multiplicative effect, the number Complexity of Simulating R Systems by P Systems 7 of copies of a symbol in Vproduced in the end of the simulation equals the number of rules in Sthat have produced this symbol in the last step. Producing exactly one copy needs one more step, 2k+1 additional symbols in Oand 3k+1 additional rules. We call this system Π8and give no more details, since obtaining it from Π7 is exactly like obtaining Π6from Π5. 3.5 Using only inhibitors First, as an exercise, we construct a P system for an R system Swith triples of symbols {(ai, bi, ci)}as rules. The initial configuration matches the initial configuration of S, plus an additional object I1. Π9= (O, µ = [ ]1, w1, R1) where O=V∪ {a0|a∈V}∪{di|1≤i≤n}∪{I1, I2}, R1={I1→I2}∪{a→a0Y1≤i≤n,ai=adi|a∈V} ∪ {I2→I1}∪{di→ci|¬(bi)0|1≤i≤n} ∪ {di→λ|¬I2|1≤i≤n}∪{a0→λ|¬I2|a∈V}. This construction is obtained from the one with promoters and inhibitors, implementing the group of rules with promoters (contrasted with existing rules with the same objects as inhibitors) in the next step, inhibited by “timer” I2. Moreover, removing objects a0is delayed for one step, to make sure that the rules inhibited by them in the second step are not applied in the third step. Notice also that the simulation of a computation step of Sonly takes two steps of computation in Π; the third step of computation cleaning objects diand a0overlaps with the first step of simulation of the next step in S. However, this produces no interference, since sub-alphabets {di|1≤i≤n} ∪ {a0|a∈V}and {I1} ∪ Vare disjoint. We also note, similarly to Π1, that the number of objects and rules can be decreased by not producing a0when aparticipates in the left side of any rule, and using dmin{j|1≤j≤n, aj=b}instead of b0as promoter. The problem of multiplicative effect can be solved in the usual way, resetting multiplicities to one: produce one copy of each candidate-object, and erase the objects where the multiplicity is zero. However, with inhibitors it takes longer: one additional step to erase objects awhen the corresponding object a00 is absent, and one further step to rewrite ainto a. Π10 = (O, µ = [ ]1, w1, R1) where O=V∪ {a0, a00, a |a∈V}∪{di|1≤i≤n}∪{I1, I2, I3, I4}, R1={I1→I2}∪{a→a0Y1≤i≤n,ai=adi|a∈V} ∪ {I2→I3Ya∈Va}∪{di→(ci)00|¬(bi)0|1≤i≤n} 8 A. Alhazov, B. Aman, R. Freund, S. Ivanov ∪ {I3→I4}∪{di→λ|¬I2|1≤i≤n}∪{a0→λ|¬I2, a →λ|¬a00 |a∈V} ∪ {I4→I1}∪{a→a|¬I3, a00 →λ|¬I3|a∈V}. Hence, the total additional price for resetting the multiplicities of elements of Vto one using only inhibitors is 2 more steps, 2k+2 additional objects, and 3k+2 rules. Now consider the general case of simulating an R system Swith alphabet V and rules {(Ai, Bi, Ci)|1≤i≤n}. The simulating P system below has the initial configuration which matches the initial configuration of S, plus additional objects I1, J and b0for each b∈V. Π11 = (O, µ = [ ]1, w1, R1=Ri∪Rii ∪Riii) where O=V∪ {b0, b00 |b∈V}∪{di|1≤i≤n}∪{I1, I2, I3, J}, Ri={I1→d1· · · dnI2J}∪{b0→b00|¬b|b∈V}∪{J→λ}, Rii ={di→λ|¬a, di→λ|¬b00 |a∈Ai, b ∈Bi,1≤i≤n} ∪ {b0→λ|¬I1|b∈V}∪{I2→I3, J →λ}, Riii ={di→Yc∈Ci c|¬I2|1≤i≤n} ∪ {a→λ|¬J|a∈V}∪{b00 →λ|¬I2|b∈V}∪{I3→I1JYb∈Vb0}. This construction is obtained from the second one with promoters and inhibitors, as follows. The role of objects b0is to change into b00 if and only if the corresponding object bis present, so b00 can be used as an inhibitor instead of promoter b; objects b0are recreated in the last step, for the next simulation cycle. Moreover, to make sure the rules erasing diin the absence of aare not applied in the third step, objects acan only be removed in the third step. This is why an additional object Jis present in each of the first two steps of the simulation, inhibiting premature removal of objects a. The rule erasing Jis written both in Riand Rii only to highlight that it is applied both in the first and in the second step. The system above needs only 3 steps to simulate a step of S, and if |V|=k, then |O|= 3k+n+ 4 and |R1|= 4 + 4k+n+P1≤i≤n(|Ai|+|Bi|). Of course, alternatively, objects b0could be created from one additional initial object, at a price of an additional step and a few extra rules, but we currently focus on constructions that are efficient in time and descriptional complexity. Resetting to one the multiplicities of objects in Vcan be done exactly how Π10 was constructed from Π9. Hence, the new system Π12 will have, compared to Π11, 2 more steps, 2k+ 2 additional objects, and 3k+ 2 rules. Complexity of Simulating R Systems by P Systems 9 4 Using antimatter This section is devoted to a different control mechanism: matter-antimatter annihilation rules are used instead of promoters and/or inhibitors. The weak priority of annihilation rules over non-cooperative rules is assumed, which is the most common variant of the antimatter model. First, we notice that erasing with a promoter, say, d→λ|b, in the case the promoting object bis erased without being used anywhere else, and when the number of copies of dis bounded, can be modeled by antimatter as follows: •replace the promoting object bby anti-object d−of the promoted object, in sufficient copies to erase all possible copies of promoted object d, •add erasing rules for this anti-object d−to remove the copies of the anti-objects which did not annihilate. We now construct the P system equivalent to Π1using antimatter. Π13 = (O=V∪ {di, d− i|1≤i≤n}, µ = [ ]1, w1, R1) where R1={a→Y1≤i≤n,bi=ad− iY1≤i≤n,ai=adi|a∈V} ∪ {did− i→λ, di→ci, d− i→λ|1≤i≤n}. In each rule of the first group of R1, it is enough to produce a single copy of d− i, because at most one dimay be generated by the system in the same step, since the rule uniquely determines its left side. The simulation only takes two steps, and uses k+ 2nobjects and k+ 3nrules. This construction, too, has multiplicative effect. Resetting multiplicities to one can be done by two-step annihilation. Say, we got some number (possibly zero) of objects c00, and we only want to know whether this number is positive. Then we produce one copy of (c00)−and rewrite it to c0if it does not immediately annihilate. One step later, we produce one copy of (c0)−, and rewrite it to cif it does not immediately annihilate. As a result, cwill appear if and only if (c0)−did not annihilate, i.e., c0did not appear one step before. But this happened if and only if (c00)−was annihilated, i.e., there was at least one copy of c00 two steps before. Performing this routine to objects in Vof Π13, we obtain the following system, using an additional starting object I1: Π14 = (O, µ = [ ]1, w1, R1) where O=V∪ {a0, a00,(a0)−,(a00)−|a∈V}∪{di, d− i|1≤i≤n}∪{I1, I2, I3, I4}, R1={a→Y1≤i≤n,bi=ad− iY1≤i≤n,ai=adi|a∈V}∪{I1→I2} ∪ {did− i→λ, di→(ci)00, d− i→λ|1≤i≤n}∪{I2→I3Ya∈V(a00)−} ∪ {a00(a00)−→λ, (a00)−→a0|a∈V}∪{I3→I4} ∪ {a0(a0)−→λ, (a0)−→a|a∈V}∪{I4→I1}. 10 A. Alhazov, B. Aman, R. Freund, S. Ivanov As you can see, resetting multiplicities with antimatter has a price of two more steps, 4k+ 4 additional objects and 4k+ 4 additional rules. Now consider the general case of simulating an R system Swith alphabet V and rules {(Ai, Bi, Ci)|1≤i≤n}. The simulating P system below has the initial configuration which matches the initial configuration of S, plus additional object I1. Π15 = (O, µ = [ ]1, w1, R1=Ri∪Rii ∪Riii where O=V∪ {a0,(a0)−, a00,|a∈V}∪{di, d− i|1≤i≤n}∪{I1, I2, I3}, Ri={I1→I2d1· · · dnYa∈Va0}∪{a→(a0)−a00 |a∈V}, Rii ={a0(a0)−→λ, a0→d− i, b00 →d− i,(a0)−→λ |a∈Ai, b ∈Bi,1≤i≤n}∪{I2→I3}, Riii ={did− i→λ, di→Yc∈Ci c, d− i→λ|1≤i≤n}∪{I3→I1}. Symbols from Ciare produced from diif and only if it is not annihilated, i.e., neither a0nor b00 should produce d− ifor any a∈Ai,b∈Bi. Since a0is annihilated if and only if ais present, and b00 is not produced if and only if bis absent, the simulation of an application of rule iof the R system happens if and only if all symbols from the first set are present and all symbols from the second set are absent. The simulation takes 3 steps, using the alphabet of 4k+ 2n+ 3 symbols and the set of 3k+ 3n+3+P1≤i≤n(|Ai|+|Bi|) rules. This construction produces each symbol in multiplicity equal to the number of rules of Sthat produced it, not carrying the multiplicative effect to the next step. If needed, resetting multiplicities can be done costing two more steps, 4k+ 2 additional objects and 4k+2 additional rules. We call this system Π16, and provide no more details since it is obtained from Π15 exactly as Π14 is obtained from Π13. 5 Non-standard P systems Some difficulty of simulation of R systems by P systems lie in the difference of their standard derivation modes. We would like to discuss how varying this may affect the problem. First, if we consider P systems with sets instead of multisets, where production of a symbol multiple times still yields a single copy of the result, then all constructions in this paper still hold literally, i.e., no changes in the description of these P systems is needed. However, some things may become simpler, e.g., in this case resetting multiplicities to one is done by the model, and does not require additional time, symbol and rule complexity. We note that, in a non-distributed case, P systems with sets of objects are no longer universal, since the number of possible configuration is bounded by two to Complexity of Simulating R Systems by P Systems 11 the power of the cardinality of the alphabet. However, universality is not needed to simulate R systems (which has also been shown in the case of deterministic P systems with promoters and/or inhibitors). Second, if we consider P systems which deterministically apply all individually applicable rules, even with overlapping left sides (i.e., competing for resources), then of course the existing solutions still literally hold, but in some cases there are much easier ways: we would have no need to explicitly produce multiple objects from one. For instance, the constructions in this paper usually involve production of rule labels di, either from the corresponding reactant ai, or from some “timer” object Ij, and then have different rules processing these label objects. In this “autoreplication” mode, these various processing rules could be applied directly to the corresponding original object aior Ij, the replication being done by the model itself. This would definitely simplify the simulation. Let us refer to this aspect as auto-replication. For example, the set of rules of system Π1can be simplified to the following: {ai→ci|¬bi|1≤i≤n}∪{a→λ|a∈V}, i.e., just one step, no additional objects and kadditional rules. The problem with resetting the multiplicities is also simpler: Π= (O, µ = [ ]1, w1, R1where O=V∪ {a0|a∈V}∪{I1, I2}, R1={I1→I2}∪{ai→(ci)0|¬bi|1≤i≤n}∪{a→λ|a∈V} ∪ {I2→I1}∪{I2→c|c0}∪{c0→λ|c∈V}, i.e., requiring only one more step, k+2 additional symbols and 2k+2 additional rules (compared to increase of complexity of Π2over Π1by one step, 2k+3 symbols and by 3k+ 3 rules). Third, if we consider P systems where idle objects (i.e., those not consumed by applied rules) do not contribute to the next configuration, we call this aspect “no persistence”, then many erasing rules (in particular, all erasing promoted or inhibited by some “timer” Ij) would no longer be needed, while occasionally some renaming rules should be added when object was designed to be used later than in the next step after its production. For instance, in case of no-persistence, all n+k0 erasing rules of Π1may be removed, leaving just n+krules. Similarly, all erasing rules of Π2may be removed; hence, the subtask of resetting the multiplicities to one in this case only needs k+ 3 additional rules instead of 3k+ 3. However, testing for presence of some object bby “failing to apply a rule with inhibitor band finding the reactant unchanged in the next step” would not work. The working solution is to use bas an inhibitor in a rule producing some object b0, and to use b0as an inhibitor in the next step. Testing for absence by “failing to apply a rule with a promoter and finding the reactant unchanged in the next 12 A. Alhazov, B. Aman, R. Freund, S. Ivanov step” would be no longer possible, so the model with promoters only seems to be considerably weaker in the case without persistence of idle objects. We would like to note that, in case of P systems with sets and auto-replication, the aspect of no-persistence can be simulated as follows: add rules a→λfor each a∈V; they will make sure that such objects are not carried over to the next step, in the same time not adding anything to the result (as for productive objects, erasing them is just another option, which in the auto-replication case neither grows nor shrinks the set of objects obtained from them). This simulation takes one step, kobjects and n+krules. And, of course, if we consider P systems with all these differences, i.e., with sets, auto-replication, and without object persistence, then rule (a, b, c) of R systems becomes identical to rule a→c|¬bof P systems, while rule (A, B, C) of R systems becomes identical to rule Qa∈Aa→Qc∈Cc|{¬b|b∈B}, so the simulation is trivial, requiring one step, kobjects and nrules of type (ncoo, pro1,∗+inh∗,1). 6 Conclusions We recall that although deterministic P systems with promoters and/or inhibitors are not universal and have subregular characterizations, their power is sufficient to simulate R systems. All constructions presented in this paper (except those in previous section) simulate R systems (in their standard derivation mode) by P systems (in their standard derivation mode), with the slowdown by a factor of constant, where the descriptional complexity of the simulating P system is linear with respect to the descriptional complexity of the simulating P system. The proportionality constants vary depending on whether R systems are defined as triples of symbols or as triples of sets of symbols, and on whether promoters, inhibitors or both are used in P systems. All constructions are deterministic: while the multiset of rules to be applied to a given configuration may not be unique, the next configuration is unique. Indeed, in all these constructions, if two rules have the same left side, then either their applicability is mutually exclusive (one is being promoted and the other one is being inhibited by the same symbol), or also the right side is the same (and thus, if there are multiple choices which object would promote or inhibit the rule, such choice would not influence the result). Seventeen constructions are presented, see Table 1: 0)(general and simple in particular) R systems using single higher-weight promoters together with multiple atomic inhibitors, 1)simple R systems using promoters and inhibitors, 2)simple R systems using promoters and inhibitors and resetting multiplicities to one, 3)general R systems using promoters and inhibitors, 4)general R systems using promoters and inhibitors and resetting multiplicities to one, 5)simple R systems using promoters, 6)simple R systems using promoters and resetting multiplicities to one, 7)general R systems using promoters, 8)general R systems using promoters and resetting multiplicities to one, 9)simple R systems using inhibitors, 10)simple Complexity of Simulating R Systems by P Systems 13 P R mult features steps |O| |R1| Π0s L (ncoo, pro1,1+inh1,1) 1 n+k+ 1 3n+k+ 1 Π0G L (ncoo, pro1,∗+inh∗,1) 1 n+k+ 1 2n+k+ 1 + T0 Π1s M (ncoo, pro1,1, inh1,1) 2 n+k+k02n+k+k0 Π2s 1 (ncoo, pro1,1, inh1,1) 3 n+ 3k+k0+ 3 2n+ 4k+k0+ 3 Π3G L (ncoo, pro1,1, inh1,1) 3 n+k+ 3 n+k+ 3 + T Π4G 1 (ncoo, pro1,1, inh1,1) 4 n+ 3k+ 4 n+ 4k+ 4 + T Π5s M (ncoo, pro1,1) 3 n+k+k0+ 3 2n+k+k0+ 3 Π6s 1 (ncoo, pro1,1) 4 n+ 3k+k0+ 4 2n+ 4k+k0+ 4 Π7G L (ncoo, pro1,1) 3 n+ 2k+ 3 n+ 3k+ 3 + T Π8G 1 (ncoo, pro1,1) 4 n+ 4k+ 4 n+ 6k+ 4 + T Π9s M (ncoo, inh1,1) 2 n+k+k0+ 2 2n+k+k0+ 2 Π10 s 1 (ncoo, inh1,1) 4 n+ 3k+k0+ 4 2n+ 4k+k0+ 4 Π11 G L (ncoo, inh1,1) 3 n+ 3k+ 4 n+ 4k+ 4 + T Π12 G 1 (ncoo, inh1,1) 5 n+ 5k+ 6 n+ 6k+ 6 + T Π13 s M (ncoo, antim/pri) 2 2n+k3n+k Π14 s 1 (ncoo, antim/pri) 4 2n+ 5k+ 4 3n+ 5k+ 4 Π15 G L (ncoo, antim/pri) 3 2n+ 4k+ 3 3n+ 3k+ 3 + T Π16 G 1 (ncoo, antim/pri) 5 2n+ 8k+ 5 3n+ 7k+ 5 + T Table 1. Comparative table of simulation of R systems by P systems R systems using inhibitors and resetting multiplicities to one, 11)general R systems using inhibitors, 12)general R systems using inhibitors and resetting multiplicities to one, 13)simple R systems using antimatter, 14)simple R systems using antimatter and resetting multiplicities to one, 15)general R systems using antimatter, 16)general R systems using antimatter and resetting multiplicities to one. The table below shows the number of steps of simulating P system to simulate one step of R system, alphabet size and the number of rules in these simulations (n is the number of rules in S,kis the number of symbols in S,k0is the number of symbols that do not appear in the left side of any rule of the simulated system; by Twe denote P1≤i≤k(|Ai|+|Bi|) and by T0we denote P1≤i≤k|Bi|). Column R describes the type of simulated system, where s stands for simple (rules with triples of symbols) and G stands for general (rules with triples of sets). Column mult describes the multiplicities of symbols in the simulating P system, where M stands for multiplicative effect, L stands for last multiplicity, and 1 stands for multiplicities 0 and 1. Column features describes the kinds of rules used. Note: in Π6,Π8and Π9, intermediate objects are removed one step later, in parallel with the first step of simulation of the next step of evolution of the simulated R system, but not interfering with it. Finally, in the previous section we discussed how (qualitatively and quantitatively) adopting some aspects of R systems (such as sets instead of multisets, auto-replication or no-persistence) into the working model of P systems simplifies simulation of R systems. 20 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron have been dissolved, and thus the resulting location of each catalyst. Then, for each catalyst, associated rules in its current location are considered and combined, similarly to the second observation above, but globally. Having obtained a sequential system, the catalyst is no longer needed. Then, in [2] it was shown that such a generalization is nothing else but a sequential blind vector addition system with states, and it was claimed that it characterizes precisely the family of all semilinear vectors of integers. Indeed, in this way any purely catalytic P system over integers can be substituted by a sequential blind vector addition system with states, so the upper bound of the family of all semilinear sets of vectors of integers, or, equivalently, the family of all integer vector sets, generated by blind register machines, holds. However, the reverse is not necessarily true, i.e., it does not follow that for any sequential blind vector addition system with states there would exist an equivalent purely catalytic P system over integers. Another result in [2] has been obtained for integer vector addition P systems, namely Theorem 5. That model has been shown to characterize exactly the uniform semilinear sets. However, since in the model of integer vector addition P systems, as opposed to purely catalytic P systems over integers, there is no concept of a catalyst, dissolving a membrane only disables rules of that region, without enabling rules that, in purely catalytic P systems over integers, are contained in the parent region and associated to the catalysts that were in the dissolved region. Hence, the characterization from Theorem 5 of [2] has no direct implication on the power of purely catalytic P systems over integers. Therefore, at this point in the present paper we would like to definitely deviate into the particularities of how dissolution affects the computation, and the lower bounds. 4.2 Generative Power We recall that we discuss the family of integer vector sets generated by purely catalytic P systems over integers, with the usual halting condition. Since the output region cannot be dissolved by definition and any other applicable rule can never be stopped, single-membrane purely catalytic P systems over integers are degenerate: ZdOZP1(pcat∗, δ) = {∅} ∪ {{v} | v∈Zd}. For simplicity, we will not mention these degenerate cases while considering multiple membranes. With two membranes, a characterization is still straightforward: ZdOZP2(pcat∗, δ) = ZdSLINU N. Indeed, let Abe the finite set of vectors corresponding to the non-dissolving rules in the elementary membranes, and let Bbe the finite set of sums of two vectors: Purely Catalytic P Systems over Integers and Their Generative Power 21 the one corresponding to the initial configuration and vectors corresponding to the dissolving rules in the elementary membrane; the skin should have no rules. If the catalyst in the elementary membrane is c2, then the correspondence mentioned above is c2→c2x↔ψ(x), and similarly with dissolution. An arbitrary computation of a P system consists of an arbitrary number of applications of non-dissolving rules and one application of a dissolving rule. Hence, the resulting vector sums up from the “initial” vector, one arbitrary “dissolving” vector, and an arbitrary linear combination of “non-dissolving” vectors. It is worth noting that, by a similar reasoning, for a P system with multiple membranes, if the chronological order of dissolving membranes is fixed, the result is still ZdSLINU N. Indeed, each combination of rules (one for each catalyst) yields one vector, so all such possible combinations of non-dissolving rules yield a finite set of vectors, and multiple non-dissolving steps yield a linear set generated by these vectors. Thus, over the whole computation the result sums up from the initial configuration, a finite number of dissolution vectors, and a finite number of linear sets corresponding to the membrane structures reached during that computation. Since the total number of chronological orders of dissolving membranes is bounded, the known result already follows: ZdOZP∗(pcat∗, δ)⊆ZdSLINN. Even with three membranes, in case two of them are elementary, the power of such purely catalytic P systems over integers is still ZdSLINU N, but for a different reason: each elementary membrane contributes with its uniform semilinear set, and a sum of two uniform semilinear sets is still uniform semilinear. Let us now examine a P system with three nested membranes – the minimal number to obtain a set which is not in ZdSLINU N. Let the vector obtained by joining the initial contents of all membranes be a, the set of non-dissolving vectors of the elementary membrane be A3, the set of dissolving vectors of the elementary membrane be B3, the sets of non-dissolving and dissolving vectors in the middle membrane associated to catalyst c2are A2and B2, and the similar sets associated to catalyst c3(which will arrive from the elementary membrane) are Aand B. Let us see what the resulting vector set is built from, besides a. A non-dissolving computation in three membranes adds at each step (an element of) A3to the elementary membrane and (an element of) A2to the middle membrane. Eventually all objects will arrive to the skin, so the three-membrane phase of the computation will contribute by (an arbitrary element of) hA2+A3iN. Then there are two possibilities. If membrane 2 is dissolved first, then the system continues computing by only applying the rules in membrane 3, and eventually dissolving membrane 3, yielding B2+hA3iN+B3. However, if membrane 3 is dissolved first, then both catalysts are active in membrane 2, eventually dissolving it, yielding B3+hA2+AiN+ (B2+A∪A2+B∪A+B). The expression in parentheses corresponds to applying at least one dissolving rule. Therefore, the set of integer vectors generated by such a purely catalytic P system over integers with three nested membranes is 22 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron M=a+B3+hA2+A3iN+B2+hA3iN∪ hA2+AiN+B2+A∪A2+B∪B2+B, and the power of all three-membrane purely catalytic P systems over integers, noting that the power of the nested case subsumes the power of the case with two elementary membranes, is ZdOZP1(pcat∗, δ) = {M|a∈Zd, A2, A3, B2, B3, A, B ∈F IN(Zd)}, where Mis the expression above. Unfortunately, it is not obvious what can be simplified in it, except B3can subsume a. So we try to analyze it in details, possibly going into particular cases. All terms in the expression Mare bounded except three: hA3+A2iN,hA3iN and hA+A2iN. These terms are not independent, even though A2,A3and Aare three independent finite sets of vectors. It is, however, possible to separate them in a particular case when |A3|= 1, choosing A2=−A3and A=C−A2. Since A3is a singleton, the identity A3−A3={0}holds, so the three unbounded terms become h{0}iN,hA3iNand hCiN, so we are getting close to obtaining a union of two particular linear (or even uniform semilinear) sets with different base vectors. Indeed, if we choose a=0,B3={0},B2={0},B={0}and A3={e}, expression Msimplifies to h{e}iN∪hCiN+(C+{e}∪{0}), which can be rewritten as h{e}iN∪ hCiN∪ {e} hCiN. Alternatively, to avoid dealing with the union of three cases when membrane 2 is divided last, if we choose B2=A2and B=A, then the last parenthesis in the general expression of set Mbecomes simply A2+A=C. Choosing a=0, B3={0}, and A3={e}, expression Msimplifies to h{e}iN− {e}∪hCiN+C. Since 0∈ h{e}iN− {e}and hCiN+C∪ {0}=hCiN, in this case we can rewrite Mto −{e} ∪ h{e}iN∪ hCiN, which is a union of any two homogeneous linear sets, such that the first one has only one generator, united with the opposite vector of that generator. Hence, ZdOZPn(cat, δ))ZdSLINU N, n ≥3. What if B=∅, i.e., catalyst c3has no associated dissolution rules in region 2? Then the general expression of set Mis immediately simplified to M=a+B2+B3+hA2+A3iN+ (hA3iN∪ hA2+AiN+A), and in our case of A3={e},A2=−{e}and A=C+{e},Mbecomes a+B2+B3+ (h{e}iN∪ hCiN+C+{e}), and choosing a+B2+B3={−e}, and noticing that C0 times is covered by e0 times and hCiN+C∪{0}=hCiN, we simplify Mto {−e} ∪h{e}iN∪hCiN, i.e., an “almost clean union” we already obtained before. Finally, we notice that we can equivalently write it as h{e},−eiN∪ hCiN. Continuing the current approach with more membranes would only result in more cases. Purely Catalytic P Systems over Integers and Their Generative Power 23 4.3 Communication We would like to remark that adding target indications to the regular objects should not increase the power of purely catalytic P systems over integers. Indeed, looking at a purely catalytic P system over integers, it is easily decidable which membranes will eventually be dissolved. Hence, the only question is whether the contents of a region specified by target, after possible dissolutions, will be in the output. There is no need to examine the future of a moved regular object, since the resources in purely catalytic P systems over integers are unbounded, and we can view this copy of a moved object as staying in that region until the end of the computation. However, if also the catalysts are allowed to have target indications associated, it does make a difference. We claim the following characterizations. ZdOZP∗(mpcatk, tarn) = ZdSLINN, k ≥1, ZdOZP∗(mpcatk+δ) = ZdSLINN, k ≥1, ZdOZP∗(mpcat∗, δ) = ZdSLINN, The upper bound in either case is easy to see because the number of possible arrangements of catalysts across the given membrane structure (and any possible structures obtained from it by membrane dissolutions) is bounded. Hence, purely catalytic P systems over integers with mobile catalysts are still not more powerful than blind vector-addition systems with states, which characterize Z∗SLINN, see [2]. We now proceed to ⊇inclusions. Consider an arbitrary semilinear set S1≤i≤mhAi, biiN, where for each i, 1 ≤i≤ m,Aiis a finite set, Ai∪ {bi} ⊆ Zd. We construct the following purely catalytic P system over integers Π1= (O, C, µ, w1,· · · , w2m+1, R1,· · · , R2m+1, i0= 1) where O={ai|1≤i≤d}, C ={c}, µ= [ [ [ ]m+2 ]2· · · [ [ ]2m+1 ]m+1 ]1, w1=c, wi+1 =λ, 1≥i≥2m, R1={c→(c, ini+1)vi|1≤i≤m, ψ(vi) = bi}, Ri+1 ={c→c(v, out)|ψ(v)∈Ai}∪{c→(c, inm+i+1)},1≤i≤m, Rm+i+1 =∅,1≤i≤m. The work of Π1consists of a non-deterministic choice of i-th linear set to generate, by moving catalyst cinto membrane i+ 1 and producing bi. After sending to the skin an arbitrary combination of vectors from Ai, the catalyst enters membrane m+i+ 1 and the system halts. The system Π2is obtained from Π1by replacing the sets Ri+1 of rules, 1 ≤ i≤m, by {c→cv |ψ(v)∈Ai}∪{c→(c, inm+i+1)δ}. 24 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron It works just as Π1, with one difference, Here, instead of sending vout (possibly containing negative multiplicities), the linear combination of vectors from Aiis generated directly in membrane i+1, and is released into the skin upon dissolution of membrane i+ 1, simultaneously with sending the catalyst into the elementary membrane m+i+ 1. Now consider the following purely catalytic P system over integers. Π3= (O, C, µ, w1,· · · , w3m+1, R1,· · · , R3m+1, i0= 1) where O={ai|1≤i≤d}, C ={ci|1≤i≤m+ 1}, µ= [ [ [ [ ]2m+2 ]m+2 ]2· · · [ [ [ ]3m+1 ]2m+1 ]m+1 ]1, w1=c1, wi+1 =λ, 1≤i≤2m, w2m+1+i=c1+i,1≥i≥m, R1={c1→(c1, ini+1)vi|1≤i≤m, ψ(vi) = bi}, Ri+1 ={c1→c1v|ψ(v)∈Ai} ∪ {c1→(c1, inm+i+1), ci→ciδ},1≤i≤m, Rm+i+1 ={c1→(c1, in2m+i+1), ci→(ci, out)},1≤i≤m, R2m+i+1 ={c1→c1δ},1≤i≤m. The basic idea is the same, but the implementation is a little longer. To each linear set i, 1 ≤i≤n, three nested membranes are associated (i+ 1, m+i+ 1 and 2m+i+ 1). The beginning is just like in the case of Π2, until catalyst c1is sent into membrane m+i+ 1, but membrane i+ 1 is not dissolved yet. Then, c1 enters the elementary membrane 2m+i+1 and dissolves it, releasing catalyst ci+1 into the surrounding membrane m+i+ 1. Clearly, c1cannot reenter membrane 2m+i+1, which no longer exists, so it has no applicable associated rules. Catalyst ci, however, is sent out to membrane i+ 1, and dissolves it, which releases all generated regular objects to the skin and halts the computation. This proves the characterizations. 5 Conclusions We have reproved that the power of purely catalytic P systems over integers is contained in the family of all semilinear sets of vectors of integers. We then have shown that with one membrane purely catalytic P systems over integers give degenerate results, and with two membranes they are characterized exactly by the family of all uniform semilinear sets of vectors of integers. With more membranes, this equality becomes a strict inclusion, and a specific union of linear sets with different base vectors have been obtained. More specifically, for any vector e∈Zd and any finite set C⊆Zd, purely catalytic P systems over integers can generate h{e},−ei∪hCiN. Purely Catalytic P Systems over Integers and Their Generative Power 25 The most interesting open question remaining is whether Z∗OZP∗(pcat∗, δ) is closed under union. While in almost all cases in membrane computing closure under union is trivial, e.g., by making a non-deterministic choice in the first step of the computation, the current situation is rather surprising. Finally, we have considered the variants with mobile catalysts, and showed a few combinations of features leading to characterizations of semilinear sets of Z-vectors. References 1. A. Alhazov, B. Aman, R. Freund, and Gh. P˘aun. Matter and anti-matter in membrane systems. In H. J¨urgensen, J. Karhum¨aki, and A. Okhotin, editors, Descriptional Complexity of Formal Systems: 16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014. Proceedings, pages 65–76. Springer, 2014. 2. A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A. E. Porreca, and C. Zandron. Semilinear sets, register machines, and integer vector addition (P) systems. This volume, 2016. 3. O. Belingheri, A. E. Porreca, and C. Zandron. P systems with hybrid sets, 2016. Workshop on Membrane Computing, submitted. 4. J. Carette, A. P. Sexton, V. Sorge, and S. M. Watt. Symbolic domain decomposition. In S. Autexier, J. Calmet, D. Delahaye, P. D. F. Ion, L. Rideau, R. Rioboo, and A. P. Sexton, editors, Intelligent Computer Mathematics, 10th International Conference, AISC 2010, 17th Symposium, Calculemus 2010, and 9th International Conference, MKM 2010, Paris, France, July 5-10, 2010. Proceedings, volume 6167 of Lecture Notes in Computer Science, pages 172–188. Springer, 2010. 5. R. Freund, O. Ibarra, Gh. P˘aun, and H.-C. Yen. Matrix languages, register machines, vector addition systems. Third Brainstorming Week on Membrane Computing, pages 155–167, 2005. 6. R. Freund, S. Ivanov, and S. Verlan. P systems with generalized multisets over totally ordered abelian groups. In Int. Conf. on Membrane Computing, volume 9504 of Lecture Notes in Computer Science, pages 117–136. Springer, 2015. 7. S. A. Greibach. Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7(3):311–324, 1978. 8. C. Haase and S. Halfon. Integer vector addition systems with states. In J. Ouaknine, I. Potapov, and J. Worrell, editors, Reachability Problems: 8th International Workshop, RP 2014, Oxford, UK, September 22-24, 2014. Proceedings, pages 112–124. Springer, 2014. 9. J. Hopcroft and J.-J. Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theoretical Computer Science, 8(2):135–159, 1979. 10. S. N. Krishna and A. P˘aun. Results on catalytic and evolution-communication P systems. New Generation Computing, 22(4):377–394, 2004. 11. Gh. P˘aun. Some quick research topics. http://www.gcn.us.es/files/OpenProblems bwmc15.pdf. 12. Gh. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61:108–143, 1998. 13. Gh. P˘aun, G. Rozenberg, and A. Salomaa. The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA, 2010. Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems Artiom Alhazov1, Omar Belingheri2, Rudolf Freund3, Sergiu Ivanov4, Antonio E. Porreca2, and Claudio Zandron2 1Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: [email protected] 2Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy E-mail: {o.belingheri@campus,porreca@disco,zandron@disco}.unimib.it 3Faculty of Informatics, TU Wien Favoritenstraße 9-11, 1040 Vienna, Austria E-mail: [email protected] 4Universit´e Paris Est, France E-mail: [email protected] Summary. In this paper we consider P systems working with multisets with integer multiplicities. We focus on a model in which rule applicability is not influenced by the contents of the membrane. We show that this variant is closely related to blind register machines and integer vector addition systems. Furthermore, we describe the computational power of these models in terms of linear and semilinear sets of integer vectors. 1 Introduction P systems have been traditionally viewed as hierarchical processors of multisets [11]. In the list of open problems disseminated in 2015 [10], Gheorghe P˘aun suggested going beyond the traditional setting and considering multisets in which objects would not be restricted to having natural multiplicities. Several possible approaches have been suggested since then, including the one from [3], which defines generalised multisets as taking multiplicities from finitely generated, totally ordered Abelian groups. The work [1] takes a different approach — the objects of the P system are partitioned into two classes: regular objects, which may have any integer multiplicity, and “catalysts”, which may only appear in a bounded number of copies and cannot be consumed without being immediately reproduced. Thus, the regular objects cannot influence the applicability of rules, while the always bounded 28 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron catalysts induce a finite set of “rule teams” which can be applied in parallel in one step. The virtual absence of applicability conditions and the finiteness of the “teams” hints at the possibility of seeing them as integer vectors; in this case the P system itself can be seen as evolving by sequentially adding such vectors to the contents of its membranes. Even though this vision is quite reminiscent of the folklore vector addition systems (VAS), the latter model is actually limited to having natural vectors as configurations [2, 8]. On the other hand, P systems manipulating integer multisets allow symbols with negative multiplicities to appear. It turns out that vector addition systems without the limitation of having natural configurations (integer VAS) have received relatively little attention in the literature [7]. Another related model which has received notoriously little attention are the blind register machines, whose registers are allowed to range over the whole set of integers. Blind counter automata have been introduced and studied as string recogniser devices by Sheila Greibach in [6]; their adaptation to recognising vectors of integer numbers seems quite relevant to the study of multisets with integer multiplicities. In the present work we bring together the three models — P systems over integer multisets as defined in [1], integer vector addition systems, and blind register machines — and formally show the connections between their different variants. We also give detailed characterisations of their computing power in terms of linear and semilinear sets of natural and integer vectors. The article is structured as follows. Section 2 recalls some notions used throughout the paper, in particular semilinear sets and vector addition systems. Section 3 gives a general definition of a register machine over a set A, and then defines blind, partially blind, and conventional register machines within this general framework. Section 4 defines the model of integer vector addition P systems and gives some details as to their semantics. Section 5 investigates the power of blind register machines and gives characterisations in terms of semilinear sets of vectors. Finally, Section 6 studies the power integer vector addition systems with and without membranes, and compares different variants of the models between themselves and with blind register machines. 2 Preliminaries The reader is assumed to be familiar with the basic notions of formal languages and membrane computing; see [12] for a comprehensive introduction to both. 2.1 Linear Sets The N-linear set of Z-vectors (or just linear set of Z-vectors) generated by a set of vectors A={a1,· · · ,ad} ⊆ Znand an offset a0∈Znis defined as follows: Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems 29 hA, a0iN=(a0+ d X i=1 kiaiki∈N,1≤i≤d). We underline that the vectors are over Z, but the coefficients are from N(we will also consider the special case when A∪ {a0} ⊆ Nn; this would be an N-linear set of N-vectors, or just a linear set, a well-known concept from Formal Language Theory). AZ-linear set of Z-vectors hA, a0iZ=(a0+ d X i=1 kiai|ki∈N,1≤i≤d) can be considered, too. It corresponds precisely to the linear vector space notion from the classic course of Linear Algebra. However, it is also a particular case. Indeed, it is easy to see that hA, a0iZ=hB, a0iNfor B={a1,· · · ,ad,−a1,· · · ,−ad}. If the offset a0is the zero vector, we call the corresponding linear set homogeneous. Apositive-restricted N-linear set of Z-vectors generated by Aand an offset a0is defined to be the N-linear set of Z-vectors generated by A, restricted to non-negative vectors only: hA, a0i+ Z={x∈ hA, a0iZ|x≥0}, where x≥0 means that every component of xis non-negative. We will use the notations ZnLINN,NnLINN,ZnLINZ, and Zn +LINNto refer to the classes of all N-linear sets of Z-vectors, N-linear sets of N-vectors, Z-linear sets of Z-vectors, and positive restricted N-linear sets of Z-vectors of dimension n, correspondingly. Semilinear sets are defined as finite unions of the corresponding types of linear sets. We will use the notations ZnSLINN,NnSLINN,ZnSLINZ and Zn +SLINNto refer to the families of N-semilinear sets of Z-vectors, N- semilinear sets of N-vectors, Z-semilinear sets of Z-vectors, a nd positive-restricted N-semilinear sets of Z-vectors of dimension n, respectively. In case no particular restriction is imposed on the dimension, nwill be replaced by ∗. We may omit n if n= 1. We recall the following general result from number theory known as B´ezout’s identity. Given a set of integers A={a1,· · · , an} ⊆ Z, there exist integers x1,· · · , xn∈Zsuch that the following holds: n X i=1 xiai= gcd(a1,· · · , an), where gcd(a1, . . . , an) in the greatest common divisor of the integers from A. Furthermore, the greatest common divisor is the smallest positive integer which can be obtained as a linear combination of the elements of A. 36 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron To prove the converse inclusion, it suffices to take an arbitrary integer vector addition system and construct a blind register machine by reversing the arrows in the state control graph and by simulating the inverse effect of the addition vectors using multiple states. The same construction can be used to show that partially blind register machine are equivalent in power to conventional vector addition systems with states. Taking into consideration the result on equivalence between (conventional) VAS and VAS with states from [8], we formulate the following characterisation of the power of partially blind register machines. Theorem 2. PsPBRM =VASS =VAS. We will now show that blind register machines do not recognise more than N-semilinear sets of Z-vectors. Lemma 1. PsZBRM ⊆Z∗SLINN. Proof. Consider a blind n-register machine B. At every step, Bcan increment or decrement a register, independently of the contents of the registers. Consider the alphabet of actions of B:AB={ADD(i), SUB(i)|1≤i≤n}; every computation of Bcan be represented as a string over this alphabet. Let valid(AB)⊆A∗ Bbe the strings over A∗ Bwhich correspond to all computations of B. Pick such a string w∈valid(AB). Since the actions do not depend on the contents of the registers, any permutation of wwhich is in valid(AB) will have the same effect as w. In particular, Bwill halt with the same values in its registers. Therefore, the set of vectors Brecognises can be described as follows: N(B) = −(a1, . . . , an)|w∈valid(AB), ai=|w|ADD(i)− |w|SUB(i), where |w|xis the number of copies of the symbol x∈ABin the string w. Because Bcannot read the values of its registers, the set valid(AB) is the regular language given by the state control of B. Therefore, the Parikh image Psvalid(AB)is an N-semilinear set. This means that N(B) is an N-semilinear set of Z-vectors, and so is the set of vectors including only the values of the output registers of B. Consequently, P sZBRM ⊆Z∗SLINN, which is the statement of the lemma. We will now show that blind register machines can recognise all N-semilinear sets of Z-vectors. Lemma 2. PsZBRM ⊇Z∗SLINN. Proof. Consider an N-semilinear set Aof Z-vectors. There exists a finite collection of sets of generators Ai⊆Znand offsets ai∈Znsuch that A=SihAi,aiiZ. Consider a blind register machine Bwhich starts by non-deterministically choosing a set of generators Aiand the corresponding offset ai.Bthen repeats the following procedure until the set Aiis exhausted: Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems 37 1. remove a generator afrom Ai; 2. subtract afrom the vector describing the registers of Ba number of times chosen non-deterministically. At the end, Bsubtracts the vector aifrom its registers. If Bmanages to reset all its registers using this procedure, then, by construction, the input vector belongs to hAi,aiiZ⊆A(and the computation of the machine gives a way to construct this vector from Aiand ai). This implies the statement of the lemma. It follows from Lemmas 1 and 2 that blind register machines recognise exactly the N-semilinear sets of Z-vectors. Theorem 3. PsZBRM =Z∗SLINN. Consequently, if one takes only the natural vectors recognised by blind register machines, one obtains positive-restricted N-semilinear sets of Z-vectors. Corollary 1. PsNBRM =Z∗ +SLINN. 6 On the Power of Z-VA(P)S In this section we will describe the power of integer vector addition (P) systems in terms of semilinear sets of vectors and blind register machines. We will start by pointing out that Z-VAPS without dissolution and with unconditional halting generate exactly the sets reachable by Z-VAS. Lemma 3. PsZVAPS(gen, uncond) = Z-VAS. Proof. The effect of rules of Z-VAPS without dissolution does not depend on the contents of the membranes. Consider the set of rules Rof such a P system Π; we will construct a Z-VAS Γwhose starting vector is the initial contents of the output membrane hoof Π, and whose addition vectors are given by the projection {r(ho)|r∈R}. Since Πcan halt at any moment, its output is exactly the reachable vectors of Γ. Therefore PsZVAPS(gen, uncond)⊆Z-VAS. The converse inclusions follows from the fact that any Z-VAS can be seen as a one-membrane Z-VAPS working with unconditional halting. The same kind of reasoning allows us to characterise the power of Z-VAPS working in recognising mode and halting by reaching zero vectors in all membranes. Lemma 4. PsZVAPS(acc, zero) = Z-VAS. On the other hand, because of the direct equivalence between Z-VAS and N- linear sets of Z-vectors, we can write the previous two results in the following way. Theorem 4. PsZVAPS(gen, uncond) = PsZVAPS(acc, zero) = Z∗LINN=Z- VAS. 38 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron Allowing membrane dissolution together with unconditional halting allows generating at most unions of vector languages generated by families of Z-VAS which may only differ in their start vectors. We will call such families uniform and will denote the class of vector languages generated by such families by Z-VAS∪. Lemma 5. PsZVAPS(gen, inappl, δ)⊆Z-VAS∪. Proof. Consider a Z-VAPS Πwith normal membrane dissolution and halting by inapplicability of rules. First of all, we remark that the contents of the output membrane hoonly depend on the evolution of the membranes located within. Furthermore, homust have no rules associated, otherwise the system will never halt (or will end up dissolving hoif hois not the skin, in which case no output will be yielded either). Finally, only those inner membranes of howhich are dissolved contribute to its final contents. Consider one of the membranes hlocated somewhere within ho. If it has no inner membranes, its evolution is described by a Z-VAS. If hhas one inner membrane h0which is elementary (it contains no other membranes), then we can distinguish two phases in the evolution of h: before and after the dissolution of h0(and before the dissolution of hitself). Given that the contents of h0must eventually be merged with those of h, we can just as well consider that, during the first phase, the rules contributing to hare extended by the corresponding additions carried out by the rules contributing to h0. Since the order in which the rules of Z-VAPS are applied does not affect the result, we can consider that hcontains no inner membranes at all, but possesses a double set of contributing rules instead: one which combines the original rules contributing to hand to h0, and another which only includes the original rules contributing to h. Therefore, we can correctly describe the evolution of hby taking at least some of the vectors a Z-VAS can reach. We remark that the rule dissolving h0in this case may only be applied once, and its effect can be simulated by adding the vector it produces to the starting multiset of the containing membrane h. The reasoning from the previous paragraphs can be applied to a membrane which contains multiple elementary membranes, as well as, inductively, to all inner membranes of the output membrane ho: we can replace hoby a new elementary membrane h0 o, and take some of the vectors generated in it into the output language. Remark now that the moment at which a membrane is dissolved is not correlated with its contents and only depends on whether all of its inner membranes have been dissolved already. This means that, if the depth of the membrane structure contained in hois d,dsteps of evolution are necessary and suffice for dissolving all the inner membranes of ho. Therefore, the contents of the membrane ho in the halting configurations of Πare given by all the vectors that can be reached in membrane h0 oin at least dsteps. These are the vectors which can be reached by the family of Z-VAS {(wi, W)|wi∈Wd}, where Wcontains the addition vectors defined by the rules contributing to the new membrane h0 o, and Wdis the (finite) set of vectors which h0 ocan reach in exactly dsteps. Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems 39 It turns out that this family of Z-VAPS can generate all vector languages from Z-VAS∪. Lemma 6. PsZVAPS(gen, inappl, δ)⊇Z-VAS∪. Proof. Consider a finite family of Z-VAS F={(wi, W)|1≤i≤n}. We will define a Z-VAPS Πgenerating the vectors reachable by the systems from Fin the following way. Πwill have two nested membranes and two groups of rules. The first group of rules will apply the vectors from Wto the inner membrane. A rule of the second group will add one of the vectors wito the inner membrane and dissolve it immediately. By construction, the vectors appearing in the halting configurations of Πare exactly the vectors which can be reached by the Z-VAS from F, which proves the lemma. The following theorem summarises the two preceding lemmas. Theorem 5. PsZVAPS(gen, inappl, δ) = Z-VAS∪. Interestingly, the class Z-VAS∪is strictly in between the classes Z-VAS and Z-VASS. Lemma 7. Z-VAS ( Z-VAS∪. Proof. The inclusion is trivial. Consider now two Z-VAS having the axioms (0,0) and (0,1), and sharing the only addition vector (1,1). The language of vectors reachable by these two systems is L={(a, a),(a, a + 1) |a∈N}. Suppose there exists a Z-VAS Γgenerating the same vector language L. In order to generate all pairs of natural numbers (a, a), it must start with the axiom (0,0) and have an addition vector of the form (1,1). Then, in order to generate the pairs (a, a + 1), Γneeds to have an addition vector of the form (x, x + 1). However, applying this addition vector twice yields the vector (2x, 2x+ 2) /∈L, which contradicts the supposition and proves that the inclusion from the statement of the lemma is strict. The following lemma describes the relationship between Z-VAS∪and Z-VASS. Lemma 8. Z-VAS∪( Z-VASS. Proof. The work of a finite family Fof Z-VAS can be simulated by a Z-VASS by non-deterministically choosing a state in which one of the start vectors of Fwill be added, and by subsequent direct simulation of the application of the shared addition vectors. Consider now the Z-VASS Γwith the starting vector (0,0), which applies the addition vector (0,0) in the starting state q0and the non-deterministically chooses between q(1,0) and q(0,1). In q(1,0),Γmay apply the addition vector (1,0) indefinitely, before transitioning into qh. Similarly, in q(0,1),Γmay apply the addition vector (0,1) indefinitely, before moving into qh. Thus, the vector language generated by Γis L={(a, 0),(0, a)|a∈N}. 40 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron Suppose there exists a family of Z-VAS which generate the same language. The shared addition vectors of this family must therefore include both (1,0) and (0,1). But then, this family must also generate vectors in which both components are non-zero and which therefore do not belong to L. This contradicts our supposition and proves that the inclusion in the statement of the lemma is strict. The previous lemma also gives an example of a Z-semilinear set which cannot be generated by uniform family of Z-VAS systems, which implies the following result. Corollary 2. Z-VAS∪( Z∗SLINN. It follows from the Theorem 5, Lemmas 7 and 8, as well as from the characterisations from the previous section, that the languages recognised by Z-VAPS with normal dissolution and conventional halting are situated strictly in between N-linear sets of Z-vectors and N-semilinear sets of Z-vectors. Theorem 6. Z∗LINN(PsZVAPS(gen, inappl, δ)( Z∗SLINN. Finally, we show that allowing dissolution of multiple membranes by one rule allows generating all Z-semilinear languages and therefore renders such Z-VAPS equivalent in power to blind register machines. Theorem 7. PsZVAPS(gen, inappl, δ∗) = Z∗SLINN. Proof (Sketch). Consider a family Fof nZ-VAS, each of which generates a Z- linear set of vectors. One can construct an integer vector addition P system Π with multiple dissolution in the following way. Πwill have n+ 2 membranes organised in a linear structure. The rules of Πwill simulate the i-th Z-VAS in the membrane at depth i+ 1 (the depth of the skin is 0); moreover, Πwill have a rule producing the start vector wiand introducing n−icopies of δinto the membrane at depth i+ 1, for 1 ≤i≤n. These rule effectively finalise the simulation of the i-th Z-VAS. Finally, Πwill have rules introducing icopies of δinto the innermost membrane, for 1 ≤i≤n, which will “select” the membrane at depth i+ 1 and will allow it to eventually apply its dissolution rules and put the result into the skin. Thus, Πgenerates the semilinear language generated by the family F. To prove the inverse inclusion, we will rely on Lemma 1. Consider a Z-VAPS Πwith multiple dissolution. We will construct a blind register machine Bwhich recognises the vector language generated by Πin the following way. Bwill have a group of working register per membrane of Πwhich will represent the multiplicities of the symbols in this membrane. Bwill start with the vector xin its input registers, and will simulate the applications of rules of Πin its working registers. Whenever Πdissolves a membrane (or multiple membranes), Bwill nondeterministically guess the multiplicities of each symbol in the dissolved membrane and will copy the guessed values into the working registers representing the corresponding parent membrane. When all inner membranes of the output membranes have been dissolved (Bcan encode the information about the membrane structure Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems 41 in its state), Bwill simultaneously decrement the working registers representing the contents of the skin and the input registers. If, earlier during the simulation, Bhad guessed the value of a register wrongly, or, at the end of the simulation, the values of the input registers and the working registers representing the skin did not match, some registers of Bwill be zero and the vector xwill be rejected. It follows from the construction that Bwill accept exactly the vector generated by Π, which implies the statement of the theorem. 7 Conclusion In this paper we continued the investigation of P systems with multisets with integer multiplicities, proposed in [10] and already studied in [3] and [1]. We focused on the model originally described in [1] and generalised it to integer vector addition P systems, in which the applicability of rules does not in any way depend on the contents of the membranes. Interestingly enough, this P system variant exhibits very strong connection with blind register machines and integer vector addition systems — two models which have received little to no attention in the scientific literature up to now. We studied a number of working modes of and halting conditions for integer vector addition P systems and gave exact characterisations of the power of the corresponding variants in terms of linear and semilinear sets over Zand over N. We also pointed out a number of relations between the classes of languages generated or accepted by the model. Some non-trivial open questions are revealed by our research. One of them concerns the semantics of multiple dissolution. In P systems, dissolution typically concerns one membrane at a time; in the present paper we suggest considering the possibility of dissolving multiple containing membranes in one step. The semantics we propose discards the contents of the dissolved intermediary membranes, so only the multiset of the innermost dissolved membrane is transferred to the corresponding parent membrane. Other semantics of multiple dissolution may be possible and are certainly worth exploring. A very interesting open question concerns the types of semilinear sets. In this paper we only deal with semilinear sets with generators and initial offsets from Nn and Zn, restricted to non-negative values or not. It is however possible to consider the generators, the offsets, and the coefficients to belong to Nnor Zn, alternatively. This yields 8 possibly different kinds of semilinear sets, not including restrictions to non-negative values. Exploring the relations between these kinds of semilinear sets may be useful in further refining certain characterisations. Finally, we point out that classical halting by inapplicability of rules is not necessarily well adapted for dealing with generalisations of multisets to integers. We give examples of different halting conditions inspired by other models of computing, but our list is far from exhaustive and is definitely worth to be extended. 42 A. Alhazov, O. Belingheri, R. Freund, S. Ivanov, A.E. Porreca, C. Zandron References 1. O. Belingheri, A. E. Porreca, and C. Zandron. P systems with hybrid sets, 2016. Workshop on Membrane Computing, submitted. 2. R. Freund, O. Ibarra, Gh. P˘aun, and H.-C. Yen. Matrix languages, register machines, vector addition systems. Third Brainstorming Week on Membrane Computing, pages 155–167, 2005. 3. R. Freund, S. Ivanov, and S. Verlan. P systems with generalized multisets over totally ordered abelian groups. In Int. Conf. on Membrane Computing, volume 9504 of Lecture Notes in Computer Science, pages 117–136. Springer, 2015. 4. R. Freund, M. Kogler, and M. Oswald. A general framework for regulated rewriting based on the applicability of rules. In J. Kelemen and A. Kelemenov´a, editors, Computation, Cooperation, and Life, volume 6610 of Lecture Notes in Computer Science, pages 35–53. Springer Berlin Heidelberg, 2011. 5. R. Freund and S. Verlan. A formal framework for static (tissue) P systems. In G. Eleftherakis, P. Kefalas, Gh. P˘aun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, volume 4860 of Lecture Notes in Computer Science, pages 271–284. Springer Berlin Heidelberg, 2007. 6. S. A. Greibach. Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7(3):311–324, 1978. 7. C. Haase and S. Halfon. Integer vector addition systems with states. In J. Ouaknine, I. Potapov, and J. Worrell, editors, Reachability Problems: 8th International Workshop, RP 2014, Oxford, UK, September 22-24, 2014. Proceedings, pages 112–124. Springer, 2014. 8. J. Hopcroft and J.-J. Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theoretical Computer Science, 8(2):135–159, 1979. 9. O. H. Ibarra. Automata with reversal-bounded counters: A survey. In H. J¨urgensen, J. Karhum¨aki, and A. Okhotin, editors, Descriptional Complexity of Formal Systems: 16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014. Proceedings, pages 5–22. Springer, 2014. 10. Gh. P˘aun. Some quick research topics. http://www.gcn.us.es/files/OpenProblems bwmc15.pdf. 11. Gh. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61:108–143, 1998. 12. Gh. P˘aun, G. Rozenberg, and A. Salomaa. The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA, 2010. Extended SNP Systems with States Artiom Alhazov1, Rudolf Freund2, and Sergiu Ivanov3 1Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: [email protected] 2Faculty of Informatics, TU Wien Favoritenstraße 9-11, 1040 Vienna, Austria E-mail: [email protected] 3Universit´e Paris Est, France E-mail: [email protected] Summary. We consider (extended) spiking neural P systems with states, where the applicability of rules in a neuron not only depends on the presence of sufficiently many spikes (yet in contrast to the standard definition, no regular checking sets are used), but also on the current state of the neuron. Moreover, a spiking rule not only sends spikes, but also state information to the connected neurons. We prove that this variant of the original model of extended spiking neural P systems can simulate register machines with only two states, even in the basic non-extended variant. 1 Introduction In the area of P systems, the model of spiking neural P systems was introduced in [7]. Whereas the basic model of membrane systems, see [11], reflects hierarchical membrane structures, in spiking neural P systems the cells are arranged in a tissuelike manner, with the contents of a cell (neuron) consisting of a number of so-called spikes, i.e., of a multiset over a single object. The rules assigned to a neuron allow us to send information to other neurons in the form of electrical impulses (also called spikes) which are summed up at the target neuron; the application of the rules depends on the contents of the neuron and in the general case is described by regular sets. As inspired from biology, the neuron sending out spikes may be “closed” for a specific time period corresponding to the refraction period of a neuron; during this refraction period, the neuron is closed for new input and cannot get excited (“fire”) for spiking again. The length of the axon may also cause a time delay before a spike arrives at the target. Moreover, the spikes coming along different axons may cause effects of different magnitude. All these biologically motivated features were included in the model of extended spiking neural P systems considered in [3], the most 44 A. Alhazov, R. Freund, and S. Ivanov important theoretical feature being that neurons can send spikes along the axons with different magnitudes at different moments of time. In this paper, we consider a variant of the model of extended spiking neural P systems which not only uses spikes to be sent to other neurons when some neuron spikes, but also allows for sending some additional information called “state” along the axons. All these state informations arriving in a neuron then determine the next state of the neuron. On the other hand, we do not use the regular checking sets for the current number of spikes in the neuron any more, which decreases the amount of information a spiking rule may use. Hence, the spiking rules now depend on the current states of the neurons and the availability of sufficiently many spikes. This variant of extended spiking neural P systems with states has been inspired by the variant of spiking neural P systems with polarizations, see [16], where the states are called polarizations, and the underlying model of extended spiking neural P systems was the basic one with a fixed connection structure, only extended by allowing more than one spike to be sent along the axons. There it was shown that computational completeness (i.e., simulation of register machines) can be obtained with only three polarizations. In this paper we now show that computational completeness can already be obtained with only two states, i.e., with two polarizations, even for the basic non-extended variant as considered in [16], which solves an open problem raised at the Brainstorming Week on Membrane Computing in Sevilla at the beginning of February 2016. The rest of the paper is organized as follows: In the next section, we recall some preliminary notions and definitions from formal language theory, especially the definition and some well-known results for register machines. In Section 3 we recall the definitions of the extended model of spiking neural P systems as considered in [3] and then define the model of spiking neural P systems with states as considered in this paper. In Section 4, we prove our main result and show that spiking neural P systems with only two states (0 and 1) can simulate register machines; the complexity of the construction depends on the features we require the spiking neural P systems to have, but the result even holds true for the basic non-extended variant of spiking neural P systems with states, where the connection structure between the neurons is fixed and does not depend on the spiking rules applied in the neurons. Moreover, we can use a very simple global state composition function computing the new state of a neuron from the state information having arrived from the input neurons in the simplest way by going to the “activated state 1” if and only if at least one such activating signal 1 has come in the previous step. In Section 5, we show how small universal spiking neural P systems with states can be constructed based on the results obtained in this paper. A short summary of the results we obtained concludes the paper. 2 Preliminaries In this section we recall the basic elements of formal language theory and especially the definitions and results for register machines; we also refer to the corresponding Extended SNP Systems with States 45 section from [3] and [2]. For the basic elements of formal language theory needed in the following, we refer to any monograph in this area, in particular, to [14]. We just list a few notions and notations: V∗is the free monoid generated by the alphabet Vunder the operation of concatenation and the empty string, denoted by λ, as unit element; for any w∈V∗, |w|denotes the number of symbols in w(the length of w). N+denotes the set of positive integers (natural numbers), Nis the set of non-negative integers, i.e., N=N+∪ {0}. 2.1 Register Machines The proofs of the results establishing computational completeness in the area of P systems are often based on the simulation of register machines; we refer to [9] for original definitions, and to [6] for the definitions we use in this paper: An n-register machine is a tuple M= (n, B, l0, lh, P ), where nis the number of registers, Bis a set of labels, l0∈Bis the initial label, lh∈Bis the final label, and Pis the set of instructions bijectively labeled by elements of B. The instructions of Mcan be of the following forms: •p: (ADD(r), q, s), with p∈B\ {lh},q, s ∈B, 1 ≤j≤n. Increases the value of register rby one, followed by a non-deterministic jump to instruction qor s. This instruction is usually called increment. •p: (SUB(r), q, s), with p∈B\ {lh},q, s ∈B, 1 ≤j≤n. If the value of register ris zero then jump to instruction s; otherwise, the value of register ris decreased by one, followed by a jump to instruction q. The two cases of this instruction are usually called zero-test and decrement, respectively. –lh:halt (HALT instruction) Stop the machine. The final label lhis only assigned to this instruction. A (non-deterministic) register machine Mis said to generate a vector (s1,· · · , sβ) of natural numbers if, starting with the instruction with label l0and all registers containing the number 0, the machine stops (it reaches the instruction lh:halt) with the first βregisters containing the numbers s1,· · · , sβ(and all other registers being empty). The register machines are known to be computationally complete, equal in power to (non-deterministic) Turing machines: they generate or accept exactly the sets of vectors of non-negative integers which can be generated by Turing machines. 3 Extended Spiking Neural P Systems The reader is supposed to be familiar with basic elements of membrane computing, e.g., from [10] and [12]; comprehensive information can be found on the P systems 52 A. Alhazov, R. Freund, and S. Ivanov p p0 r p00 q s (0, a) (a, 0) (a, 0) (0, a) (a, 0) (0, a) (a, 1) (0, a) (a, 0) (1, a) (a, 0) Fig. 4. Simulation of ADD using a connection structure which only depends on states. p0: (0, a)→000 q, a, 0(100 s, a, 0) and p0: (0, a)→000 q, a, 1(100 s, a, 1), together with the following rules in the neurons 000 l,100 l, for every label l∈B: 000 l: (0, a)→(l, a, 1) and 000 l: (1, a)→λ, 100 l: (1, a)→(l, a, 1) and 100 l: (0, a)→λ. Figure 5 gives a graphical illustration of these rules. Forgetting rules which only consume spikes without sending anything anywhere are depicted as dangling arrows. p p0 r 000 q 100 s q s (1, a) (a, 0) (a, 0) (0, a) (a, 0) (a, 0) (0, a) (a, 1) (a, 1) (0, a) (a, 1) (1, a) (a, 1) (1, a) (0, a) Fig. 5. Simulation of ADD using a fixed connection structure. Instead of showing how SUB-instructions can also be simulated within a fixed connection structure, we also attack the last remaining non-standard feature at the same time, i.e.: Can we avoid sending zero spikes? p: (SUB(r), q, s) is simulated by the neurons p, ˜p, ˜p0,ˆp, ˆp0,ˆp00,¯p, ¯p0with the rules p: (1, a)→(˜p, a, 1) (ˆp, a, 1) (r, a, 1), Extended SNP Systems with States 53 ˜p: (1, a)→(˜p0, a, 0), ˜p0:1, a2→(q, a, 1) Ql∈SUB(r)\{p}ˆ l00, a, 1, ˜p0: (0, a)→λas well as ˆp: (1, a)→(ˆp0, a, 1), ˆp0: (1, a)→(ˆp00, a, 0), ˆp00: (0, a)→(r, a, 1) (¯p, a, 1), ˆp00:1, a2→λ, ¯p: (1, a)→(¯p0, a, 1), and ¯p0: (1, a)→(s, a, 1) Ql∈SUB(r)ˆ l00, a, 1 together with the following rules for the register neuron rand for the additional neuron r0: r:1, a2→(r0, a, 1) Ql∈SUB(r)˜ l0, a, 1and r0: (1, a)→Ql∈SUB(r)ˆ l00, a, 1. The rules are graphically illustrated in Figure 6. As before, dangling arrows represent rules sending nothing, while dashed arrows correspond to families of right-hand sides. For readability, we highlight neurons p,q, and s, which represent the states of the simulated machine. The dotted line going into neuron ˆp00 represents the family of right-hand sides which broadcast spikes and states to all neurons ˆ l00,except neuron ˆp00 (l∈SUB(r)\ {p}). Finally, to avoid line intersections, the picture uses a “clone” of neuron r(the small grey rbetween ˆp00 and ¯p), which represents the same neuron r. The main idea of this construction is to start both decrement and zero-check case in parallel and then, depending on the signal from rand r0take the necessary action, including to reset register rto the 0 if the additional spike sent there did not lead to a spiking action of neuron rin case the value stored in the register was zero. Moreover, all actor neurons affected by signals from neuron rnot belonging to the current label phave to be reset without allowing them to act in a non-desired way: For the neurons ˜p0this happens automatically as with only one spike athey cannot spike in state 1, yet after one step the state goes back to 0 and then allows the spike to be forgotten. For the neurons ˆp00 this happens if the state signal 1 and the spike from neuron r0are accompanied by a second spike which allows for resetting the neuron by using the forgetting rule 1, a2→λ. 5 Universal (Extended) Spiking Neural P Systems with Two States We simulate the strongly universal register machine U22 of Korec, see [8]. Rather than performing a direct simulation which would yield 9 ×1 + 8 ×1 + 13 ×4 = 69 54 A. Alhazov, R. Freund, and S. Ivanov p r ˜p ˆp r0 ˜p0 ˆp0 q ˆp00 ¯p¯p0s (1, a) (a, 1) (a, 1) (a, 1) (1, a) (a, 0) (1, a2) (a, 1) (a, 1) (0, a) (1, a) (a, 0) (0, a) (a, 0) (0, a) (a, 1) r (a, 1) (1, a2) (1, a) (a, 1) (1, a) (a, 1) (a, 1) (1, a2) (a, 1) (a, 1) (1, a) (a, 1) Fig. 6. Simulating SUB using a fixed connection structure and without sending zero spikes. rules, we notice that simulation of ADD-instructions does not require separate rules, because it can be done as a part of the simulation of SUB-instructions. More exactly, increments are built into the transitions to qand sof p: (SUB(r), q, s). This has been formalized as generalized register machine (GRM for short), see [1]. The rules of U22 in the GRM form are given below. q1: (SUB(1),ADD(7)q1,ADD(6)q4), q4: (SUB(5),ADD(6)q4, q7), q7: (SUB(6),ADD(5)q10, q4), q10 : (SUB(7),ADD(1)q7, q13), q13 : (SUB(6),ADD(6)q14, q1), q14 : (SUB(4), q1, q16), q16 : (SUB(5), q18, q23), q18 : (SUB(5), q20, q27), q20 : (SUB(5),ADD(4)q16,ADD(2)ADD(3)q32), q23 : (SUB(2), q32, q25), q25 : (SUB(0), q1, q32), q27 : (SUB(3), q32,ADD(0)q1), q32 : (SUB(4), q1, qh). We note that also the first step of the simulation of a generalized SUB- instruction can be embedded into the last step of the preceding simulation. Moreover, note that in this case we may start with one spike in neuron q00 13. It is easy to see that it suffices to have 3 rules per each of the 13 generalized conditional decrement instructions and 1 rule per each of the 8 registers, yielding a total Extended SNP Systems with States 55 of only 47 rules, associated to register neurons, primed instruction neurons and double-primed instruction neurons. Register neurons 0 : (1, a)→(q00 25, λ, 1) , 1 : (1, a)→(q00 1, λ, 1) , 2 : (1, a)→(q00 23, λ, 1) , 3 : (1, a)→(q00 27, λ, 1) , 4 : (1, a)→(q00 14, λ, 1) (q00 32, λ, 1) , 5 : (1, a)→(q00 4, λ, 1) (q00 16, λ, 1) (q00 18, λ, 1) (q00 20, λ, 1) , 6 : (1, a)→(q00 7, λ, 1) (q00 13, λ, 1) , 7 : (1, a)→(q00 10, λ, 1) . The primed instruction neurons have the rules q0 i: (1, a)→(q00 i, a, 0) for i∈ {1,4,7,10,13,14,16,18,20,23,25,27,32}. We give the rules of double-primed instruction neurons in the table below, the row representing the neuron, the column representing the left side of a rule, and their intersection containing the right side of that rule. (0, a) (1, a) q00 1(q0 4, a, 1) (5, λ, 1)(6, a, 0) (q0 1, a, 1) (1, λ, 1)(7, a, 0), q00 4(q0 7, a, 1) (6, λ, 1) (q0 4, a, 1) (5, λ, 1)(6, a, 0), q00 7(q0 4, a, 1) (5, λ, 1) (q0 10, a, 1) (7, λ, 1)(5, a, 0), q00 10 (q0 13, a, 1) (6, λ, 1) (q0 7, a, 1) (6, λ, 1)(1, a, 0), q00 13 (q0 1, a, 1) (1, λ, 1) (q0 14, a, 1) (4, λ, 1)(6, a, 0), q00 14 (q0 16, a, 1) (5, λ, 1) (q0 1, a, 1) (1, λ, 1), q00 16 (q0 23, a, 1) (2, λ, 1) (q0 18, a, 1) (5, λ, 1), q00 18 (q0 27, a, 1) (3, λ, 1) (q0 20, a, 1) (5, λ, 1), q00 20 (q0 32, a, 1) (4, λ, 1)(2, a, 0)(3, a, 0) (q0 16, a, 1) (5, λ, 1)(4, a, 0), q00 23 (q0 25, a, 1) (0, λ, 1) (q0 32, a, 1) (4, λ, 1), q00 25 (q0 32, a, 1) (4, λ, 1) (q0 1, a, 1) (1, λ, 1), q00 27 (q0 1, a, 1) (1, λ, 1)(0, a, 0) (q0 32, a, 1) (4, λ, 1), q00 32 (qh, a, 0) (q0 1, a, 1) (1, λ, 1). This construction uses a total of 8 + 2 ×13 + 1 = 35 neurons. The halting neuron qhcan be avoided, e.g., by changing the right side of the rule with q00 32 : (0, a) to, e.g., (4, λ, 1). Indeed, the register machine halts with register 4 being empty, so the P system will halt after neuron 4 has reset its state to 0. We also remark that this construction does not respect the requirement of all states on the right side being equal. This requirement can be fulfilled by replacing (r, a, 0) by (r0, a, 1) for r∈ {0,1,4,5,6,7}and (2, a, 0)(3, a, 0) by (h2,3i0, a, 1) in the right sides of the rules above, and adding 7 additional neurons, each having one rule: r0: (1, a)→(r, a, 0) for r∈ {0,1,4,5,6,7}and the neuron h2,3iwith the rule h2,3i0: (1, a)→(2, a, 0)(3, a, 0), yielding a total of 54 rules. 56 A. Alhazov, R. Freund, and S. Ivanov If we consider the most restricted variant of spiking neural P systems with states elaborated at the end of Section 4, which is comparable with the model considered in [16] using the notion of polarizations instead of the notion states, when again embedding the first step of the simulation of a generalized SUB-instruction into the last step of the preceding simulation, a straight-forward calculation yields two neurons and two rules per register as well as 7 neurons and 9 rules per generalized conditional decrement instruction, which yields a total of 16 +7 ×13 = 107 neurons as well as 16 + 9 ×13 = 133 rules. It only remains to argue the correctness of the construction. As before, embedded ADD-instructions translate exactly into sending additional spikes to register neurons by existing rules simulating the SUB-instructions. Hence, we only explain the latter, i.e., the decrement case and the zero-test case. Suppose we simulate a rule p: (SUB(r), q, s), and the next instruction performs the SUB (rq) or the SUB (rs) command, respectively. The configuration of the P system consists of the description of (the state of and the number of spikes in) each of its neurons. Clearly, the neurons in state 0 and without spikes present no interest; we also omit the register neurons different from r. By lwe denote any element of SUBrother than r. Furthermore, we underline the spikes which are to be removed from the firing neuron, and we will highlight in bold the neurons which are idle and whose state switches from 1 to 0. Step p˜p˜p0ˆpˆp0ˆp00 r r0˜ l0ˆ l00 1 (1, a) (0, anr) 2 (1, a) (1, a) (1, anr−1+2) 3 (1, a2) (1, a) (0, anr−1) (1, a) (1,a) 4 (1, a2) (0, anr−1) (0, a) (1, a2) 5 (0, anr−1) Fig. 7. The trace of the decrement case. The trace of the decrement case is presented in Figure 7. What is not reflected on this figure is that line 4 of the trace of instruction pis superposed with line 2 of instruction q. However, since the neurons are disjoint, no interference happens. Indeed, the last step of simulation of instruction premoves the spikes from neurons ˆp00,ˆ l00, and ˜ l0, while the simulation of instruction qacts upon neurons ˜q, ˆqand rq. We observe that (if p6=q) a spike is removed from ˜q0simultaneously with a spike being sent to ˜q0, which of course causes no interference, since the spikes do not meet. As mentioned before, the first step is omitted (by embedding it into the initial configuration and into every preceding step), so the simulation starts at line 2, taking just 2 steps to produce line 2 for the next instruction, and one more step to remove the superfluous spikes. Extended SNP Systems with States 57 Step p˜p˜p0ˆpˆp0ˆp00 ¯p¯p0r r0˜ l0ˆ l00 1 (1, a) 2 (1, a) (1, a) (1,a) 3 (1,a) (1, a) (0, a) 4 (0, a) (0, a) (0, a) 5 (1, a) (1, a2) 6 (1,a) (1, a) (1, a) (1,a) 7 (0, a) (1, a2) (0, a) (1, a2) 8 Fig. 8. The trace of the zero-test case. The trace of the zero-test case is presented in Figure 8. Similarly to the decrement case, it does not reflect that line 7 of the trace of instruction pis superposed with line 2 of instruction s. Hence, the arguments about the correctness of the decrement case also hold for the zero-test case, with the following differences. The last step of simulation of instruction palso removes two spikes from neuron ˜p0. As mentioned before, the first step is omitted, so the simulation starts at line 2, taking 5 steps to produce line 2 for the next instruction, and one more step to remove the superfluous spikes. This completes the explanation of the correctness. It is easy to see that forgetting rules may be replaced by sending a spike to one additional dummy neuron. 6 Conclusion We have shown that only two states (or polarizations as they are called in [16]) are needed for obtaining computational completeness with (extended) spiking neural P systems with states, thus solving an open problem raised at the Brainstorming Week on Membrane Computing in Sevilla at the beginning of February 2016. References 1. A. Alhazov and R. Freund. Variants of small universal P systems with catalysts. Fundamenta Informaticae, 138(1-2):227–250, 2015. 2. A. Alhazov, R. Freund, S. Ivanov, M. Oswald, and S. Verlan. Extended spiking neural P systems with white holes. In L. Mac´ıas-Ramos, Gh. P˘aun, A. Riscos-N´u˜nez, and L. Valencia-Cabrera, editors, Proceedings of the 13th Brainstorming Week on Membrane Computing, pages 45–62. F´enix Editora, Sevilla, 2015. 3. A. Alhazov, R. Freund, M. Oswald, and M. Slavkovik. Extended spiking neural P systems. In Workshop on Membrane Computing, volume 4361 of Lecture Notes in Computer Science, pages 123–134. Springer, 2006. 58 A. Alhazov, R. Freund, and S. Ivanov 4. H. Chen, R. Freund, M. Ionescu, Gh. P˘aun, and M. P´erez-Jim´enez. On string languages generated by spiking neural P systems. In Prooceedings of the Fourth Brainstorming Week on Membrane Computing, volume 1, pages 169–194. F´enix Editora, Sevilla, 2006. 5. H. Chen, M. Ionescu, T.-O. Ishdorj, A. P˘aun, Gh. P˘aun, and M. J. P´erez-Jim´enez. Spiking neural P systems with extended rules: universality and languages. Natural Computing, 7(2):147–166, 2007. 6. R. Freund and M. Oswald. A short note on analysing P systems. Bulletin of the EATCS, 78:231–236, 2002. 7. M. Ionescu, G. P˘aun, and T. Yokomori. Spiking neural P systems. Fundamenta Informaticae, 71(2,3):279–308, 2006. 8. I. Korec. Small universal register machines. Theoretical Computer Science, 168:267– 301, 1996. 9. M. L. Minsky. Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey, 1967. 10. Gh. P˘aun. Membrane Computing: An Introduction. Natural Computing Series Natural Computing. Springer, 2002. 11. Gh. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61:108–143, 2000. 12. Gh. P˘aun, G. Rozenberg, and A. Salomaa, editors. The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. 13. Gh. P˘aun, Y. Sakakibara, and T. Yokomori. P systems on graphs of restricted forms. Publicationes Mathematicae Debrecen, 60:635–660, 2006. 14. G. Rozenberg and A. Salomaa, editors. Handbook of Formal Languages, volume 1-3. Springer, 1997. 15. The P Systems Website. 16. T. Wu, A. P˘aun, Z. Zhang, and L. Pan. Spiking neural P systems with polarizations. submitted, 2015. Computational Completeness of P Systems Using Maximal Variants of the Set Derivation Mode Artiom Alhazov1, Rudolf Freund2, and Sergey Verlan3 1Institute of Mathematics and Computer Science Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au, MD-2028, Moldova E-mail: [email protected] 2Faculty of Informatics, TU Wien Favoritenstraße 9-11, 1040 Wien, Austria E-mail: [email protected] 3LACL, Universit´e Paris Est – Cr´eteil Val de Marne 61, av. G´en´eral de Gaulle, 94010, Cr´eteil, France Email: [email protected] Summary. We consider P systems only allowing rules to be used in at most one copy in each derivation step, especially the variant of the maximally parallel derivation mode where each rule may only be used at most once. Moreover, we also consider the derivation mode where from those sets of rules only those are taken which have the maximal number of rules. We check the computational completeness proofs of several variants of P systems and show that some of them even literally still hold true for the for these two new set derivation modes. Moreover, we establish two new results for P systems using target selection for the rules to be chosen together with these two new set derivation modes. 1 Introduction Membrane systems with symbol objects are a theoretical framework of parallel distributed multiset processing. Usually, multisets of rules are applied in parallel to the objects in the underlying configuration; for example, in the maximally parallel derivation mode (abbreviated max), a non-extendable multiset of rules is applied to the current configuration. In this paper we now consider variants of these derivation modes, where each rule is only used in at most one copy, i.e., we consider sets of rules to be applied in parallel, for example, in the set-maximally parallel derivation mode (abbreviated smax) we apply non-extendable sets of rules, and in another derivation mode we apply sets of rules which contain a maximal number of applicable rules (abbreviated maxrule). 60 A. Alhazov, R. Freund, and S. Verlan Taking sets of rules instead of multisets is a quite natural restriction and it arises from different motivations, e.g., firing a maximal set of transitions in Petri Nets [5, 8] or optimizing an implementation of FPGA simulators [13]. A natural question arises concerning the power of set-based modes in contrast to multisetbased ones. The first attempt to go into this direction was done in [10] where it was shown that in some cases the computational completeness results established for the max-mode also hold for the smax-mode. In this paper we continue this line of research and we show that for several variants of P systems the proofs for computational completeness for max can be taken over even literally for smax and eventually even for maxrule, but on the other hand there are also variants of P systems where the derivation modes smax and maxrule yield even stronger results than the max-mode. 2 Variants of P Systems In this section we recall the well-known definitions of several variants of P systems as well as some variants of derivation modes and also introduce the variants of set derivation modes considered in the following. A (cell-like) P system is a construct Π= (O, C, µ, w1, . . . , wm, R1, . . . , Rm, fO, fI) where •Ois the alphabet of objects, •C⊂Ois the set of catalysts, •µis the membrane structure (with mmembranes), •w1, . . . , wmare multisets of objects present in the mregions of µat the beginning of a computation, •R1, . . . , Rmare finite sets of rules, associated with the regions of µ, •fOis the label of the membrane region from which the outputs are taken (in the generative case) •fIis the label of the membrane region where the inputs are put at the beginning of a computation (in the accepting case). fO= 0/fI= 0 indicates that the output/input is taken from the environment. If a rule u→vhas at least two objects in u, then it is called cooperative, otherwise it is called non-cooperative.Catalytic rules are of the form ca →cv, where c∈Cis a special object which never evolves and never passes through a membrane, it just assists object ato evolve to the multiset v. In catalytic P systems we use non-cooperative as well as catalytic rules. In a purely catalytic P system we only allow catalytic rules. In the maximally parallel derivation mode (abbreviated by max), in any computation step of Πwe choose a multiset of rules from R, defined as the union of the sets R1, . . . , Rm, in such a way that no further rule can be added to it so that the obtained multiset would still be applicable to the existing objects in the regions 1, . . . , m. Maximal Variants of the Set Derivation Modes 61 2.1 Set Derivation Modes The basic set derivation mode is defined as the derivation mode where in each derivation step at must one copy of each rule may be applied in parallel with the other rules; this variant of a basic derivation mode corresponds to the asynchronous mode with the restriction that only those multisets of rules are applicable which contain at most one copy of each rule, i.e., we consider sets of rules: Appl(Π, C, set) ={R∈Appl(Π, C, asyn)| |R|r≤1 for each r∈ R} In the set-maximally parallel derivation mode (this derivation mode is abbreviated by smax for short), in any computation step of Πwe choose a non-extendable multiset Rof rules from Appl(Π, C, set); following the notations elaborated in [7], we define the mode smax as follows: Appl(Π, C, smax) ={R∈Appl(Π, C, set)|there is no R0∈Appl(Π, C, set) such that R0⊃R} The smax-derivation mode corresponds to the min1-mode with the discrete partitioning of rules (each rule forms its own partition), see [7]. The derivation mode maxrulesmax is a special variant where only a maximal set of rules is allowed to be applied. But it can also seen as the variant of the basic set mode where we just take a set of applicable rules with the maximal number of rules in in it, hence, we will also call it the maxrule derivation mode. Formally we have: Appl(Π, C, maxrule) ={R∈Appl(Π, C, set)|there is no R0∈Appl(Π, C, set) such that |R0|>|R|} As usual, with all these variants of derivation modes as defined above, we consider halting computations. We may generate or accept or even computing functions or relations. The inputs/outputs may be multisets or strings, defined in the well-known way. 2.2 The History of the smax-Derivation Mode In [13], a paper on fast P systems simulators using FPGA, the problem of the unbounded max-mode was considered as too difficult to be parallelized on this hardware. In the quest for an efficient solution, the authors proposed to restrict to the case of the maximal parallelism where each rule can be applied at most once. The most important advantage of this variant was that the multiset of applicable rules could be represented as a binary string, i.e., an encoding as a number. Moreover, the paper showed that in many interesting cases it is possible to represent the language of corresponding binary strings at each step by an automaton. Then the problem of the simulation of a P system could be solved as follows: 68 A. Alhazov, R. Freund, and S. Verlan 6 Computational Completeness of (Purely) Catalytic P Systems with Additional Control Mechanisms In this section we consider (purely) catalytic P systems with additional control mechanisms, in that way reaching computational completeness with only one (two) catalyst(s). 6.1 P Systems with Label Selection For all the variants of P systems of type X, we may consider to label all the rules in the sets R1, . . . , Rmin a one-to-one manner by labels from a set Hand to take a set Wcontaining subsets of H. Then a P system with label selection is a construct Π= (O, µ, w1, . . . , wm, R1, . . . , Rm, H, W, f) where Π0= (O, µ, w1, . . . , wm, R1, . . . , Rm, f) is a P system as defined above, His a set of labels for the rules in the sets R1, . . . , Rm, and W⊆2H. In any transition step in Πwe first select a set of labels U∈Wand then apply a non-empty multiset Rof rules such that all the labels of these rules in Rare in Uin the maximally parallel way, i.e., the set Rcannot be extended by any further rule with a label from Uso that the obtained multiset of rules would still be applicable to the existing objects in the membrane regions 1, . . . , m. The families of sets Yγ,δ (Π), Y∈ {N, Ps},δ∈ {gen, acc}, and γ∈ {sequ, asyn, max, smax, maxrule, . . . }, computed by P systems with label selection with at most mmembranes and rules of type Xis denoted by Yγ,δOPm(X, ls). The proof of the following theorem is based on the proof given in [6] for the maximally parallel mode max; the proof can be taken over for the mode smax word by word; the only difference is that in non-successful computations where more than one trap symbol # has been generated, the trap rule # →# is only applied once. Theorem 5. Yγ,δOP1(cat1, ls) = YγδOP1(pcat2, ls) = Y RE for any Y∈ {N, Ps},δ∈ {gen, acc}, and γ∈ {max, smax}. Proof. We only prove the inclusion P sRE ⊆Pssmax,genOP1(cat1, ls). Let us consider a register machine M= (n+ 2, B, l0, lh, I) with only the first and the second register ever being decremented, and let A={a1, . . . , an+2}be the set of objects for representing the contents of the registers 1 to n+ 2 of M. We construct the following P system: Π= (O, {c},[ ]1, cdl0, R1, H, W, 0), O=A∪B∪ {d, #}, H={l, l0|l∈B} ∪ lhxi|x∈ {1,2,10,20, d, #}, Maximal Variants of the Set Derivation Modes 69 and the rules for R1and the sets of labels in Ware defined as follows: A. Let li: (ADD (r), lj, lk) be an ADD instruction in I. If r > 2, then the (labeled) rules li:li→lj(ar, out), l0 i:li→lk(ar, out), are used, and for r∈ {1,2}, we take the rules li:li→ljar, l0 i:li→lkar. In both cases, we define {li, l0 i}to be the corresponding set of labels in W. The contents of each register r,r∈ {1,2}, is represented by the number of objects ar present in the skin membrane; any object arwith r≥3 is immediately sent out into the environment. B. The simulation of a SUB instruction li: (SUB (r), lj, lk), for r∈ {1,2}, is carried out by the following rules and the corresponding sets of labels in W: For the case that the register r,r∈ {1,2}, is not empty we take the (labeled) rules li:li→lj, lhri:car→c, lhdi:cd →c#, (if no symbol aris present, i.e., if the register ris empty, then the trap symbol # is introduced by the rule lhdi:cd →c#). For the case that the register ris empty, we take the (labeled) rules l0 i:li→lk, lhr0i:car→c# (if at least one symbol aris present, i.e., if the register ris not empty, then the trap symbol # is introduced by the rule lhr0i:car→c#). The corresponding sets of labels to be taken into Ware li, lhri, lhdiand l0 i, lhr0i, respectively. In both cases, the simulation of the SUB instruction works correctly if we have made the right choice. C. As soon as the final label lhis reached, we apply the rules lh:lh→λ, l0 h:cd →c according to the set of labels {lh, l0 h}in W. In fact, neglecting the single catalyst c, we could even obtain a clean result in the skin membrane when leaving the result objects in the skin membrane instead of sending them out. D. We also add the labeled rule lh#i: # →# to R1and the set lh#ito W, hence, the computation cannot halt once the trap symbol # has been generated. In sum, we observe that each computation step in Mis simulated by exactly one computation step in Π; moreover, such a simulating computation in Πhalts if and only if the corresponding computation in Mhalts (as soon as the label lh appears, only the set of rules {lh, l0 h}can be applied, and afterwards no rule can be applied anymore in Π, of course, provided that no trap symbol is present). 70 A. Alhazov, R. Freund, and S. Verlan If at some moment we make the wrong choice when trying to simulate a SUB instruction and have to generate the trap symbol #, the computation will never halt. Hence, we have shown Ps (M) = P s (Π), which completes the proof for the catalytic case. For the purely catalytic case, all the non-cooperative rules are associated with the second catalyst, which immediately yields the corresponding purely catalytic P system with two catalysts. ut 6.2 Controlled P Systems and Time-Varying P Systems Another method to control the application of the labeled rules is to use control languages (see [9] and [4]). A controlled P system is a construct Π= (O, µ, w1, . . . , wm, R1, . . . , Rm, H, L, f) where Π0= (O, µ, w1, . . . , wm, R1, . . . , Rm, f) is a P system as defined above, H is a set of labels for the rules in the sets R1, . . . , Rm, and Lis a string language over 2H(each subset of Hrepresents an element of the alphabet for L) from a family FL. Every successful computation in Πhas to follow a control word U1. . . Un∈L: in transition step i, only rules with labels in Uiare allowed to be applied (but again in the maximally parallel way, i.e., we have to apply a multiset Rof rules with labels in Uiwhich cannot be extended by any rule with a label in Uisuch that the resulting multiset would still be applicable), and after the n-th transition, the computation halts; we may relax this end condition, i.e., we may stop after the i-th transition for any i≤n, and then we speak of weakly controlled P systems. If L= (U1. . . Up)∗,Πis called a (weakly) time-varying P system: in the computation step pn +i,n≥0, rules from the set Uihave to be applied; pis called the period. The family of sets Yγ,δ (Π), Y∈ {N, P s}, computed by (weakly) controlled P systems and (weakly) time-varying P systems with period p, with at most mmembranes and rules of type Xas well as control languages in FL is denoted by Yγ,δOPm(X, C (FL)) (Yγ,δOPm(X, wC (FL))) and Yγ,δOPm(X, TVp) (Yγ,δOPm(X, wTVp)), respectively, for δ∈ {gen, acc}and γ∈ {sequ, asyn, max, smax, maxrule, . . . }. The proof of the following theorem again is taken over for the mode smax word by word as given in [6] for the maximally parallel mode max. Theorem 6. Yγ,δOP1(cat1, αTV6) = Yγ,δOP1(pcat2, αTV6) = Y RE, for any α∈ {λ, w},Y∈ {N, P s},δ∈ {gen, acc}, and γ∈ {max, smax}. Proof. We only prove the inclusion P sRE ⊆Pssmax,genOP1(cat1, TV6). Let us consider a register machine M= (n+ 2, B, l0, lh, I) with only the first and the second register ever being decremented. Again, we define A={a1, . . . , an+2}and divide the set of labels B\ {lh}into three disjoint subsets: Maximal Variants of the Set Derivation Modes 71 B+={li|li: (ADD (r), lj, lk)∈I}, B−r={li|li: (SUB (r), lj, lk)∈I}, r ∈ {1,2}; moreover, we define B−=B−1∪B−2as well as B0=nl, ˜ l, ˆ l|l∈B\ {lh}o∪l−, l0,¯ l−,¯ l0,|l∈B−. The main challenge in the construction for the time-varying P system Πis that the catalyst has to fulfill its task to erase an object ar,r∈ {1,2}, for both objects in the same membrane where all other computations are carried out, too; hence, at a specific moment in the cycle of period six, parts of simulations of different instructions have to be coordinated in parallel. The basic components of the timevarying P system Πare defined as follows (we here do not distinguish between a rule and its label): Π= (O, {c},[ ]1, cl0, R1∪ · · · ∪ R6, R1∪ · · · ∪ R6,(R1. . . R6)∗,0), O=A∪ {a0 1, a0 2} ∪ B0∪ {c, h, lh,#}. We now list the rules in the sets of rules Rito be applied in computation steps 6n+i,n≥0, 1 ≤i≤6: R1: in this first step of the cycle, especially all the ADD instructions are simulated, i.e., for each li: (ADD (r), lj, lk)∈Iwe take cli→car˜ lj,cli→car˜ lkfor r∈ {1,2}as well as cli→c(ar, out)˜ lj,cli→ c(ar, out)˜ lkfor 3 ≤r≤n+ 2 (in order to obtain the output in the environment, for r≥3 we have to take (ar, out) instead of ar); only in the sixth step of the cycle, from ˜ ljand ˜ lkthe corresponding unmarked labels ljand lkwill be generated; cl →cl−,cl →cl0initiate the simulation of a SUB instruction for register 1 labeled by l∈B−1, i.e., we make a non-deterministic guess whether register ris empty (with introducing l0) or not (with introducing l−); cl →cˆ lmarks a label l∈B−2(the simulation of such a SUB instruction for register 2 will start in step 4 of the cycle); #→# keeps the trap symbol # alive guaranteeing an infinite loop once # has been generated; h→λeliminates the auxiliary object hwhich eventually has been generated two steps before (his needed for simulating the decrement case of SUB instructions). R2: in the second and the third step, the SUB instructions on register 1 are simulated, i.e., for all l∈B−1we start with ca1→ca0 1(if present, exactly one copy of a1can be primed, but only if a label l−for some lfrom B−1is present) and l−→¯ l−h,l0→¯ l0for all l∈B−1; all other labels ˜ lfor l∈Bblock the catalyst cfrom erasing a copy of a1by forcing the application of the corresponding rules c˜ l→c˜ lfor cin order to avoid 72 A. Alhazov, R. Freund, and S. Verlan the introduction of the trap symbol # by the enforced application of a rule ˜ l→#, i.e., we take c˜ l→c˜ l,˜ l→# for all l∈B, and cˆ l→cˆ l,ˆ l→# for all l∈B−2; #→# keeps the computation alive once the trap symbol has been introduced. R3: for all li: (SUB (1) , lj, lk)∈Iwe take c¯ l0 i→c˜ lk,a0 1→#, ¯ l0 i→# (zero test; if a primed copy of a1is present, then the trap symbol # is generated); ¯ l− i→˜ lj,ca0 1→c,ch →c# (decrement; the auxiliary symbol his needed to keep the catalyst cbusy with generating the trap symbol # if we have taken the wrong guess when assuming the register 1 to be non-empty); c˜ l→c˜ l,˜ l→# for all l∈B(with these labels, we just pass through this step); cˆ l→cˆ l,ˆ l→# for all l∈B−2(these labels pass through this step to become active in the next step); #→#. R4: in the fourth step, the simulation of SUB instructions on register 2 is initiated by using cˆ l→cl−,cˆ l→cl0for all l∈B−2, i.e., we make a non-deterministic guess whether register ris empty (with introducing l0) or not (with introducing l−); c˜ l→c˜ l,˜ l→# for all l∈B(with all other labels, we only pass through this step); #→#, h→λ(if hhas been introduced by l−→¯ l−hin the second step for some l∈B−1, we now erase it). R5: in the fifth and the sixth step, the SUB instructions on register 2 are simulated, i.e., for all l∈B−2we start with ca2→ca0 2(if present, exactly one copy of a2can be primed) and l−→¯ l−h,l0→¯ l0for all l∈B−2; c1˜ l→c1˜ l,˜ l→# for all l∈B; #→#. R6: the simulation of SUB instructions li: (SUB (2) , lj, lk)∈Ion register 2 is finished by c¯ l0 i→clk,a0 2→#, ¯ l0 i→# (zero test; if a primed copy of a2is present, then the trap symbol # is generated); ¯ l− i→lj,ca0 2→c,ch →c# (decrement; the auxiliary symbol his needed to keep the catalyst cbusy with generating the trap symbol # if we have taken the wrong guess when assuming the register 2 to be non-empty; if it is not used, it can be erased in the next step by using h→λin R1); c˜ l→cl,˜ l→# for all l∈B; #→# . Without loss of generality, we may assume that the final label lhin Mis only reached by using a zero test on register 2; then, at the beginning of a new cycle, Maximal Variants of the Set Derivation Modes 73 after a correct simulation of a computation from Min the time-varying P system Πno rule will be applicable in R1(another possibility would be to take c¯ l0 i→c instead of c¯ l0 i→clhin R6). At the end of the cycle, in case all guesses have been correct, the requested instruction of Mhas been simulated and the label of the next instruction to be simulated is present in the skin membrane. Only in the case that Mhas reached the final label lh, the computation in Πhalts, too, but only if during the simulation of the computation of Min Πno trap symbol # has been generated; hence, we conclude Ps (M) = Ps (Π). For the purely catalytic case, all the non-cooperative rules are associated with the second catalyst, which immediately yields the corresponding purely catalytic P system with two catalysts. ut 7 P Systems with Toxic Objects In many variants of (catalytic) P systems, for proving computational completeness it is common to introduce a trap symbol # for the case that the derivation goes the wrong way as well as the rule # →# (or c#→c# with a catalyst c) guaranteeing that the derivation will never halt. Yet most of these rules can be avoided if we specify a specific subset of toxic objects Otox. The P system with toxic objects is only allowed to continue a computation from a configuration Cby using an applicable multiset of rules covering all copies of objects from Otox occurring in C; moreover, if there exists no multiset of applicable rules covering all toxic objects, the whole computation having yielded the configuration Cis abandoned, i.e., no results can be obtained from this computation. For any variant of P systems, we add the set of toxic objects Otox and in the specification of the families of sets of (vectors of) numbers generated by P systems with toxic objects using rules of type Xwe add the subscript tox to O, thus obtaining the families Yγ,genOtoxPm(X), for any m≥1, γ∈ {sequ, asyn, max, smax, maxrule}, and Y∈ {N, Ps}. The following theorem stated in [2] only for the max-mode obviously hols for the smax-mode, too. Theorem 7. For β∈ {max, smax}, PsRE =P sβ,genOtoxP1([p]cat2). In general, we can formulate the following “metatheorem”: Metatheorem: Whenever a proof has been established for the derivation mode max and literally also holds true for the derivation mode smax, then omitting trap rules by using the concept of toxic objects works for both derivation modes in the same way. 74 A. Alhazov, R. Freund, and S. Verlan In the following sections, we now turn our attention to models of P systems where the derivation mode smax yields different, in fact, stronger results than the derivation mode max. 8 Atomic Promoters and Inhibtors As shown in [11], P systems with non-cooperative rules and atomic inhibitors are not computationally complete when the maximally parallel derivation mode is used. P systems with non-cooperative rules and atomic promoters can at least generate PsET 0L. On the other hand, already in [10], the computational completeness of P systems with non-cooperative rules and atomic promoters has been shown. In the following we will establish a new proof for the simulation of a register machine where the overall number of promoters only depends on the number of decrementable registers of the register machine. Moreover, we also show a new pretty surprising result, establishing computational completeness of P systems with non-cooperative rules and atomic inhibitors, and the number of inhibitors again only depends on the number of decrementable registers of the simulated register machine. Finally, in both cases, if the register machine is deterministic, then the P system is deterministic, too. 8.1 Atomic Promoters We now establish our new proof for the computational completeness of P systems with non-cooperative rules and atomic promoters when using the derivation mode smax; the overall number of promoters only is 5mwhere mis the number of decrementable registers of the simulated register machine. Theorem 8. For any register machine M= (d, B, l0, lh, R), with m≤dbeing the number of decrementable registers, we can construct a P system with atomic inhibitors Π= (O, µ = [ ]1, w1=l0, R1, f = 1) working in the smax- or maxrule-derivation mode and simulating the computations of Msuch that |R1| ≤ ADD1(R)+2×ADD2(R)+5×SUB(R)+7×m, where ADD1(R)denotes the number of deterministic ADD-instructions in R, ADD2(R)denotes the number of non-deterministic ADD-instructions in R, and SUB(R)denotes the number of SUB-instructions in R; moreover, the number of atomic inhibitors is 5m. Finally, if the register machine is deterministic, then the P system is deterministic, too. Maximal Variants of the Set Derivation Modes 75 Proof. The numbers of objects orrepresent the contents of the registers r, 1 ≤ r≤d; moreover, we denote BSUB ={p|p: (SUB(r), q, s)∈R}. O={or|1≤r≤d}∪{o0 r, cr, c0 r, c00 r, c000 r|1≤r≤m} ∪(B\ {lh})∪ {p0, p00, p000 |p∈BSUB} The symbols from {o0 r, cr, c0 r, c00 r, c000 r|1≤r≤m}are used as promoters. An ADD-instruction p: (ADD(r), q, s) is simulated by the two rules p→qor and p→sor. A SUB-instruction p: (SUB(r), q, s) is simulated in four steps as follows: 1. p→p0cr; 2. p0→p00c0 r;or→o0 r|cr,cr→λ; 3. p00 →p000c000 r,c0 r→c00 r|o0 r,o0 r→λ; 4. p000 →q|c00 r,p000 →s|c0 r,c0 r→λ|c000 r,c00 r→λ,c000 r→λ. As final rule we could use lh→λ, yet we can omit this rule and replace every appearance of lhin all rules as described above by λ.ut 8.2 Atomic Inhibtors We now show that even P systems with non-cooperative rules and atomic promoters using the derivation mode smax can simulate any register machine needing only 2m+ 1 inhibitors where mis the number of decrementable registers of the simulated register machine. Theorem 9. For any register machine M= (d, B, l0, lh, R), with m≤dbeing the number of decrementable registers, we can construct a P system with atomic inhibitors Π= (O, µ = [ ]1, w1=l0, R1, f = 1) a P system with atomic inhibitors Π= (O, µ = [ ]1, w1=l0, R1, f = 1) working in the smax- or maxrule-derivation mode and simulating the computations of M such that |R1| ≤ ADD1(R)+2×ADD2(R)+5×SUB(R)+3×m+ 1, where ADD1(R)denotes the number of deterministic ADD-instructions in R, ADD2(R)denotes the number of non-deterministic ADD-instructions in R, and SUB(R)denotes the number of SUB-instructions in R; moreover, the number of atomic inhibitors is 2m+ 1. Finally, if the register machine is deterministic, then the P system is deterministic, too. Proof. The numbers of objects orrepresent the contents of the registers r, 1 ≤ r≤d. The symbols drprevent the register symbols or, 1 ≤r≤m, from evolving. 76 A. Alhazov, R. Freund, and S. Verlan O={or|1≤r≤d}∪{o0 r|1≤r≤m}∪{dr|0≤r≤m} ∪(B\ {lh})∪ {p0, p00,˜p|p∈BSUB} We denote D=Qm i=1 diand Dr=Qm i=1,i6=rdi. An ADD-instruction p: (ADD(r), q, s) is simulated by the two rules p→qorD and p→sorD. A SUB-instruction p: (SUB(r), q, s) is simulated in four steps as follows: 1. p→p0Dr; 2. p0→p00Dd0; in parallel, the following rules are used: or→o0 r|¬dr,dk→λ, 1 ≤k≤m; 3. p00 →˜pD |¬o0 r;o0 r→λ,d0→λ; again, in parallel the rules dk→λ, 1 ≤k≤m, are used; 4. p00 →qD |¬d0, ˜p→sD. As final rule we could use lh→λ, yet we can omit this rule and replace every appearance of lhin all rules as described above by λ.ut 9 P Systems with Target Selection In P systems with target selection, all objects on the right-hand side of a rule must have the same target, and in each derivation step, for each region a (multi)set of rules – non-empty if possible – having the same target is chosen. We show that for P systems with target selection in the derivation mode smax no catalyst is needed any more, and with maxrule, we even obtain a deterministic simulation of deterministic register machines. Theorem 10. For any register machine M= (d, B, l0, lh, R), with m≤dbeing the number of decrementable registers, we can construct a P system with noncooperative rules working in the smax-derivation mode and simulating the computations of M. Proof. As usual, we take an arbitrary register machine Mwith dregisters satisfying the following conditions: the output registers are m+ 1,· · · , d, and they are never decremented; moreover, registers 1,· · · , m are empty in any reachable halting configuration. Clearly, these conditions do not restrict the generality. We construct the following P system Πsimulating M. The correct behavior of the object associated to the simulated instruction of Mis the following. In the decrement case, we have inr+ 2, out,in2, idle, out,in2, here,out,here (9 steps in total), whereas in the zero-test case, we have the same as before, except that the fourth and the fifth steps are out and here instead of idle and out, respectively. In case of an increment instruction, we get here,here,here, here,in2,here,out,here (8 steps in total). We remark that the first four steps are carried out in the skin, while the last four steps repeat the cases of zero-test and decrement. Maximal Variants of the Set Derivation Modes 77 The value of each register ris represented by the multiplicity of objects orin the skin. For every decrementable register r, there is a rule sending orinto region r+2. However, this rule may only be applied safely in the first step of the simulation of the SUB instruction, as otherwise some other object will also enter the same region as # (either one of e,e0,e00, ˆe, ˆe0, which we will in the following refer to as the guards, or an object associated to the label of the simulated instruction, which we will in the following call a program symbol) forcing an unproductive computation, see the rules in brackets in the tables below. The “correct” target selection for the inner regions normally coincides with that of the program symbol (described above) and no rule is applied there if the program symbol is not there, with the following exceptions. In the first step of simulating an instruction, object eexits membrane 2, as it is the only rule applicable there in this step. In the last step of simulating an instruction, object ¯eis rewritten into ein membrane 2, as it is the only rule applicable there in this step. In the fourth step of the decrement case, the program symbol is idle while object dis erased. The “correct” target selection for the skin coincides with that of the program symbol, and is here if the program symbol is missing in the skin. 84 A. Alhazov, R. Freund, and S. Verlan 13. S. Verlan and J. Quiros. Fast hardware implementations of P systems. In E. Csuhaj- Varj´u, M.Gheorghe, G. Rozenberg, A. Salomaa, and Gy. Vaszil, editors, Membrane Computing. 13th International Conference, CMC 2012, Budapest, Hungary, August 28-31, 2012, Revised Selected Papers, volume 7762 of Lecture Notes in Computer Science, pages 404–423. Springer, 2013. Verifying P Systems with Costs by Using Priced-Timed Maude Bogdan Aman and Gabriel Ciobanu Romanian Academy, Institute of Computer Science, Ia¸si, Romania E-mail: [email protected],[email protected] Summary. We consider P systems that assigns storage costs per step to membranes, and execution costs to rules. We present an abstract syntax of the new class of membrane systems, and then deal with costs by extending the operational semantics of P systems with promoters, inhibitors and registers. We use Priced-Timed Maude to implement the P systems with costs. By using such a rewriting engine which corresponds to the semantics of membrane systems with costs, we are able to prove the operational correctness of this implementation. Based on such an operational correspondence, we can analyze properly the evolutions of the P systems with costs, and verify several reachability properties, including the cost of computations that reach a given membrane configuration. This approach opens the way to various optimization problems related to membrane systems, problems making sense in a bio-inspired model which now can be verified by using a complex software platform. 1 Introduction Membrane computing is introduced in [10] and represents now a well known branch of natural computing that aims to abstract computing ideas and formal models from the structure and functioning of living cells, as well as from the organization of cells in tissues, organs or other higher order structures such as colonies of cells [11]. Membrane systems (known also as P systems) are parallel and distributed models working with multisets of symbols in cell-like compartmental architectures. The existing results in membrane computing refer mainly to the P systems characterization of Turing computability, providing also some polynomial solutions to NP-complete problems by using an exponential workspace created in a “biological way”. Time was introduced and studied in the framework of membrane systems [2]. However, time is not the only quantitative notion of interest; other quantities such as energy [8] or accumulated cost can be included in such systems. The notions of energy and cost are connected to (evolution) time, because the longer the system evolves, the higher the energy and costs are. For simplicity, in this paper we study 86 B. Aman, G. Ciobanu only the (evolution) costs in a membrane system. A membrane system with costs is essentially a simple membrane system in which object storage costs per evolution step are assigned to membranes, and execution costs are assigned to rules. Notice that here we consider the cost only as an external/observer variable, and thus whether a rule is applicable only depends on available resources (not cost value). In this paper we present an abstract syntax of the membrane systems with costs, and then define a structural operational semantics of P systems with costs. We use a rewriting engine called Priced-Timed Maude to implement these P systems. After proving an operational correctness of this implementation, we can analyze properly the evolutions of the P systems involving costs, We look at the cost of computations reaching a given membrane configuration. This paper represents a first step towards a more detailed analysis of various costs in the context of membrane systems. This class of P systems with costs differs from energy-based P systems [8], a model of membrane systems whose computations occur by manipulating the energy associated to the objects, as well as the free energy units occurring inside the regions of the system. In [8] the energy units are used to transform objects, while in this paper the costs are used only to compute the evolution cost, and eventually to return an optimal evolution with respect to its cost. 2 Membrane Systems with Costs Before describing in a formal way the evolution of a P system with costs, we present first an inductive definition of the membrane structure, the sets of configurations, and a definition for the corresponding transition systems. Configurations are states of a transition system, and a computation consists of sequences of transitions between configurations terminating (if it terminates) in a final configuration. A sequence of transition steps represents a computation. A computation is successful if this sequence is finite, namely there is no rule applicable to the objects present in the last committed configuration. In a halting committed configuration, the result of a successful computation is the total number of objects present either in the membrane considered as the output membrane, or in the outer region. In general,operational semantics provides a framework for defining a formal description of a computing system. It is intuitive and flexible, and it becomes more attractive during the years by the developments presented in [12] and [9]. In basic P systems, a computation is regarded as a sequence of parallel applications of rules in various membranes, followed by a communication step and a dissolving step. The operational semantics of the P systems emphasises the deductive nature of the membrane computing by describing the transition steps by using a set of inference rules [3]. The operational semantics of P systems is implemented by using the cost extension of the rewriting system called Maude [7]. The relationship between the operational semantics of P systems and Maude rewriting is given by certain operational correspondence results. Verifying P Systems with Costs Using Priced-Timed Maude 87 Let Obe a finite alphabet of objects over which we consider the free commutative monoid O∗ c, whose elements are multisets. The empty multiset is denoted by empty. Objects can be enclosed in messages together with a target indication. We have here messages of typical form (w, here), out messages (w, out), and in messages (w, inL). For the sake of simplicity, hereinafter we consider that the messages with the same target indication merge into one message: Qi∈I(vi, here)=(w, here), Qi∈I(vi, inL) = (w, inL), Qi∈I(vi, out)=(w, out), with w=Qi∈Ivi,Ia non-empty set, and (vi)i∈Ia family of multisets over O. We use the mapping rules to associate to a membrane label the set of evolution rules: rules(Li) = Ri, and the projections L,wand cwhich return from a membrane its label, its current multiset, and its cost, respectively. The set M(Π)of membranes for a P system with costs Π, and the membrane structures are inductively defined as follows: •if Lis a label, cis a cost and wis a multiset over O∪(O× {here})∪(O× {out})∪{δ}, then hL;c|wi ∈ M(Π); hL;c|wiis called simple (or elementary) membrane, and it has the structure hi; •if Lis a label, cis a cost and wis a multiset over O∪(O× {here})∪(O× {inL(Mj)|j∈[n]})∪(O× {out})∪ {δ},M1, . . . , Mn∈ M(Π), n≥1, where each membrane Mihas the structure µi, then hL;c|w;M1, . . . , Mni∈M(Π); hL;c|w;M1, . . . , Mniis called a composite membrane having the structure hµ1, . . . , µni. We conventionally suppose the existence of a set of sibling membranes denoted by NULL such that M, NULL =M=NULL, M and hL|w;NULL i=hL|wi. The use of NULL significantly simplifies several definitions and proofs. Let M∗(Π) be the free commutative monoid generated by M(Π) with the operation ( ,) and the identity element NULL. We define M+(Π) as the set of elements from M∗(Π) without the identity element. Let M+,N+range over non-empty sets of sibling membranes, Miover membranes, M∗,N∗range over possibly empty multisets of sibling membranes, and Lover labels. The membranes preserve the initial labelling, cost and evolution rules in all subsequent configurations. Therefore in order to describe a membrane we consider its label, its cost and the current multiset of objects together with its structure. Aconfiguration for a P system with costs Πis a skin membrane which has no messages and no dissolving symbol δ, i.e., the multisets of all regions are elements in O∗ c. We denote by C(Π) the set of configurations for Π. An intermediate configuration is an arbitrary skin membrane in which we may find messages or the dissolving symbol δ. We denote by C#(Π) the set of intermediate configurations. We have C(Π)⊆ C#(Π). Each P system with costs has an initial configuration which is characterized by the initial multiset of objects for each membrane and the initial membrane structure of the system. For two configurations C1and C2of Π, we say that there is a transition from C1to C2, and write C1⇒C2, if the following steps are executed in the given order: 1. maximal parallel rewriting step as in [6]; 88 B. Aman, G. Ciobanu 2. parallel communication of objects through membranes; 3. parallel membrane dissolving of the membranes containing δ. The last two steps take place only if there are messages or δsymbols resulting from the first step, respectively. If the first step is not possible, then neither are the other two steps; we say that the system has reached a halting configuration. To illustrate these notions we give in Figure 1 a small example containing only of a single membrane labelled by 1 and with associated cost 2. This membrane contains three objects Aand three rules with different assigned costs (rule R0with cost 10, rule R1with cost 8 and rule R2with cost 12). A possible evolution leads in just one step to a configuration consisting of three objects Band with the cost of evolution of 30 resulting from applying three times rule R0. Fig. 1. A Small P System with Costs 1 2 A+A+A R0:A10 −→ B R1:A8 −→ C R2:C12 −→ D 3 Implementing P Systems with Costs by using Maude Reasoning about the accumulated cost (of energy usage, for instance) during behaviours is crucial in biological and embedded systems (e.g., wireless sensor networks) where minimizing overall consumed resources is critical. Generally, by using a rewriting engine called Maude, a formal specification of a system can be automatically transformed into an interpreter. Moreover, Maude provides an useful new extension called Priced-Timed Maude [4] supporting the formal specification and analysis of systems in which the cost of performing actions plays a significant role. The tool offers a search command, a semi-decision procedure for finding failures of safety properties, and also a model checker. Since the P systems with costs combine the power of parallel rewriting in various locations (compartments), the power of local and contextual evolution and the use of rewriting costs, it is natural to use a rewriting engine and a rewrite theory. Roughly speaking, a rewrite theory is a triple (Σ, E, R,L), where (Σ, E) is an equational theory used for implementing the deterministic computation, therefore (Σ, E) should be terminating and Church-Rosser, Ris a set of rewrite rules with costs used to implement nondeterministic and/or concurrent computations, and L is a set of tick rules which can model the time elapse in the system. Therefore we find rewriting logic suitable for implementing these membrane systems. Verifying P Systems with Costs Using Priced-Timed Maude 89 For simplicity, in this section we consider only costs added to the evolution rules. A P system consists of a maximal parallel application of the evolution rules, the (repeated) steps of internal evolution, communication, and dissolving. This sequence of steps uses a kind of synchronization. A P system has a tree like structure with the skin as its root, the composite membranes as its internal nodes and the elementary membranes as its leaves. The order of the children of a node is not important due to the associativity and commutativity properties of the concatenation operation ,of membranes. In what follows we extend with costs the operational semantics of membrane systems with promoters, inhibitors [5] and registers [1]. We define an operational semantics of membrane systems by means of three sets of inference rules corresponding to maximal parallel rewriting, sending messages and dissolving. The notation R ` t→t0is used to express that t→t0is provable in the theory Rusing the inference rules of rewriting logic. We use the syntax of the rewriting engine Maude extended for systems with costs [4] to describe a rewriting theory which corresponds faithfully to the semantics of membrane systems with costs. In rewriting logic we describe a multiset of objects and messages as consisting of four “bags” of which three are multisets of objects (standing for objects which are actually in the membrane, objects with message here, objects with message out), and the fourth containing a multiset of pairs of objects and labels iwhich stand for objects with message ini. This representation facilitates the rewriting logic specification because in this way there is no need for additional sorts with respect to messages. We first consider the following sorts: sorts Obj ObjMultiset ObjAddressMultiset Label Rule RuleSet . subsort Obj < ObjMultiset . subsort Rule < RuleSet . By emptyMO and emptyMAO we denote the empty multiset of objects, respectively of objects with labels, and use +to denote the addition on both ObjMultiset and ObjAddressMultiset. The multiset of objects with addresses is constructed through the operator op in : ObjMultiset Label -> ObjAddressMultiset. A rule is constructed through the operator op _->_|_|_|_|_|_ : ObjMultiset ObjMultiset ObjMultiset ObjAddressMultiset ObjMultiset ObjMultiset Cost -> Rule [ctor] . The first slot is for the objects to be consumed (it is the left hand side of the rule); the second slot is for the objects produced with label ”here”; the third slot is for the objects produced with label ”out”; the fourth slot is for the objects produced with label ”in child”; the next two slots are for promoters respectively inhibitors. The last slot is used to give the cost of applying the rule. The operators which are used to manipulate the components of a rule are ops lhs rhsHere rhsOut promoter inhibitor : Rule -> ObjMultiset . op rhsIn : Rule -> ObjAddressMultiset . op costOf : Rule -> Cost . 90 B. Aman, G. Ciobanu rulesIn : Label -> RuleSet is used to present the rules inside a membrane. We work with register membranes even when implementing message passing and dissolving. This does not modify in any way the semantics. In what follows, all the membranes are register membranes, even when not explicitly stated. A register membrane is constructed through the operator op <_‘[_|_|_|_‘]_>_ : Label ObjMultiset ObjMultiset ObjMultiset ObjAddressMultiset MembraneSet ObjMultiset -> Membrane [ctor] . The first slot is for the label; the second slot is for the objects inside the membrane; the third slot is for the objects with label ”here”; the fourth slot is for the objects with label ”out”; the fifth slot is for the objects with label ”in child”; the sixth slot is for the set of children membranes; the last slot is for the register. The operators which are used to manipulate the components of a rule are op labelOf : Membrane -> Label . ops register here : Membrane -> ObjMultiset . ops content out : MembraneSet -> ObjMultiset . op inChildren : Membrane -> ObjAddressMultiset . op children : Membrane -> MembraneSet . Other operators are _isIn_ which evaluates whether a multiset is contained in another multiset, mprIrred,msgIrred,dissIrred,eraseDelta,emptyOut and emptyReg whose names are self-explaining. We also use labelsOf to gather the membrane labels which appear in the right hand side of a rule, for the same purpose membraneSetLabels with respect to the membrane sets, and subsetOf to compare them. These last three functions are used only when evaluating whether a pair formed of a membrane Mand a rule Ris valid: op valid : Membrane Rule -> Bool . ceq valid(M, R) = true if lhs(R) isIn content(M) /\ promoter(R) isIn (content(M) + register(M)) /\ labelsOf(rhsIn(R)) subsetOf membraneSetLabels(children(M)) /\ if (inhibitor(R) =/= emptyMO) then (inhibitor(R) isIn (content(M) + register(M)) == false) else true fi . eq valid(M, R) = false [owise] . To separate the three stages of evolution of a membrane we use four tags: sorts evolutionType State . ops mpr msg diss end : -> evolutionType [ctor] . op _;_ : MembraneSet evolutionType -> State [ctor] . where end is used to stop the rewriting once the membrane has stopped evolving. The maximal parallel rewriting of a membrane is given by the following rules, where the second one is executed with the cost of the corresponding rule: crl [1] : M , MM ; mpr => M1 , MM ; mpr if MM =/= null /\ M ; mpr => M1 ; mpr /\ M =/= M1 . crl[2]:<L[W1|W2|W3|A]MM>W4;mpr=> < L [ W1 - lhs(R) | W2 + rhsHere(R) | W3 + rhsOut(R) | A + rhsIn(R) ] MM > (W4 + lhs(R) ) ; mpr with cost costOf(R) Verifying P Systems with Costs Using Priced-Timed Maude 91 if mprIrred(MM) /\ R RR := rulesIn(L) /\valid(<L[W1|W2|W3|A]MM>W4,R). crl[3]:<L[W1|W2|W3|A]MM>W4;mpr=> <L[W1|W2|W3|A]MM1>W4;mprif mprIrred(MM) == false /\ MM ; mpr => MM1 ; mpr /\ MM =/= MM1 . These rules impose the following evolution: if in a membrane there is some mprreducible child membrane, then the membrane is replaced by a similar membrane which has that child rewritten (rules crl [3] and crl [1]); if a membrane has only mpr-irreducible children, all valid rules are applied one by one (rule crl [2]). When even the skin membrane is mpr-irreducible, the following rule is applied crl [4] : M ; mpr => emptyReg(M) ; msg if labelOf(M) == 1 /\ mprIrred(M) . in order to empty the register and to begin the next evolution stage, that of the message sending. This message sending stage is governed by the following rules: crl [5] : M , MM ; msg => M1 , MM ; msg if MM =/= null /\ M ; msg => M1 ; msg /\ M =/= M1 . crl[6]:<L[W1|W2|W3|A]MM>W4;msg=>ifL==1then < L [ W1 + W2 + out(MM1) | emptyMO | emptyMO | emptyMAO ] emptyOut(sendIn(A, MM1)) > W4 ; msg else < L [ W1 + W2 + out(MM1) | emptyMO | W3 | emptyMAO ] emptyOut(sendIn(A, MM1)) > W4 ; msg fi if msgIrred(MM) == false /\ MM ; msg => MM1 ; msg /\ msgIrred(MM1) . crl[7]:<L[W1|W2|W3|A]MM>W4;msg=>ifL==1and W3 =/= emptyMO then < L [ W1 + W2 + out(MM) | emptyMO | emptyMO | emptyMAO ] emptyOut(sendIn(A, MM)) > W4;msg else < L [ W1 + W2 + out(MM) | emptyMO | W3 | emptyMAO ] emptyOut(sendIn(A, MM)) > W4 ; msg fi if msgIrred(MM) /\ (A =/= emptyMAO) or (W2 =/= emptyMO) or out(MM) =/= emptyMO . In this stage a membrane evolves in a single rewriting step: if the set MM of children membranes is msg-reducible, then MM rewrites to a msg-irreducible MM1(rule crl [5]); the membrane Mwith objects W1 which contains MM is rewritten to the membrane M1 with objects W1 + W2 + out(MM1) (i.e. the objects with messages of form (a, here) are transformed in objects of form a, and the objects sent out by the set MM1 of membranes are added), and children emptyOut(sendIn(A, MM1)) (i.e. the objects of form (a, inj) are sent into the membrane with label jand then the objects with messages of form (a, out) are erased from every child membrane). The result is msg-irreducible, because the only objects with messages are in the membrane M1, and they are of the form (a, out) (if M1 is the skin not even those objects remain). If the set MM of children membranes is msg-irreducible, then the same process takes place, except that instead of MM1 it is still MM(rule [7]). 92 B. Aman, G. Ciobanu Rules crl [5],crl [6] and crl [7] correspond to inference rules msg1 and msg2 . In defining the transition relation Tmsg we treat the case of an elementary membrane separately, since we prefer to avoid extending Tmsg to sets of membranes. Although rules crl [6] and crl [7] look almost identical, we cannot include them in a single rule with the conditional part if MM ; msg => MM1 ; msg because it would lead to an infinite loop of identical rewritings. This happens because MM;msg →MM;msg is provable in rewriting logic. When the entire membrane system is msg-irreducible, the rule crl [8] : M ; msg => M ; diss if labelOf(M) == 1 /\ msgIrred(M) . is applied. This rule starts the next evolution stage, that of dissolving. The rules for dissolving membranes are: crl [9] : M , MM ; diss => M1 , MM ; diss if MM =/= null /\ M ; diss => M1 ; diss /\ M =/= M1 . crl[10]:<L[W1|W2|W3|A]MM>W4;diss=> < L [ W1 + eraseDelta(content(M)) | W2 | W3 | A ] children(M) , MM1 > W4 ; diss if dissIrred(MM) /\ M , MM2 := MM /\ delta isIn content(M) /\ MM1 := children(M) , MM2 . crl[11]:<L[W1|W2|W3|A]MM>W4;diss=> <L[W1|W2|W3|A]MM1>W4;diss if dissIrred(MM) == false /\ MM ; diss => MM1 ; diss /\ dissIrred(MM1) . If the set MM of children membranes for a membrane Mis diss-reducible and it rewrites to a diss-irreducible set of membranes MM1, then Mis rewritten to the similar membrane M1 which has children membranes MM1 (rules crl [9] and crl [11]). When the set MM of children membranes is diss-irreducible and at least one of the membranes in MM contains the special symbol δ, then all the membranes from MM which contain δare dissolved (rule crl [10]). Note that a top membrane Mdoes not dissolve even when it does contain δ. This happens because the rewriting rules are given with the purpose of describing the evolution of the skin membrane, which can never dissolve. Rules crl [9],crl [10] and crl [11] correspond to inference rules msg1 and msg2. Again, we have used the first rule in this group as a stepping stone towards the rewriting of a set of sibling membranes, while avoiding to include the rewriting of a set of sibling membranes in the transition relation Tdiss. When the skin membrane is diss-irreducible but is mpr-reducible, the rule crl [12] : M ; diss => M ; mpr if labelOf(M) == 1 /\ dissIrred(M) /\ mprIrred(M) == false . is applied; it starts once more the maximal parallel rewriting stage of the evolution. However, if the skin membrane is also mpr-irreducible, rule crl [13] : M ; diss => M ; end if labelOf(M)==1 /\dissIrred(M)/\mprIrred(M). Verifying P Systems with Costs Using Priced-Timed Maude 93 is applied; in this case it ends the rewriting. We do not need to evaluate the msg-irreducibility of the skin membrane, because the dissolving stage can only be reached by msg-irreducible membranes. The correspondence between the operational semantics given by the transition relation ⇒on one hand, and the rewriting logic implementation on the other hand is is given by a mapping ψ:Π→State defined by the natural encoding presented above. By Rwe denote the rewrite theory defined by the rewrite rules [1] . . . [13] together with the operators and equations defining them. The next theorem emphasizes the correspondence between the dynamics of the membrane systems with costs and the rewrite theory. Theorem 1. Mc ⇒Niff RD`ψ(M)⇒∗ψ(N)with cost c. 4 Analyzing and Verifying P Systems With Costs Using the previous operational correspondence provided by Theorem 1, the software experiments done in Priced-Timed Maude reflect exactly the evolution of the encoded membrane systems with costs. In this section we use a simple example of a membrane system with costs, example that is described in rewriting logic in the following form: eq R0 = A -> B | emptyMO | emptyMAO | emptyMO | emptyMO | 10 . eq R1 = A -> C | emptyMO | emptyMAO | emptyMO | emptyMO | 8 . eq R2 = C -> D | emptyMO | emptyMAO | emptyMO | emptyMO | 12 . eq Q = < 1 [ A + A + A | emptyMO | emptyMO | emptyMAO ] null > emptyMO . eq rulesIn(1) = R0 R1 R2 . eqS=Q;mpr. When entering the rewrite command (ptfrew {S} in time <= 0 with cost <= 70 .) Maude presents the following output: Result PricedTimedSystem : {< 1[B + B + B | emptyMO | emptyMO | emptyMAO]null > emptyMO ; end} in time 0 with cost 30 We use priced-time Maude to check if certain configurations of a system can be reached (reachability problem). (ptsearch {S} =>* {X:StateStop} with no limits .) We use the ptsearch command to answer the question: starting from the initial membrane system S, what are the reachable final states (the ones containing the end tag)? This is done by searching for states which match a corresponding pattern. In this example, we use the =>∗symbol, meaning that we are searching for several steps. If one is interested in a bounded number of reachable final states, the command ptsearch[n] can be used to obtain systems reachable in nsteps. In our case, the output is Stern-Gerlach Experiment Maria Arazo1, Marc Barroso1, Óscar De la Torre1, Laura Moreno1, Ariadna Ribes1, Patricia Ribes1, Ana Ventura1, and David Orellana-Martín2 1Universitat de Barcelona Email: {maria.arazo, marc.barroso4, oscar.delatorre.perez, 95morenolaura, aribesmetidieri, ribesmetidieri, a.venturabarroso}@gmail.com 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla E-mail: [email protected] Summary. This work is about modelling an experiment composed by multiple Stern- Gerlach devices using Membrane Computing. We will study the behaviour of a set of independent particles passing through three linked Stern-Gerlach devices and discarting the spin down particles after passing through the first one, taking profit of the Membrane Computing’s ability of running parallel processing. Using a cell-like model to describe the system and testing it using the P-lingua framework we have obtained the theorically predicted results when the number of initial multisets is high enough. 1Introduction In 1998 Gheorghe Păun introduced an alternative computing science paradigm, Membrane Computing (MC from now on) [ 4 ]. P-systems appeared, and with it, an innovative way to interpret the natural world. Those models are based on the structure of living cells and how they process compounds within their membranes (cell-like system) or even how they interact one with the others (tissue-like system). To model the processes occurring inside them, they make use of rules, which represent the different reactions or exchanges of the objects inside or through the membranes. Those rules can be of several types: communication, rewriting, annihilation, etc. For years, they have been applied to study the evolution of biological systems, neuronal systems or even complex ecosystems. Nevertheless, the application of Membrane Computing paradigms in other fields has not been yet so promoted. Therefore, one of the aims of this project is to extend the Membrane Computing applicability to physics. Moreover, this article has been used as a excuse in order to learn about this new computing paradigm and to be able to seek for possible further applications. 102 Arazo, Barroso, De la Torre, Moreno, A. Ribes, P. Ribes, Ventura, Orellana 1.1Combining MC with Physics When studying Physics the aim is not to know exactly what things are, but to understand how they behave, this is the reason why it is so important to model natural phenomena. The modelling process’ goal is to attain a set of analytical expressions that describes the studied system reduced into a determined approximation. Because of the complexity of those analytical expressions, it is commonly useful to solve them with numerical methods. When dealing with a great number of particles, even with n→ ∞ , being n the number of particles, the computation time could become large enough that it would turn inefficient (to use certain numerical methods). Here is where Membrane Computing provides a really suitable framework, due to maximal parallelism, one of MC’s main features. Membrane Computing is originally based in a model analogous to cells and tissues. Because of that, it could fit perfectly in a system of discrete particles. By making the analogy with the structure provided by MC, one could identify particles with the objects, whereas rules applied in each membrane enable us to model particles’ behaviour. It is also a useful tool when working with problems involving non-deterministic processes, i.e. those that can be found in modern physics, such as quantum mechanics or nuclear physics, where probabilities play an important role. 1.2Introduction to Quantum Mechanics For many years, the world was ruled by Classical Mechanics, which considered that all processes occurred in a deterministic way, i.e. one could predict the position and momentum of any particle at the same time. It was not until 1900, when Max Planck published his paper [ 6 ], that new phenomena which did not coincide with classical physics stopped seeming unwarranted, then quantum physics was borned. Quantum Mechanics is a fundamental branch of Physics that explains the behaviour of subatomic particles and it is grounded on the idea that measurable observables are discrete and quantified. In Quantum Mechanics, the mathematical formalism is based on the Hilbert space, hence the Quantum world is described by six postulates, whereas the evolution of the body’s movement in classical mechanics is ruled by Newton’s Law. Postulate 1.On the representation of the state of a physical system. The maximum possible information on a physical system at a given time t is its quantum state ψ , which is represented as a vector |ψi of unitary module and arbitrary phase in a separable Hilbert space. Postulate 2.On the representation of measurable magnitudes. Every measurable magnitude of the system has associated a linear and autoadjoint operator defined on the vector space of the states. The totality of the eigenvalues is the spectrum, and the eigenvectors define a base on the Hilbert space. Postulate 3.On the result of the measure. The result of measuring the observable A is one of its eigenvalues ai of the spectrum, the probability of obtaining the result aiis given by: Stern-Gerlach Experiment 103 P(ai) ψ=|hai|ψi|2 Postulate 4.On the collapse or reduction of the wave function. Immediately after measuring the observable A with result ai , the new state of the system is |aii, i.e. the corresponding eigenvector. Postulate 5.On the temporal evolution. Between measures, the system evolves according to the Schrödinger equation: i¯hd dt|ψ(t)i=H(t)|ψ(t)i Where His the Hamiltonian of the system. Postulate 6.On the Pauli exclusion principle. The position and momentum operators for fermions satisfy commutative rules that are directly related to the Pauli exclusion principle, i.e. that two fermions cannot have the same quantum numbers. 2Stern-Gerlach experiment 2.1The basic Stern-Gerlach experiment The Stern-Gerlach experiment [ 3 ] is used to illustrate that particles have intrinsic properties such as the spin, the orbital momentum, etc. The total momentum of a particle is the composition of the orbital momentum and the spin, being the last one the observable that is measured by the Stern-Gerlach device. In particular, we focus the study on the third component of the spin that it is discrete and quantifiable, and can only take the values (i.e. eigenvalues) +¯h 2 (denoted as up to simplify notation) or −¯h 2(down). The basic Stern-Gerlach experiment is composed by a magnet that creates a non-uniform magnetic field oriented towards a general direction ˆn that is contained in the plain surface perpendicular to the particle’s direction of propagation (the y axis in Figure 1). Once the particle has passed through the magnetic field, the third component of the spin may have changed. In the particular case of a Stern-Gerlach (device) oriented towards the z axis (i.e. the magnetic field too), the third component of the spin is measured after the particles passes through. While in a more general case (where ˆn is a general direction as mentioned above), the measured magnitude is the projection of the spin in that arbitrary direction. 2.2The experiment modelled with MC The modelled experiment consists on three Stern-Gerlach devices situated along the x axis, and a set of particles that go through the three of them and impact 104 Arazo, Barroso, De la Torre, Moreno, A. Ribes, P. Ribes, Ventura, Orellana on a screen. Initially, the incident particles have an undetermined state, i.e. the third component of the spin may be positive or negative and unknown unless it is explicitly measured. The first Stern-Gerlach, which is ˆz -oriented, defines the third component of the spin with a fifty percent of probability of being either positive (or up , to simplify notation), or negative ( down ). Then, once a particle with non-determined spin goes through the first Stern-Gerlach device, which in Figure 2is labelled as SG1 , the spin-state of the particle becomes determined. This is what we define as the initial state for the other two Stern-Gerlach devices. Since we are considering an arbitrary number n of incident particles, after this step we would obtain 50% particles with third component of the spin up and 50% down if nis large enough. S N y x z x z up down Fig. 1: Original Stern-Gerlach experiment, with the magnet parallel to the ˆz axis so the zcomponent of the spin is measured. For the second Stern-Gerlach device, we discard the particles with initial spin down and make the up -particles go through the magnet (labelled as SG2 ), oriented with an arbitrary angle θ as shown in Figure 2. In this general case, the probabilities of obtaining spin up or spin down do not only depend on the initial state of the particle (now restrained to up ), but also on the angle θ between the Stern-Gerlach device and the zaxis. Those probabilities are derived on the following lines. For ˆn= sinθˆı+ cosθˆ k the direction of the Stern-Gerlach device and σ= σxˆı+σyˆ+σzˆ ka general vector for the Pauli matrices3, the associated matrix is 3 The Pauli matrices are the most general hermitic matrices of dimension 2×2 with eigenvalues 1and −1, and are defined as: σx=0 1 1 0σy=0−i i0σz=1 0 0−1 With eigenvalues 1and −1and the corresponding eigenvectors: Stern-Gerlach Experiment 105 non-defined spin spin up y x z x SG 1 initial state z SG 2 SG 3 θ up down Fig. 2: Three Stern-Gerlach devices as proposed in this article ˆnσ=cosθsin θ sinθ−cosθ Given that the eigenvalues are +1 and −1 as in the Pauli matrices, and imposing that the corresponding eigenvectors generalised as (α β) should be normal and therefore satisfy that |α|2+|β|2= 1, the eigenvectors found are: |ˆnσ= +1i=cosθ/2 sinθ/2 |ˆnσ=−1i=−sinθ/2 cosθ/2 And the probabilities 4 of obtaining spin up or down for a particle with initial up state5are defined by: |σx= +1i=1 √21 1|σx=−1i=1 √21 −1 |σy= +1i=1 √21 i|σy=−1i=1 √21 −i |σz= +1i=1 0|σz=−1i=0 1 4 More on notation: the first subscript refers to the initial state, and the second one to the final state, so P↑↓ is the probability of obtaining down spin given a particle with initial spin up. 5Notation for the initial states up or down: 106 Arazo, Barroso, De la Torre, Moreno, A. Ribes, P. Ribes, Ventura, Orellana P↑↑ =|hˆnσ= +1|+i|2=cosθ/2sin θ/21 0 2 = cos2θ 2 P↑↓ =|hˆnσ=−1|+i|2=−sinθ/2cos θ/21 0 2 = sin2θ 2 Following that same procedure, the probabilities for initial down state particles are: P↓↑ =|hˆnσ= +1| −i|2=cosθ/2sin θ/20 1 2 = sin2θ 2 P↓↓ =|hˆnσ=−1| −i|2=−sinθ/2cos θ/20 1 2 = cos2θ 2 Finally, the particles will pass through the last SG device ( SG3 ), which is oriented on the z axis and therefore allows us to measure the third component of the spin 6 and count how many particles have as final state spin up or spin down . This result, though redundant, shows one of the most important facts of Quantum Mechanics: that measure alters the system. As we can observe here, though we considered only the up -particles to go through the second Stern-Gerlach, on the final state (i.e. the screen) we have recovered the initial distribution of fifty percent of particles up and fifty percent down . See Figure 3for an scheme of the proposed experiment. SG 1 SG 2 SG 3 u d Block +u d θ n· P↑↑ n· P↑↓ − Defining the initial state Determine n· P↑↑ and n· P↑↓, in agreement with their probabilities Fig. 3: Schematic description of the proposed experiment 3P-system model 3.1PDP systems P systems [ 2 ] [ 5 ] are an abstraction of the membrane structure inside a cell, which delimite regions containing objects that can evolve acording to certain rules. In up:|↑i =|+i=1 0down:|↓i =|−i =0 1 6 As a reminder, the Stern-Gerlach device basically measures the projection of the spin in the direction that it is oriented, i.e. a ˆz -SG measures the third component Sz and so on. Stern-Gerlach Experiment 107 general, the dynamic of those systems is defined through a non-deterministic and synchronised mode. Population Dyanmics P systems (PDP) models are a complex variant of P systems, as they consider a collection of environments, each containing a cell (all of them with the same membrane structure and rules) connected among them as a network. Also, in those models, rules are associated with probabilistic functions and membranes with polarizations. All these ingredients make PDP systems a useful computational tool to model complex systems. On this articles, we focus on a reduced version of PDP systems as no envrionment and polarizations are needed. What follows are the main aspects. We define a probabilistic P system as a tuple Π= (Γ, µ, M1,...,Mq, R, {fr|r∈R}) where: •Γ is a finite set, not empty, called alphabet, whose elements are named objects of Π. The whole of all finite multisets over Γis denoted by MF(Γ). •µ is a tree structure, labelled by {i|1≤i≤q} , that describes the membranes’ structure. The skin membrane (also named as tree root) is the only one labelled by 1. •Mi∈MF (Γ),1≤i≤q, is the initial multiset of objects associated to cell i. •R is a finite set of evolution rules of the form: u[v]i→u0[v0]i , where u, v, u0, v0∈ MF (Γ) , 1≤i≤q , and |u|+|v| 6= 0 . With u[v]i being the left-hand side of the rule. • For each r∈R, fr∈[0,1] , describes the probability distribution over the rules with a same left-hand side. Then Prfr= 1 for all the the rules in R whose left-hand side is equal. A rule r∈R of the form u[v]i→u0[v0]i can be applied within a membrane labelled i if it contains v and its parent membrane contains u . If a rule of this kind is applied, objects in v and u vanish from membrane i and its parent. Simultaneously, objects in v0and u0are included in membrane iand its parent, respectively. A configuration for any unit time is a tuple that specifies the multisets of objects that can be found in each membrane. In every step of time, rules applied are chosen in a non-deterministic way depending on its left-hand side, taking into account the probability associated to each of them. A maximal number of rules are applied simultaneously. Computation is a succession of configurations such that the first one coincides with the initial configuration and every of the remaining are obtained from the former using the rules of the system as it has been described above. 3.2Model In order to test the designed system we have define it for the simulator given by the P-lingua framework, using a single cell with two inner membranes. Given n as the number of particles we want to do the experiment with, we put an object a (in 108 Arazo, Barroso, De la Torre, Moreno, A. Ribes, P. Ribes, Ventura, Orellana membrane 2)ntimes, i.e., anwould be the input multiset. Let ΠSG = (Γ, µ, M1,M2,M3, R, {fr|r∈R}), where: •Γ={a, u, d}is the alphabet we use for this multiset. •µ= [[ ]2[ ]3]1is the structure of the membranes. •Mi=∅, i ∈ {1,3}. •M2=an. •The set of rules R, each rule with its corresponding probability, is: (a) These rules take care of the initial state spin of the particles that is determined by the first Stern Gerlach device. The particles with spin down are blocked. r1≡[a]2 1/2 −−→ [d]2 r2≡[a]2 1/2 −−→ u[ ]2 (b) Here, we simulate the particles passing through the second and third Stern Gerlach devices. The spin of the particles is determined according to a probability given by the angle of the magnetic field of the second Stern Gerlach with the ˆz axis. The third Stern Gerlach is simulated by introducing the particles with definite spin within the membrane with label 3, where the results are collected. r3≡u[ ]3 cos2(θ/2) −−−−−−→ [u]3, r4≡u[ ]3 1−cos2(θ/2) −−−−−−−−→ [d]3, an [a]2 1/2 −−→ [d]2 [a]2 1/2 −−→ u[ ]2 u[ ]3 1−cos2(θ/2) −−−−−−−−→ [d]3 u[ ]3 cos2(θ/2) −−−−−−→ [u]3 1 2 3 Fig. 4: Visual representation of our P-system Stern-Gerlach Experiment 109 4Code @model<probabilistic> def Sg(@cos(theta / 2)) { @mu = [[]’2[]’3]’1; /* Rules in membrane 2*/ /* Here, we determine the initial state of the particle by blocking the particles with down spin, which remain in the region 2*/ [a]’2--> [d]’2:: 0.5; [a]’2--> u[]’2:: 0.5; /* Rules in membrane 3*/ /* Implementation of the second Stern Gerlach 2and 3*/ u[]’3--> [u]’3:: @cos(theta / 2) * @cos(theta / 2); u[]’3--> [d]’3:: 1-@cos(theta / 2) * @cos(theta / 2); } def main() { call Sg(@cos(theta / 2)); @ms(2) = a*1000; } /* End of main module */ 116 Arazo, Barroso, De la Torre, Moreno, A. Ribes, P. Ribes, Ventura, Orellana 2.2U-238 decay chain As we can see in Table 1, the Uranium decay chain consists of 15 main steps (i.e. decay reactions). This table shows the most probable decay modes, but there are other decays with an extremely low probability of occurring, showed with more detail in the second part of Table 1. Nevertheless, independently from the path chosen, the final product is always lead (Pb-206), which is stable. A diagram of the whole U-238 decay chain and its less probable decay modes can be found in Figure 1. Uranium-238 decay chain 117 Parent T1/2(s) λ(decays/s) τ(s) Decay modes Reaction fr,1 238 92 U (a)1.41 ×1017 4.92 ×10−18 2.03 ×1017 α(100%): 234 90 Th [a]0→x[b]09.68 ×10−1 234 90 Th (b)2.08 ×1063.33 ×10−73.00 ×106β−(100%): 234 91 Pa [b]0→z[c]05.33 ×10−1 234 91 Pa (c)2.41 ×1042.87 ×10−53.48 ×104β−(100%): 234 92 U[c]0→z[d]06.22 ×10−1 234 92 U (d)7.74 ×1012 8.95 ×10−14 1.12 ×1013 α(100%): 230 90 Th [d]0→x[e]02.29 ×10−1 230 90 Th (e)2.38 ×1012 2.92 ×10−13 3.43 ×1012 α(100%): 226 88 Ra [e]0→x[f]02.53 ×10−1 226 88 Ra (f)5.05 ×1010 1.37 ×10−11 7.28 ×1010 α(100%): 222 86 Rn [f]0→x[g]03.30 ×10−1 222 86 Rn (g)3.30 ×1052.10 ×10−64.77 ×105α(100%): 218 84 Po [g]0→x[h]05.70 ×10−1 218 84 Po (h)1.86 ×1023.73 ×10−32.68 ×102α(99.98%): 214 82 Pb β−(0.02%): 218 85 At [h]0→x[v]0 [h]0→z[j]0 7.20 ×10−1 1.44 ×10−4 214 82 Pb (v)1.62 ×1034.27 ×10−42.34 ×103β−(100%): 214 83 Bi [v]0→z[k]06.77 ×10−1 214 83 Bi (k)1.19 ×1035.81 ×10−41.72 ×103β−(99.979%): 214 84 Po α(0.021%): 210 81 Tl [k]0→x[n]0 [k]0→z[m]0 1.43 ×10−4 6.83 ×10−1 214 84 Po (m)1.64 ×10−44.22 ×1032.37 ×10−4α(100%): 210 82 Pb [m]0→x[p]01.00 ×100 210 82 Pb (p)7.00 ×1089.90 ×10−10 1.01 ×109β−(100%): 210 83 Bi α(1.9×10−6%): 206 80 Hg [p]0→x[o]0 [p]0→z[q]0 7.90 ×10−9 4.16 ×10−1 210 83 Bi (q)4.33 ×1051.60 ×10−66.25 ×105β−(100%): 210 84 Po α(13.2×10−5%): 206 81 Tl [q]0→x[s]0 [q]0→z[r]0 7.45 ×10−7 5.64 ×10−1 210 84 Po (r)1.20 ×1075.80 ×10−81.72 ×107α(100%): 206 82 Pb [r]0→x[t]04.98 ×10−1 206 82 Pb (t) Stable — — — — — Other (less probable) decays 218 85 At (j)1.50 4.62 ×10−12.16 α(99.9%): 214 83 Bi β−(0.1%): 218 86 Rn [j]0→x[k]0 [j]0→z[l]0 8.16 ×10−1 8.17 ×10−4 218 86 Rn (l)3.50 ×10−21.98 ×1015.05 ×10−2α(100%): 214 84 Po [l]0→x[m]08.92 ×10−1 210 81 Tl (n)7.80 ×1018.89 ×10−31.13 ×102β−(100%): 210 82 Pb [n]0→z[p]07.38 ×10−1 206 80 Hg (o)4.99 ×1021.39 ×10−37.20 ×102β−(100%): 206 81 Tl [o]0→z[s]07.00 ×10−1 206 81 Tl (s)2.52 ×1022.75 ×10−33.64 ×102β−(100%): 206 82 Pb [r]0→x[t]04.98 ×10−1 Table 1: Half-life times, decay constants, mean lifetimes, decay modes, reaction and probability functions for each reaction in the U-238 decay chain. The letter in brackets corresponds to the letter assigned to each nucleus for implementation. Half-lifes and probabilities for the chain decays obtained from [ 3 ] [ 5 ]; probabilities for the less probable decays obtained from [ 4 ]. The probability function associated to each transformation rule depends on the decay constant and the decay mode probability. 118 Arazo, Barroso, De la Torre, Moreno, A. Ribes, P. Ribes, Ventura, Orellana 238 92 U 234 90 Th 234 91 Pa 234 92 U 230 90 Th 226 88 Ra 222 86 Rn 218 84 Po 218 85 At 218 86 Rn 214 82 Pb 214 83 Bi 214 84 Po 210 81 Tl 210 82 Pb 210 83 Bi 210 84 Po 206 80 Hg 206 81 Tl 206 82 Pb α β−β− α α α α α β− β−β− αα β− α β− αα α β− α β− β−β− Fig. 1: Uranium decay chain. Uranium-238 decay chain 119 3P-system model Population Dynamics P systems (PDP systems) [ 1 ] are a kind of P systems that combines the characteristics of both cell-like and tissue-like models. A PDP system is constituted by (i) a set of connected environments placed in the nodes of a directed graph (ii) identical cell-like structures of hierarchically arranged membranes placed inside each environment, (iii) a working alphabet of objects and (iv) a set of rules which describe how objects evolve and move inside the P systems ( R ) and among the environments (Rε). Formally, a Population Dynamics P system of degree ( q , m ) with q, m ≥1 , taking Ttime units, T≥1, is a tuple (G, Γ, Σ, T, Rε, µ, R,{fr,j :r∈ R,1≤j≤m},{Mij : 1 ≤i≤q, 1≤j≤m}) (5) where: •G= (V, S) is a directed graph and V={e1, . . . , em} are the elements called environments. •Γ∪Σis the working alphabet. •Tis a natural number that represents the simulation time of the system. •Rεis a set of communication rules between environments of the form (x)ej p(x,j,j1,...,jh) −−−−−−−−−→ (y1)ej1· · · (yh)ejh (6) where x, y1,· · · yh∈Γ, (ej, ejl)∈S(l= 1, . . . , h) and p(x,j,j1,...,jh)(t)∈[0,1] , for each t= 1,...T. The previous definition means that, when a communication rule is applied, object x contained in environment ej passes to environments ej1. . . ejh , possibly modified into objects y1,...yh . If more than one rule can be applied to (x)ej , then the rule executed is chosen randomly according to the probabilities p(x, j, j1, ..., jh). •µ is the membrane structure of the cells contained in each of the m environments and each consisting on a set of q hierarchically arranged membranes injectively labeled by 1,...q . The skin membrane, or outer membrane is labeled by 1. The membranes can also have electrical charges or polarizations, EC ={0,+,−}. •R is a set of evolution rules applied within each cell. They are of the form r:u[v]α i→u0[v0]α0 iwhere u, v, u0, v0∈M(Γ),i∈1,...q, and α0∈EC. • For each r∈ R and for each j, 1≤j≤m , fr,j is a computable function which satisfies that, for each u, v ∈M(Γ) all the rules r∈ R whose left-hand side is (i, α, u, v) and the right-hand side have a polarization α0 , Pj=1 fr,j(t)=1 ∀t≤T. •M1j,...,Mqj ∈M(Γ) are the initial multisets of objects for environments j= 1,...m placed inside the membranes 1,...q of µ. The tuple of multisets of objects present at any moment in the m environments and at each of the regions of the P systems (cell-like structures) constitutes the a 120 Arazo, Barroso, De la Torre, Moreno, A. Ribes, P. Ribes, Ventura, Orellana configuration of the system at any time. At the initial configuration of the system, all environments are assumed to be empty and all the membranes have neutral polarization. The system evolves from one configuration to another at each time step by executing simultaneously all the applicable rules of the set R=Rε∪Sm i=1 RΠj 3 in a maximal way. When there are rules acting on overlapping left-hand sides, i.e. u[v]α i , u0[v0]α i where u, u0, v, v0∈M(Γ) , u6=u0∨v6=v0 and u∩u06=∅ ∨ v∩v06=∅ , the rule which is executed is selected randomly according to the probability associated with each rule. Finally, it is interesting to highlight the fact that a global clock is considered in the system, marking the time for the whole system, so the application of all rules (both from Rεand R) are synchronized in all environments. 3Πj={Γ, µ, R,M1j,...,Mqj} denotes the P system in environment ej and RΠj , the set of rules defined on the considered P system. Uranium-238 decay chain 121 2,2 3,24,2 b5a2 a6 2,1 3,1 [ab]1→a2b[ ]1 [a]2 0,2 −−→ b[ ]2 [a]2 0,8 −−→ a[a]2 [ab]1→a2b[ ]1 [a]2 0,2 −−→ b[ ]2 [a]2 0,8 −−→ a[a]2 1,1 1,3 2,3 b7a5 [ab]1→a2b[ ]1 [a]2 0,2 −−→ b[ ]2 [a]2 0,8 −−→ a[a]2 b7a5 1,2 2,2 3,2 a5 a3b3 b4a2 (a)2 0,25 −−→ (b)1 (a)2 0,75 −−→ (a)1 (a)2 0,5 −−→ (a)3 (ab2)3→(a2)1 (ab)3→(b)2 (a)2 0,5 −−→ (b)3 3,3 Fig. 2: A graphical example of a PDP system 4Implementation 4.1First model The Step of time model is the simplest possible modelization of the Uranium decay problem, as it characterizes the half-lifetime, the characteristic time parameter, of the nuclear reactions using the clock steps of time defined in the membrane computing model. This first rought approximation is based on two assumptions: • The nuclear reaction of a given element cannot begin until all the progenitor nuclei of this element have reacted. • The duration of each reaction can be represented assigning different clock steps to every reaction. 122 Arazo, Barroso, De la Torre, Moreno, A. Ribes, P. Ribes, Ventura, Orellana The timescale of the reactions (characterized by the half-lifetime, T1/2 ) involved in the network of nuclear reactions is huge, varying 21 orders of magnitude: the T1/2 of the fastest reaction is of about ≈10−4 s while for the slowest T1/2≈1017 s. In order to translate the half-lifetime of each reaction to a number of clock iterations, a logarithmic scale is considered. The number of clock iterations is therefore calculated assigning a scaled integer number to each reaction according to the “weight” of time for each reaction. The implementation of this model is done therefore in a single cell-like membrane through rules of the type [ai→ai+1 1≤i≤7]1 [a8→b1, z]1 [bi→bi+1 1≤i≤4]1 [b5→c1, x, y]1 when there’s a single via decay or [hi−−−−→ hi+1 1≤i≤3]1 [h4 99,98% −−−−→ v1, z]1 [h4 0,02% −−−−→ j1, x, y]1 when competition rules are considered. The letter assignation is specified at Table 1, as it is the same as the one used in the probabilistic model. x, y and z represent α particles, e− (electrons) and νe (electron antineutrino). As can be seen, after seven clock steps of computation the nuclei a decays into b . The nuclei b then waits 4steps of computation before evolving. When competition rules apply, the nuclei h also waits a given number of computations after evolving according to a given probability. Although it is not being a model really close to the real situation, with it one could obtain the results expected. The main application of the Steps of time model is then, to obtain the number of nuclei and particles of each kind once the process has ended, taking into account that some nuclei can decay by different vias according to a given probability. However, it cannot predict the number of nuclei of each kind after a given amount of time. The representation of the model is staggered-like, so it doesn’t represent a continuous and soft process and therefore the approximation is not accurate. To sum up, the biggest disadvantage in this modelization was that the next step in the chain had to wait until the previous one had finished completely. Therefore, although the simulation which implemented these rules approached reasonably the amount of particles gathered at the end of the process, it wasn’t a good approach to reality, as in a real decay several reactions of the chain take place at the same time. Uranium-238 decay chain 123 4.2Second model In order to implement the experiment of the Uranium Decay using the framework of Membrane Computing, it has been chosen the PDP system model restricted to a single environment containing a membrane structure composed by a sole membrane of neutral polarization α= 0, so the system can be described as a P system Π1= (Γ={a, b...z}, µ = [ ],R={r1,i, i = 1, ..., 38},M1,q=1 =an) Within this membrane, different objects, which represent the intermediate products in the decay chain, evolve in each step of the computation using PDP evolution rules of the type described in the previous section. The alphabet of objects Γ is composed by all the intermediate products described in Table 1. A letter has been associated to each decay product in order to enable an easier modeling of the problem. As discussed in section 2, each decay mode α or β− generates a different kind of particles, which also have a letter associated ( x for α particles and z for particles generated in β− decay), so the total number of particles obtained from the α and β− decay can be accounted at the end of the computation. In order to model the smooth and continuous decay of every specie in time, competition rules have been considered. For example, given the first reaction, the decay of U238 92 into T h234 90 through the αmode. [a]1 1−fa −−−→ [a]1 [a]1 fa −→ x[b]1 where a and b are the letters associated to U238 92 and Th234 90 respectively. The rule applied will be chosen taking into account the probability associated with it, denoted by fa,1≡fa . From this it can be seen why it is so important that the probability sums up to 1. The decay of a into b takes place through the α decay mode, so a second product x(αparticle) is generated outside the membrane. 124 Arazo, Barroso, De la Torre, Moreno, A. Ribes, P. Ribes, Ventura, Orellana an 0 an [a]0 1−fa −−−→ [a]0 [a]0 fa −→ x[b]0 [b]0 1−fb −−−→ [b]0 [b]0 fb −→ z[c]0 [c]0 1−fc −−−→ [c]0 [c]0 fc −→ z[d]0 [d]0 1−fd −−−→ [d]0 [d]0 fd −→ x[e]0 [e]0 1−fe −−−→ [e]0 [e]0 fe −→ x[f]0 [f]0 fg −→ x[g]0 [f]0 1−ff −−−→ [f]0 [g]0 1−fg −−−→ [g]0 [g]0 fg −→ x[h]0 [h]0 1−fh −−−→ [h]0 [h]0 fhpα h −−−→ x[v]0 [h]0 fhpβ h −−−→ z[j]0 [v]0 fv −→ z[k]0 [v]0 1−fv −−−→ [v]0 [j]0 1−fj −−−→ [j]0 [j]0 fjpα j −−−→ x[k]0 [j]0 fjpβ j −−−→ z[l]0 [k]0 1−fk −−−→ [k]0 [k]0 fkpα k −−−→ x[n]0 [k]0 fkpβ k −−−→ z[m]0 [l]0 1−fl −−−→ [l]0 [l]0 fl −→ x[m]0 [n]0 1−fn −−−→ [n]0 [n]0 fn −→ z[p]0 [m]0 1−fm −−−−→ [m]0 [m]0 fm −−→ x[p]0 [p]0 1−fp −−−→ [p]0 [p]0 fppα p −−−→ x[o]0 [p]0 fppβ p −−−→ z[q]0 [o]0 1−fo −−−→ [o]0 [o]0 fo −→ z[s]0 [q]0 1−fq −−−→ [q]0 [q]0 fqpα q −−−→ x[s]0 [q]0 fqpβ q −−−→ x[s]0 [s]0 1−fs −−−→ z[t]0 [s]0 fs −→ z[t]0 [r]0 1−fr −−−→ [r]0 [r]0 fr −→ x[t]0 Fig. 3: Implementation of the model with the rules applied As λ is a physical parameter constant in time and characteristic of each reaction, it has proved to be the most suitable magnitude to compute the the probability functions fr,1 . The functions fr,1 have been calculated as the normalized logarithm of the scaled (>1)λ’s. The most significant difficulty in the assignation of fr,1 to every transformation rule consisted on the great order of magnitude of the times of decay of the different reagents, as λ∈[5·1018,5·10−3] decays/s (nearly 21 orders of magnitude). Moreover, in other to compute the probabilities of each reaction, λ needed to be dimensionless and normalized in such a way that the probabilities of the rules with the same left-hand objects sum up to 1. Uranium-238 decay chain 125 In order to solve these problems, some assumptions and approximations have been made. First of all, all values of λ in Table 1have been divided between the order of magnitude of minimum λ . This way, we ensure that when the logarithm is applied the numbers will always be positive (as λ λmin >1 ), as well as granting that in logarithm scale, the order of the numbers is not changed. As have been mentioned, having such a great range of λ is truly inconvenient for doing the computations, so the rough solution that has been found consists in applying logarithms to the dimensionless quotient λ λmin . In other to obtain a global probability, which assigns probability equal to one to the rule with the greatest chance to occur, log(r) is divided by log(r)max for every rule. When the decay mode is not unique, this function is also multiplied by the probability of occurrence pγ r , with γ={α, β} representing the possible decay modes. The method used for obtaining fr,1 explained above, assigns a probability to the evolving transformation rules, which transforms a reactive into a different object. As has been explained in section 3, the sum of all probabilities applied over the same left-hand object must be one. As a consequence, the probability of occurrence of the non-evolution transformation rule r : [a]0 1−fr,1 −−−−→ [a]1 has been computed as 1−fr,1. The rules start applying when at least one object of the left-hand side of a rule is generated and continue applying until all this kind of objects are consumed. So, as more intermediate products are generated, more reagents begin to evolve in each computation step, so after a given number of time steps several products of the decay chain will be evolving at the same time (modeled as discrete clock steps in the computation). In this manner, the dependence of the decay in the abundances of each reactive has been roughly simulated in a first approximation. Moreover, the problem of the first model, when a reactive couldn’t begin to evolve until all reagents of the previous decay have been consumed has been solved. It’s necessary to notice that although this model approximates better the decay as a continuous process, the steps of time are still discrete, represented by each computation step. 5Code @model<probabilistic> def main() { @mu=[]’1; @ms(1) = a*500000; [a]’1--> [a]’1:: 0.968; [a]’1--> x[b]’1:: 0.032; [b]’1--> [b]’1:: 0.467 ; [b]’1--> z[c]’1:: 0.533 ; 132 Marc Barroso Mancha It is also necessary to explain how the rules work. The most general form is: α /ac→(t1, ak1, β1), ..., (tm, akm, βm) such that α, βj∈Q (2) that just means that when the state of the given neuron is α, and if the neuron has exactly cobjects ‘a’ inside, it should send kjspikes to the neuron tj, while also transmitting the state βj, for 1 ≤j≤m. When multiple rules are applied into the same neuron in the same clock tick (i.e. different states are transmitted to the same neuron σi), the function fidictates how they should be combined to obtain a unique final state. 2 Cellular automata A cellular automata is defined as a grid of cells, such as every cell can be in one of a finite number of states. The set of cells next to each one it’s called its neighborhood. Then, at every generation, some fixed rules determine the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. One of the most important applications is the known as “Conway’s Game of Life”, originally created by the mathematician John Conway in 1970. Its importance is due to the fact that it can be proven to be a universal Turing machine (that is, anything that can be computed algorithmically can be computed within Conway’s Game of Life - even the Game of Life itself!). Rudolf Freund and Sergiu Ivanov show in their presentation “Extended SNP Systems with States” that the ESNP with transmittable states is analogue to a cellular automata (with the only change we are going to do is talk about neurons instead of cells). More specifically, when only two states are considered, there is an easy set of rules that enables us to simulate the Game of Life. Thus, they showed that we can obtain universality with only two states in the ESNP paradigm. The description of such system can be found on their presentation. 3 Simple nuclear chain reaction model In order to implement these ideas into something more tangible, we can think of the following situation: we have an organized grid of atoms (represented by the neurons), where all of them are stable (in the sense that no rules could be applied initially, that is, the system would halt immediately). In the position (i, j) we introduce an unstable atom that will explode in one clock tick, releasing nnumber of particles (represented by the objects), that will go to any of its neighbors, making them unstable, and thus propagating some kind of state (generating the chain reaction). This is known as a two dimensional random walk. Some attractive On the cellular automata P systems and chain reactions 133 studies can consist of varying the number of objects an explosion yields, observing whether the reaction consume all the possible atoms or not (if an atom that has already exploded is considered to be destroyed insted of being replaced), or considering some time of interaction in every step. Another interesting behavior (also more difficult to implement) would be trying to change the geometry of the system (so the number of neighbors could vary from atom to atom), and see if you could get more efficiency some way or another. This is obviously the first iteration of the model one can think of: further complications can be considered, as making the grid in 3D (just by adding layers upon layers of atoms), or even trying to add probabilities so further atoms than the more direct neighbors have a chance of becoming unstable. This model can be used to simulate the path of a photon that emerges from the Sun’s core and is trying to reach the surface. A very simple model has been implemented at what aims to be an ESNP simulator, programmed in Python. It consists of a square grid of arbitrary dimensions, and an unstable atom in the middle. The initial reaction lasts two ticks, and send one spike in two random different directions. For the sake of simplicity, we have used three different states: 0 - stable atom, 1 - unstable atom, 2 - already exploded atom, even if two were already enough, as explained before. We understand that this model has some difficulties (we only used the most direct neighbors; this can be extended to have probabilities for all 8 adjoin neurons), and can even be too simplified (we know that atoms won’t be organized in a rectangular grid, as shown here, but will have some kind of spatial distribution). But while modeling this problem, we found out that this could also be implemented as some kind of A∗path-finding algorithm or some kind of path algorithm, only halting the computation when a certain point is reached or if no rules have been applied, and then letting a lot of systems run in parallel. With a comparison between the number of rules used, one can actually get a good representation of the optimal route. Could we explot from the fact that we can acces more states and take advantage of it, working under the P-systems paradigm? Further research and modeling must be done to answer this. Improving Simulations of Spiking Neural P Systems in NVIDIA CUDA GPUs: CuSNP 1Jym Paul Carandang, 1John Matthew B. Villaflores, 1Francis George C. Cabarle, 1Henry N. Adorna, 2Miguel ´ Angel Mart´ınez-del-Amor 1Algorithms and Complexity Department of Computer Science University of the Philippines Diliman Diliman 1101 Quezon City, Philippines; email: [email protected], [email protected], [email protected] [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected] Summary. Spiking neural P systems (in short, SN P systems) are parallel models of computations inspired by the spiking (firing) of biological neurons. In SN P systems, neurons function as spike processors and are placed on nodes of a directed graph. Synapses, the connections between neurons, are represented by arcs or directed endges in the graph. Not only do SN P systems have parallel semantics (i.e. neurons operate in parallel), but their structure as directed graphs allow them to be represented as vectors or matrices. Such representations allow the use of linear algebra operations for simulating the evolution of the system configurations, i.e. computations. In this work, we continue the implementations of SN P systems with delays, i.e. a delay is associated with the sending of a spike from a neuron to its neighbouring neurons. Our implementation is based on a modified representation of SN P systems as vectors and matrices for SN P systems without delays. We us massively parallel processors known as graphics processing units (in short, GPUs) from NVIDIA. For experimental validation, we use SN P systems implementing generalized sorting networks. We report a speedup, i.e. the ratio between the running time of the sequential over the parallel simulator, of up to approximately 51 times for a 512-size input to the sorting network. Key words: Membrane computing; Spiking neural P system; NVIDIA CUDA; graphics processing units 136 Carandang et al 1 Introduction Membrane computing, initiated in [15], involves models of computations inspired by structures and functions of various types of biological cells. Models in membrane computing are known as membrane or P systems. The specific type of P system we consider in this work are spiking neural P systems, in short, SN P systems. SN P systems, first introduced in [7], are inspired by the pulse coding of information that occur in biological neurons. In pulse coding from neuroscience, pulses known as spikes are indistinct, so information is instead encoded in their multiplicity or the time step(s) they are emitted. SN P systems are known to be computationally universal (i.e. equivalent to Turing machines) in both generative (an output is given, but not an input) and accepting (an input is given, but not an output) modes. SN P systems can also solve hard problems in feasible (polynomial to constant) time. Another active line of investigation on the computability and complexity of SN P systems is taking mathematical and biological inspirations in order to create new variants, e.g. asynchronous operation, weighted synapses, rules on synapses, structural plasticity. We do not go into details, and we refer to [7, 9, 14, 17, 5] and references therein. Software simulators for P systems, whether sequential or parallel, have been provided. Sequential simulators include for example those implemented using PLingua, a programming language designed for P systems, e.g. [11]. Simulators using massively parallel processors known as graphics processing units (in short, GPUs) for cell-like P systems as well as SN P systems include [13], a comprehensive survey in [12], and [4, 10]. In this work, we report our ongoing efforts to simulate SN P systems on GPUs manufactured by NVIDIA. In particular, our contributions in this report are as follows: (a) modified matrix representation of [18] in order to be able to simulate SNP systems with delays, (b) the entire simulation of SN P systems with delays is now performed in the GPU, compared to a small portion of the simulation in [4], and (c) using generalized sorting network of SN P systems, we report up to 51 times speedup in our experiments with a 512 input size network. A preliminary version of this work is available in [6]. This work is organized as follows: Section 2 provides preliminaries for the remainder of this work; Section 3 provides the definition of SN P systems as well as their linear algebra representations; Section 4 provides an overview of the NVIDIA CUDA architecture; Section 5 provides the simulation algorithm for our work; Section 6 provides experimental results for the sequential and parallel simulators; Finally, Section 7 provides conclusions from our work as well as future research directions. 2 Preliminaries We recall some formal language theory (available in many monographs). We only briefly mention notions and notations which will be useful throughout the paper. Improving Simulations of SNP Systems in CUDA GPUs: CuSNP 137 We denote the set of natural (counting) numbers as N={0,1,2, . . .}, where N+= N− {0}.Let Vbe an alphabet, V∗is the set of all finite strings over Vwith respect to concatenation and the identity element λ(the empty string). The set of all non-empty strings over Vis denoted as V+,so V+=V∗− {λ}. A language L⊆V∗is regular if there is a regular expression Eover Vsuch that L(E) = L. A regular expression over an alphabet Vis constructed starting from λand the symbols of Vusing the operations union, concatenation, and +. Specifically, (i)λand each a∈Vare regular expressions, (ii) if E1and E2are regular expressions over Vthen (E1∪E2), E1E2, and E+ 1are regular expressions over V, and (iii) nothing else is a regular expression over V. With each expression Ewe associate a language L(E) defined in the following way: (i) L(λ) = {λ}and L(a) = {a}for all a∈V, (ii) L(E1∪E2) = L(E1)∪L(E2), L(E1E2) = L(E1)L(E2), and L(E+ 1) = L(E1)+, for all regular expressions E1,E2over V. Unnecessary parentheses are omitted when writing regular expressions. If V={a}, we simply write a∗and a+instead of {a}∗and {a}+. If a∈V, we write a0=λ. 3 Spiking Neural P Systems We assume some familiarity with membrane computing concepts, widely available online (e.g. [1]) or in print (e.g. [16]). First, we formally define SN P systems, followed by linear algebra representations of their computations. 3.1 Spiking Neural P System A Spiking Neural P system Πis of the form: Π= (O, σ1, ..., σm, syn, in, out) 1. O={a}is the alphabet containing a single symbole (the spike); 2. σ1, ..., σmare neurons, of the form σi= (ni, Ri),1≤i≤mwhere: a) ni≥0 is the initial number of spikes contained in σi. b) Riis a finite set of rules of the following two forms: i. E/ac→ap;dwhere Eis a regular expression over Oand c≥p≥ 1, d ≥0. ii. as→λ, for s≥1,with the restriction that for each rule E/ac→ap;d of type (i) from Ri, we have as6∈ L(E); 3. syn ⊆ {1,2, ..., m}x{1,2, ..., m}with i6=jfor all (i, j)∈syn, 1≤I, j ≤m (synapses between neurons); 4. in, out ∈ {1,2, ..., m}indicate the input and the output neurons, respectively. The rules of type (i) as mentioned in the construct of neurons are firing (or spiking) rules while the type (ii) are called forgetting rules. An SN P system whose firing rules have p= 1 is said to be of the standard type (non-extended). Given a spiking rule, it is applied as follows. If a neuron σicontains kspikes, and 138 Carandang et al ak∈L(E), k ≥c, then the rule E/ac→ap;d∈Rican be applied. This means we remove cspikes so that k−cspikes remain in σi, the neuron is then fired and produces pspikes (1 in the case of standard SN P systems) after dtime units. Spikes are fired after t+dwhere tis the current time step of the computation. For the case that d= 0, the spikes are fired immediately. When the time step of the computation is between tand t+d, we say that the neuron σhas not fired the spike yet and σis closed, meaning it cannot receive spikes from other neuron connected to it. In the case that a neuron with an in-going synapse to σfires, the spike(s) is(are) lost. During the time step t+d, the spikes are fired, and the neuron is now open to receive spikes. At t+d+ 1 the neuron can begin applying rules. When neuron σiemits the spike, the spikes reach immediately all neuron σjsuch that (i, j)∈syn and σjis open. A forgetting rule is applied as follows. If the neuron σicontains exactly s spikes, then the rule as→λfrom Rican be applied, meaning all of the sspikes are removed from σi. For rules of the form E/ac→ap;dof type (1) where E=ac, we write it in the shortened form ac→ap;d. There are cases when two or more rules are applicable in a step of the computation, at these cases, only one rule is applied and is nondeterministically chosen. However, by definition, it is impossible to have a spiking rule and a forgetting rule to be applied at the same time. In short, for each neuron, at most one rule will be applied at a time unit. Aconfiguration or state of the system at time tcan be described by Ct= hr1/k1, . . . , rm/kmifor 1 ≤i≤m, where neuron icontains ri≥0 spikes and remains closed for kimore steps. The initial configuration of the system is therefore C0=hn1/0, . . . , nm/0i. Rule application provides us a transition from one configuration to another. A computation is any (finite or infinite) sequence of configurations such that: (a) the first term is the initial configuration C0; (b) for each n≥2, the nth 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, i.e. a configuration where all neurons are open and no rule can be applied. Two common ways to interpret output of an SN P system are as follows: (1) obtaining the time interval between exactly the first two steps when the output neuron σout spikes, e.g. number n=tn−t1is computed, where σout produced its first two spikes at steps t1and tn; (2) counting the number of spikes produced by σout until the system halts. Note that for (1) the system need not halt, since we only consider the first two steps when σout spikes. In this work, we consider systems that produce their output using the manner given in (2). Spiking Neural Systems are usually represented as a directed graphs. Figure 1 shows an example of an SN P system with 3 neurons. This system is formally defined as: Π= ({a}, σ1, σ2, σ3,{(1,2),(2,1),(1,3),(3,1)},1) where: 1. σ1= (0,{a/a →a; 0, a2/a2→λ}) Improving Simulations of SNP Systems in CUDA GPUs: CuSNP 139 a a/a →a; 1 a/a →a a→a a2→λ a a/a →a; 2 1 23 Fig. 1: Example of an SN P System 2. σ2= (1,{a/a →a; 1, a/a →a}) 3. σ3= (1,{a/a →a; 2}) Notice that in σ1, the rule a/a →a; 0 was written a→awhich is convention when L(E) = ap, we can only write ap. Also, we do not write the delay dif it is equal to 0. In this example, some rules used this convention while others did not to show the interchangeability between the two. In Figure 1, there are three neurons, two of which have initial spikes (neurons σ2and σ3). Neurons 1 and 3 have synapses between each other, likewise between σ1and σ2. A synapse exist from σ1to the environment to indicate it is the output neuron. In the first step of computation, σ1will not fire since it does not contain any spike. Neuron 3 will fire and consume its spike but it will close and will not transmit a spike yet since it has a delay. For σ2, we non-deterministically choose which rule to apply. Assuming we choose the rule a/a →a; 1, the neuron will consume all of its spikes and similar to σ3, it will close and will not send any spikes yet. Therefore, after the first step of computation, there are no spikes in the system. In the next step of computation, no rules will spike since there are no spikes in the system but σ2will release a spike since the delay is done. After this step, σ1will contain a spike. At the third step of computation, σ3will release a spike that was delayed and σ3becomes open also. Neuron 1 will send a spike to both σ2and σ3. After this step, each neuron will have one spike. Assuming we always choose to apply the first rule of σ2, this SN P system will cycle every three steps of computation. Going back to the first step of computation, assuming we choose to apply the second rule in σ2, in the next configuration, σ1will have one spike while σ2and σ3will have zero. Neuron 1 will then fire, sending a spike to σ2. Neuron 3 will not receive a spike since it is currently closed. In the third step of computation, assuming we selected the second rule in σ2again, σ3will send the delayed spike and 140 Carandang et al σ2will spike immediately. After this step, σ1will have two spikes. The forgetting rule will be applied and the computation halts. 3.2 Matrix Representation of Spiking Neural P systems with Delay In [18], a matrix representation of SN P system without delay was introduced. In this work we introduce modifications to this representation which allows us to devise simulations for SN P systems with delay. Let Πbe an SN P system with delay having mneurons and nrules. We use the following definitions, modified from [18], to represent our simulation algorithm: Definition 1: (Configuration Vector). The vector C(k)=hc1, c2, ..., cmiis called the configuration vector at the kth step of computation where each ci, i = 1,2, ..., m, is the amount of spikes neuron icontains. Specifically, the vector C(0) =hc1, c2, ..., cmiis called the initial configuration vector of Π, where ciis the amount of the initial spikes present in neuron σi, i = 1,2, ..., m before the computation starts. Definition 2: (Spiking Vector). Let C(k)=hc1, c2, ..., cmibe the kth configuration vector of Π. Assume a total order d: 1, ..., n is given for all the nrules, so the rules can be referred to as s1, ..., sn. A spiking vector S(k)is defined as follows: S(k)=hs(k) 1, s(k) 2, ..., s(k) ni s(k) i         1,if the regular expression Eiof rule riis satisfied by the numbers of spikes cj(rule riis in neuron σj) and rule riis chosen and applied; 0,otherwise Definition 3: (Status Vector). The vector St(k)=hst1, st2, ..., stmiis called the status vector at the kth step of computation where each sti, i = 1,2, ..., m, determines the status of the neuron m. sti=(1,if neuron mis open 0,if neuron mis closed Note that a neuron is said to be closed when a rule with a delay is activated and is waiting for that delay to become zero. A neuron that is closed may not receive any incoming spikes. Definition 4: (Rule Representation). The set R={r1, r2, ..., rn}is the set of rules where each ri,i= 1,2, ..., n is a vector representing each rule in Π. Each riis defined as follows. ri=hE, j, d0, ci where: Improving Simulations of SNP Systems in CUDA GPUs: CuSNP 141 1. Eis the regular expression for rule i 2. jis the neuron that contains the rule ri 3. d0=     −1,if the rule is inactive (i.e. not applied) 0,if the rule is fired ≥1,if the rule is currently on delay (i.e. σjis closed) 4. cis the number of spikes that neuron σjwill consume if it applies ri. Definition 5: (Delay Vector). The delay vector D=hd1, d2, ..., dnicontains the delay value for each rule ri, i = 1,2, ..., n in Π. Definition 6: (Loss Vector). The vector LV (k)=hlv1, lv2, ..., lvmiis the loss vector where each lvi, for each neuron σi, i = 1,2, ..., m, contains the number of spikes consumed, c, if σiapplies riat step k. Definition 7: (Gain Vector). The vector GV (k)=hgv1, gv2, ..., gvmiis the gain vector which contains the total number of spikes gained, gvi, for each neuron σi, i = 1,2, ..., m, at the kth step of computation not considering whether the neuron is open or closed. Definition 8: (Transition Vectors). Given the total order d: 1, ..., n for all the nrules, the transition vector Tv of the system Π, is a set of vectors defined as follows: Tv =htv1, ..., tvni tvi=hp1, ..., pmi pj=     p, if rule riis in neuron σs(s6=jand (s, j)∈syn) and it is applied producing pspikes; 0,if rule riis in neuron σs(s6=jand (s, j)/∈syn). The set Tv replaces the spiking transition matrix used in [18] since in [18], each matrix entry can contain values either from spikes consumed or produced by each neuron with respect to rules of other neurons. Transition vectors, however, contain only the pspikes gained from other neurons, otherwise 0. Definition 9: (Indicator Vector) The indicator vector IV k=hiv1, iv2, ..., ivmi will be multiplied to Transition Vector, T v ·IV k, in order to get the net number of spike a neuron will get not considering a neuron’s status. Definition 10: (Net Gain Vector). Let LV (k)=hlv1, lv2, ..., lvmibe the kth loss vector vector, GV (k)=hgv1, gv2, ..., gvmiis the kth gain vector vector, and St(k)=hst1, st2, ..., stmiis the kth status vector vector. The net gain vector at step kis defined as NG(k)=GV (k)⊗st(k)+LV (k) 4 NVIDIA CUDA CUDA or Compute Unified Device Architecture is a parallel programming computing platform and application programming interface model developed by NVIDIA 244 Krist´of K´antor, Gy¨orgy Vaszil Pt,2={pt8:ht00 ↔t0;eT →ei, pt9:ht0→t000;eT →ei, pt10 :ht000 ↔e;eT →ei, pt11 :he→ci;eT →ei, pt12 :heT ↔t00;ci↔ei}. The genPCol automaton Πsimulates the work of the two-counter machine M by reading the input symbols with its tape programs and keeping track of the contents of the i-th counter as the number of ci,i∈ {1,2}objects present in the environment. Each transition of Mis simulated separately. At the first step, the 0th cell contains and object that corresponds to q0∈Q, which is then sent to the environment. The environment keeps track of the current internal state of M. One transition rule is simulated by the interplay of programs of two or three cells from Π, if and only if Mchanges its state from qto q0while the counter contents are also checked and modified accordingly. A transition t: (q, x, i, B)→(q0,−1) ∈T rB,−1is simulated by two cells Ct,1, Ct,2with the sets of programs Pt,1and Pt,2. First, qenters the first cell Ct1from the environment by program pt1, activating the simulation of the transition. Then cienters the first cell (program pt2), and by programs pt3and pt4, object t0is sent to the environment. Now the programs of the second cell Ct2are activated, t0is changed to t000 and sent to the environment by the programs pt8,pt9, and pt10 . Now by pt5,pt6of the first cell, t000 is changed to q0denoting the next state of M, and it is sent to the environment by pt7. A transition t: (q, x, i, B)→(q0,0) ∈T rB,0is also simulated by two cells with the sets of programs Pt,1and Pt,2. Now the initial contents of the second cell is t00e. The first four steps are identical with the previous case described above. When t0 appears in the environment, the programs of the second cell exchange it with t00 and send ciand t000 to the environment by the programs pti,8≤i≤12, then t000 is exchanged with the object q0(denoting the next state of M) in the environment by pt5,pt6, and pt7of the first cell. A transition t: (q, x, i, B)→(q0,+1) ∈T rB,+1 is simulated by three cells with the sets of programs Pt,1,Pt,2and Pt,3. The initial contents of the three cells are te,t00e, and ee, respectively. In the first five steps the programs of the first cell are active, but besides the object t0, this time the cell also sends cito the environment. When t0appears in the environment (after the application of Pt,5, the programs of the second cell take over. They are identical to the previous case, they exchange t0with t00 and send ciand t000 to the environment as above. Finally the third cell becomes active, and t000 is exchanged with the object q0(denoting the next state of M) in the environment by pt13 ,pt14 , and pt15 . A transition t: (q, x, i, Z)→(q0,0) ∈T rZ,0is simulated by two cells with the sets of programs Pt,1and Pt,2. The initial contents of both cells are ee. The first three steps, the first cell exchanges qto t0in the environment while the second cell remains inactive. When t0appears in the environment, the programs of the second cell exchange it with t000 in the next computational step. During this step, the first cell is either inactive, or imports an object cifrom the environment, if there is at least one such object is present there. In this later case, the transition cannot be On the Classes of Languages Characterized by Generalized P Colony Automata 245 applied in a simulation of the two counter machine M, as the value stored the ith counter is not zero. This is reflected by program pt,4which introduces a a “trap object” A. If the transition is applicable in M, that is, if there is no cipresent in the environment. Then after two inactive steps, t000 is exchanged with the object q0(denoting the next state of M) in the environment by pt5and pt6of the first cell. Finally, a transition t: (q, x, i, Z)→(q0,+1) ∈T rZ,+1 is simulated by two cells with the sets of programs Pt,1and Pt,2. The initial contents of the two cells are ee and t00e, respectively. The first three steps is identical with those in the previous case. When t0appears in the environment, the programs of the second cell exchange it with t00, send an object t000 and then an object ci(in exchange with t00) to the environment. These are done by programs pt5and pt6. Similarly to the previous case, during the fourth computational step, the first cell is either inactive, or imports an object cifrom the environment (by program pt4, if there is at least one such object is present there). In the later case, the transition cannot be applied in a simulation as the value stored the ith counter of Mis not zero (so the “trap object” Ais introduced). If there is no cipresent in the environment (the transition is applicable in a simulation), then after three steps (in which the first cell is inactive), t000 is imported into the first cell, and then the object q0(denoting the next state of M) is sent to the environment by pt5and pt6, respectively. According to these considerations, we have seen that having the object qin the environment, the genPCol automaton Πreplaces it with q0, and either simulates a transition of the two-counter machine Mfrom state qto state q0(checking and adjusting the multiplicity of the objects corresponding to the counter contents accordingly), or its computation is not successful. Thus, starting with q0in the environment (q0is sent to the environment by the first program in P0in the very first step of Π) the genPCol automaton produces qacc, the accepting state of the two-counter machine Min the environment if and only if its computation corresponds to an accepting computation of M. Having qacc in the environment, Πcan reach its final configuration by importing it into the cell C0by using the second program of P0. 4 Conclusions We have studied the effect of the capacity of generalized P colony automata on their computational power using the all-tape and com-tape variants of programs used. We have shown that even with capacity one, if we do not place additional restrictions on the types of programs allowed to be used by the system, genPCol automata characterize the class of recursively enumerable languages. On the other hand, for systems with capacity three, even the use of most restrictive program types does not result in any decrease of the computational power. The most interesting cases are the ones in between these two: the restricted variants of capacity one and capacity two. These require further study, especially interesting would be 246 Krist´of K´antor, Gy¨orgy Vaszil to refine the relationship of the model with P automata, as they are very closely related, but not as similar as one might expect at the first glance. References 1. L. Cienciala, L. Ciencialov´a, P Colonies and Their Extensions. In: J. Kelemen, A. Kelemenov´a (eds.), Computation, Cooperation, and Life. Essays Dedicated to Gheorghe P˘aun on the Occasion of His 60th Birthday. LNCS 6610, Springer Berlin Heidelberg, 2011, 158–169. 2. L. Ciencialov´a, E. Csuhaj-Varj´u, A. Kelemenov´a, Gy. Vaszil, Variants of P colonies with very simple cell structure. International Journal of Computers Communication and Control,4(2009), 224–233. 3. L. Cienciala, L. Ciencialov´a, E. Csuhaj-Varj´u, Gy. Vaszil, PCol automata: Recognizing strings with P colonies. In: M. A. Mart´ınez del Amor, Gh. P˘aun, I. P´erez Hurtado, A. Riscos Nu˜nez (eds.), Eighth Brainstorming Week on Membrane Computing, Sevilla, February 1-5, 2010, F´enix Editora, 2010, 65–76. 4. E. Csuhaj-Varj´u, J. Dassow, On cooperating/distributed grammar systems. Journal of Information Processing and Cybernetics EIK, 26 (1990), 49–63. 5. E. Csuhaj-Varj´u, J. Dassow, J. Kelemen, Gh. P˘aun, Grammar Systems – A Grammatical Approach to Distribution and Cooperation. Gordon and Breach, London, 1994. 6. E. Csuhaj-Varj´u, M. Oswald, Gy. Vaszil, P automata. In [17], chapter 6, 144–167. 7. E. Csuhaj-Varj´u, Gy. Vaszil, P automata or purely communicating accepting P systems. In: Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron (eds.), Membrane Computing. International Worskhop, WMC-CdeA 2002, Curtea de Arges, Romania, August 19-23, 2002, Revised Papers. LNCS 2597, Springer Berlin Heidelberg, 2003, 219–233. 8. E. Csuhaj-Varj´u, Gy. Vaszil, P automata with restricted power. International Journal of Foundations of Computer Science,25 (2014), 391–408. 9. P.C. Fischer, Turing machines with restricted memory access. Information and Control,9(1966), 364–379. 10. R. Freund, M. Kogler, Gh. P˘aun, M.J. P´erez-Jim´enez, On the power of P and dP automata. Annals of Bucharest University, Mathematics-Informatics Series 63 (2009), 5-22. 11. K. K´antor and Gy. Vaszil Generalized P Colony Automata Journal of Automata, Languages and Combinatorics 19 (2014), 145–156. 12. J. Kelemen, A. Kelemenov´a, A grammar-theoretic treatment of multiagent systems. Cybernetics and Systems,23 (1992), 621–633. 13. J. Kelemen, A. Kelemenov´a, Gh. P˘aun, Preview of P colonies: A biochemically inspired computing model. In: M. Bedau et al. (eds.), Workshop and Tutorial Proceedings. Ninth International Conference on the Simulation and Synthesis of Living Systems (Alife IX). Boston Mass., 2004, 82–86. 14. A. Kelemenov´a, P Colonies. In [17], chapter 23.1, 584–593. 15. M.L. Minsky, Computation: Finite and Infinite Machines. Prentice Hall, 1967. 16. A. P˘aun, Gh. P˘aun, The power of communication: P systems with symport/antiport. New Generation Computing 20(3) (2002), 295-306. 17. Gh. P˘aun, G. Rozenberg, A. Salomaa, editors, The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. A Toolbox for Simpler Active Membrane Algorithms? Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron Dipartimento di Informatica, Sistemistica e Comunicazione Università degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy {leporati,luca.manzoni,mauri,porreca,zandron}@disco.unimib.it Summary. We show that recogniser P systems with active membranes can be augmented with a priority over their set of rules and any number of membrane charges without loss of generality, as they can be simulated by standard P systems with active membranes, in particular using only two charges. Furthermore, we show that more general accepting conditions, such as sending out several, possibly contradictory results and keeping only the first one, or rejecting by halting without output, are also equivalent to the standard accepting conditions. The simulations we propose are always without significant loss of efficiency, and thus the results of this paper can hopefully simplify the design of algorithms for P systems with active membranes. 1 Introduction P systems with active membranes [ 10 ] have been extensively investigated as computing devices, both from the computability and the computational complexity standpoints. By analysing the algorithms for P systems with active membranes described in the literature, it is possible to identify a number of useful and recurring techniques or “design patterns”. A standard one is using elementary membrane division to produce all assignments of a set of variables x1, . . . , xn [ 10 ]; the results of evaluating a Boolean formula under those assignments can then be combined in several ways: • by disjunction, allowing the solution of the SAT problem, and thus all NP - complete problems [15]; ? This work was partially supported by Fondo d’Ateneo (FA) 2015 of Università degli Studi di Milano-Bicocca: “Complessità computazionale e applicazioni crittografiche di modelli di calcolo bioispirati”. 248 Alberto Leporati et al. • by counting the number of satisfying assignments against a threshold, allowing the solution of counting problems in the class PP [12]; • by alternating disjunctions and conjunctions by means of a tree-shaped membrane structure of depth n , allowing the solution of PSPACE -complete problems [14]. Other techniques involve simulating register machines [ 4 ] or Turing machines [ 2 ], also in their nondeterministic version, by simulating nondeterminism with parallelism as above for solving NP -complete problems [ 6 ]. Membranes at different nesting levels can also be employed as “subroutines”, simulating multiple Turing machines and becoming functionally equivalent to oracles for subproblems [6]. While the main ideas behind those constructions are generally straightforward and show clear affinity with techniques from the theory of traditional computing devices, their implementation unfortunately often involves a number of technical details which obfuscate the big picture. One of the main culprits are the ubiquitous timer objects, which keep the different parts of the P system synchronised and allow the halting of the computation immediately after producing the output, a condition that is usually imposed by the definition of recogniser P systems and that often requires extra work to be met. One of the crucial aspects of the definition of P systems with active membranes is the number of possible membrane charges, which is 3in the original definition. Although charges are not needed to solve PSPACE -complete problems in polynomial time 2 [ 3 ] and two charges suffice to achieve universality [ 1 ], having access to a number of charges growing with the size of the input allows a simpler implementation of many algorithms. For instance, when this is allowed, the simulation of bounded-tape Turing machines becomes trivial [ 6 ]. In that paper, an arbitrary number of charges was reduced to three without loss of efficiency, but only in a very restrictive set of circumstances (essentially, no communication with adjacent membranes is allowed, and the membrane must behave deterministically). The purpose of this paper is twofold. On the one hand, we want to understand which features of recogniser P systems with active membranes are actually essential to characterise their behaviour. On the other hand, we want to provide an array of useful extensions which can be added to P systems with active membranes but can be simulated by the original model without loss of efficiency. This will hopefully reduce the amount of “boilerplate code” (repetitive rules unrelated to the main algorithm) in proofs and allow focusing on a higher-level description of P systems, such as dividing membranes working in parallel and their communication patterns. The formally redundant but convenient features we describe in this paper are the ability to use any number of charges, any partial priority ordering of rules (as in the original definition of transition P systems [ 9 ]), and the ability 2 However notice that, in the absence of membrane dissolution rules, the lack of charges seems to reduce the efficiency of P systems [5]. A Toolbox for Simpler Active Membrane Algorithms 249 to output the result of the computation in less restrictive ways, such as not requiring the P system to halt after having sent out the result, or rejecting by halting without output. Furthermore, we show that all these enhancements can be simulated efficiently by standard recogniser P systems with active membranes using only two charges (even when working in super-polynomial time). 2 Basic notions We recall the formal definition of P systems with active membranes using weak non-elementary division rules [10, 16]. Definition 1. AP system with active membranes with weak non-elementary division rules of initial degree d≥1is a tuple Π= (Γ, Λ, µ, wh1, . . . , whd, R) where: •Γ is an alphabet, i.e., a finite non-empty set of symbols, usually called objects; •Λis a finite set of labels for the membranes; •µ is a membrane structure (i.e., a rooted unordered tree, usually represented by nested brackets) consisting of d membranes labelled by elements of Λ in a one-to-one way; •wh1, . . . , whd , with h1, . . . , hd∈Λ , are strings over Γ , describing the initial multisets of objects placed in the dregions of µ; •Ris a finite set of rules. Each membrane possesses, besides its label and position in µ , another attribute called electrical charge, which can be either neutral (0), positive (+) or negative (−) and is always neutral before the beginning of the computation. The rules in Rare of the following types: (a) Object evolution rules, of the form [a→w]α h They can be applied inside a membrane labelled by h , having charge α and containing an occurrence of the object a ; the object a is rewritten into the multiset w (i.e., a is removed from the multiset in h and replaced by the objects in w). (b) Send-in communication rules, of the form a[ ]α h→[b]β h They can be applied to a membrane labelled by h , having charge α and such that the external region contains an occurrence of the object a ; the object a is sent into h becoming b and, simultaneously, the charge of h is changed to β. 250 Alberto Leporati et al. (c) Send-out communication rules, of the form [a]α h→[ ]β hb They can be applied to a membrane labelled by h , having charge α and containing an occurrence of the object a ; the object a is sent out from h to the outside region becoming b and, simultaneously, the charge of h becomes β. (d) Dissolution rules, of the form [a]α h→b They can be applied to a membrane labelled by h , having charge α and containing an occurrence of the object a ; the membrane is dissolved and its contents are left in the surrounding region unaltered, except that an occurrence of abecomes b. (e) Elementary division rules, of the form [a]α h→[b]β h[c]γ h They can be applied to a membrane labelled by h , having charge α , containing an occurrence of the object a but having no other membrane inside (an elementary membrane); the membrane is divided into two membranes having label h and charges β and γ ; the object a is replaced, respectively, by b and c , while the other objects of the multiset are replicated in both membranes. (f’) Weak non-elementary division rules, of the form [a]α h→[b]β h[c]γ h They can be applied to a membrane labelled by h , having charge α , and containing an occurrence of the object a , even if it contains further membranes; the membrane is divided into two membranes having label h and charges β and γ ; the object a is replaced, respectively, by b and c , while the rest of the contents (including whole membrane substructures) is replicated in both membranes. The instantaneous configuration of a membrane consists of its label h , its charge α , and the multiset w of objects it contains at a given time. It is denoted by [ w ] α h . The (full) configuration C of a P system Π at a given time is a rooted, unordered tree. The root is a node corresponding to the external environment of Π , and has a single subtree corresponding to the current membrane structure of Π . Furthermore, the root is labelled by the multiset located in the environment, and the remaining nodes by the configurations [ w ] α h of the corresponding membranes. A computation step changes the current configuration according to the following set of principles: • Each object and membrane can be subject to at most one rule per step, except for object evolution rules: inside each membrane, several evolution rules can be applied simultaneously. • The application of rules is maximally parallel: each object appearing on the left-hand side of evolution, communication, dissolution or division rules must be subject to exactly one of them (unless the current charge of the membrane prohibits it). Analogously, each membrane can only be subject to one communication, dissolution, or division rule (types (b)–(f’)) per computation step; these rules will be called blocking rules in the rest of the paper. In other words, the only objects and membranes that do not evolve A Toolbox for Simpler Active Membrane Algorithms 251 are those associated with no rule, or only to rules that are not applicable due to the electrical charges. • When several conflicting rules can be applied at the same time, a nondeterministic choice is performed; this implies that, in general, multiple possible configurations can be reached after a computation step. • In each computation step, all the chosen rules are applied simultaneously (in an atomic way). However, in order to clarify the operational semantics, each computation step is conventionally described as a sequence of microsteps as follows. First, all evolution rules are applied inside the elementary membranes, followed by all communication, dissolution and division rules involving the membranes themselves; this process is then repeated to the membranes containing them, and so on towards the root (outermost membrane). In other words, the membranes evolve only after their internal configuration has been updated. For instance, before a membrane division occurs, all chosen object evolution rules must be applied inside it; this way, the objects that are duplicated during the division are already the final ones. • The outermost membrane cannot be divided or dissolved, and any object sent out from it cannot re-enter the system again. Ahalting computation of the P system Π is a finite sequence ~ C = ( C0,...,Ck ) of configurations, where C0 is the initial configuration, every Ci+1 is reachable from Ci via a single computation step, and no rules of Π are applicable in Ck . A non-halting computation ~ C = ( Ci : i∈N )consists of infinitely many configurations, again starting from the initial one and generated by successive computation steps, where the applicable rules are never exhausted. P systems can be used as language recognisers by employing two distinguished objects yes and no : we assume that all computations are halting, and that either object yes or object no (but not both) is sent out from the outermost membrane, and only in the last computation step, in order to signal acceptance or rejection, respectively. If all computations starting from the same initial configuration are accepting, or all are rejecting, the P system is said to be confluent. If this is not necessarily the case, then we have a non-confluent P system, and the overall result is established as for nondeterministic Turing machines: it is acceptance iff an accepting computation exists. In order to solve decision problems (or, equivalently, decide languages), we use families of recogniser P systems Π = {Πx : x∈Σ?} . Each input x is associated with a P system Πx deciding the membership of x in a language L⊆ Σ? by accepting or rejecting. The mapping x7→ Πx must be efficiently computable for inputs of any length, as discussed in detail in [7]. Definition 2. A family of P systems Π = {Πx : x∈Σ?} is (polynomialtime) uniform if the mapping x7→ Πx can be computed by two polynomial-time deterministic Turing machines Eand Fas follows: •F (1 n ) = Πn , where n is the length of the input x and Πn is a common P system for all inputs of length nwith a distinguished input membrane. 252 Alberto Leporati et al. •E(x) = wx, where wxis a multiset encoding the specific input x. •Finally, Πxis simply Πnwith wxadded to its input membrane. The family Π is said to be (polynomial-time) semi-uniform if there exists a single deterministic polynomial-time Turing machine H such that H ( x ) = Πx for each x∈Σ?. Any explicit encoding of Πx is allowed as output of the construction, as long as the number of membranes and objects represented by it does not exceed the length of the whole description, and the rules are listed one by one. This restriction is enforced in order to mimic a (hypothetical) realistic process of construction of the P systems, where membranes and objects are presumably placed in a constant amount during each construction step, and require actual physical space proportional to their number; see also [ 7 ] for further details on the encoding of P systems. In this paper we also take advantage of rule priorities, as in the original paper introducing P systems [ 9 ]. A priority is any partial order  of the set of rules such that, whenever a conflict between rules arises, only those with higher priority can be applied; as usual, when two rules are incomparable with respect to  , any conflict is resolved via a nondeterministic choice. Furthermore, we also allow generalised charges, that is, any set Ψ⊇ { + , 0 ,−} of charges may be used [ 6 ]. Rule priorities and generalised charges will be proved redundant in Section 4. 3 Generalised Acceptance Conditions In this section we propose a more flexible variant of recogniser P system, where we do not require a single output object at the last step of the computation, or even the halting of the P system itself. This allows the omission of a number of technical details from membrane computing solutions, which are sometimes unrelated to the main algorithm but are still required in order to ensure compliance to the formal definition of recogniser P systems. We prove that there is no loss of generality in using these variants of accepting condition, as it can always be simulated without significant loss of efficiency by the standard one; we show this result first for P systems with priority and generalised charges, and in a later section for standard P systems. Definition 3. Ageneralised recogniser P system Π is a P system employing two distinguished objects yes and no and behaving in any of the three following ways: 1. It sends out an instance of object yes from its outermost membrane before sending out any instance of object no ; it can later send out any combination of objects yes and no, and is not required to halt. A Toolbox for Simpler Active Membrane Algorithms 253 2. It sends out an instance of object no from its outermost membrane before sending out any instance of object yes ; it can later send out any combination of objects yes and no, and is not required to halt. 3. It halts without sending out neither an instance of yes , nor an instance of no. The P system Π is said to accept in case 1, and to reject in case 2. The behaviour of 3 can be interpreted as either accepting or rejecting, according to a specified convention. It is trivial to observe that a standard recogniser P system [ 11 ] is a special case of generalised recogniser P system, always halting and sending out exactly an instance of yes or no and only in the last computation step. Furthermore, other acceptance conditions proposed in the literature [ 8 ] are also special cases of generalised recogniser P systems; in particular, we have acknowledger P systems (which accept by sending out one or more instances of yes and reject by halting without output) and recogniser ≥1 P systems (which accept by sending out one or more instances of yes and reject by sending out one or more instances of no ). The only notable case not covered by the notion of generalised recogniser P systems is accepting by outputting yes while rejecting by not halting; since P systems are known to be universal [ 1 ], this acceptance condition characterises the whole class of recursively enumerable sets. 3.1 Ensuring Output on Halting We can now show that standard recogniser P systems with priority and generalised charges solve exactly the same problems as generalised recogniser P systems using the same features with polynomial slowdown. Priority and generalised charges will then be eliminated, also without loss of efficiency, in Section 4. We begin by reducing case 3 of Definition 3 to one of the other two cases: case 2 if halting without output is interpreted as rejecting, or case 1 if it is interpreted as accepting. The idea is to have a timer located inside the outermost membrane, which is sent out as a no object if it does not receive a signal for 2 d consecutive steps, where d is the depth of the membrane structure. This signal indicates that at least one rule was applied in the P system in the last 2 d steps, and is propagated as an object ♣ towards the outermost membrane. Let Π be the generalised recogniser being simulated, and let Π0 be the standard recogniser simulating it; both P systems have priority and generalised charges. The initial membrane structure of Π0 is identical to that of Π . Inside each membrane, besides the original multiset, we place an instance of ♦ and one of ♥ ; finally, the outermost membrane also contains an instance of the timer object Td. The rules of Π are modified in Π0 so that their application is always detectable; in order to do so, we always either change the charge of a membrane where a rule was applied to a new, specific charge (for rules involving the 260 Alberto Leporati et al. 2. [ wiαi ] + h is as in 1, but rule ri has either the wrong label or the wrong charge on the left-hand side. 3. [ wiαi,j ] 0 h is as in 1, but a blocking rule rj for h , for some j < i , has been previously applied during the simulation of the current step of Π , and ri is necessarily an object evolution rule. 4. [ wiαi,j ] + h is as in 1, but a blocking rule rj for h , for some j < i , has been previously applied during the simulation of the current step of Π , rule ri is either an object evolution rule with wrong label or charge on the left-hand side, or it is any blocking rule. Let us consider the four types of possible configuration separately. 4.1 Configuration of the Form [wiαi]0 h The behaviour of the P system Π0 when the configuration at time whatever is [wiαi]0 hdepends on the type of rule riof Πto be simulated. Applicable Send-Out Rules Suppose that ri is a send-out rule of Π of the form [ a ] α h→ [ ] β hb ; also suppose that the simulated membrane h contains at least one instance of a , i.e., that the configuration of the membrane in Π0 is [ aiviαi ] 0 h for some multiset vi . The rule is implemented by first sending out an object ai as e bi ; the tilde here denotes that that instance of object bi has already been subject to a rule during this simulated step of Π . The charge of the membrane is also changed to + in order to signal that rule ri was actually applied (i.e., that the membrane contained at least one instance of ai): [ai]0 h→[ ]+ h e bi(7) At the same time, the object αiis primed: [αi→α0 i]0 h The configuration of the membrane is now [ uiα0 i ] + h , where ui is vi with any extra objects received from children membranes 3 , and the object e bi is now managed by the outer membrane. When the membrane becomes positive, each original object of Γ (possibly in a tilded version) gains a prime, while α0 i becomes α00 i,i , storing in its second subscript the index i of the blocking rule that has actually been applied: 3 This is not actually possible with standard P systems, since the children of a membrane always have a different label, and thus cannot apply any rule while ri is being applied. However, we will prove later that we can replace labels by charges; therefore, we will consider this case anyway. A Toolbox for Simpler Active Membrane Algorithms 261 [ci→c0 i]+ hfor c∈Γ [eci→ec0 i]+ hfor c∈Γ [α0 i→α00 i,i]+ h(8) This leads us to the configuration [ u0 iα00 i,i ] + h , where u0 i is ui with all objects primed. The object α00 i,i is now rewritten as follows: [α00 i,i →α000 i,i ]+ h The configuration is now [u0 iα000 i,i ]+ h. The object sets the charge to 0: []+ h→[ ]0 h# while α000 i,i produces • , where • is  if rule ri+1 is an evolution rule with label h and charge α (i.e., ri+1 is potentially applicable), and • is ⊕ otherwise (i.e., ri+1 is not applicable due to the label, the charge, or the membrane h having already been used): [α000 i,i →α0000 i,i •]+ h The configuration is thus [ u0 iα0000 i,i • ] 0 h . In the last step, we need to increase the rule counter i to i +1, remove all primes, and update the charge of h according to •: [α000 i,i →αi+1,i]0 h [c0 i→ci+1]0 hfor c∈Γ [ec0 i→eci+1]0 hfor c∈Γ []0 h→[ ]0 h# [⊕]0 h→[ ]+ h# We have thus reached the configuration [ ui+1 αi+1,i ] 0 h or [ ui+1 αi+1,i ] + h after 5 steps of Π0, thus restoring the invariant. Applicable Send-In Rules If ri is a send-in rule a [ ] α h→ [ b ] β h and the outer membrane contains an instance of object a that is actually assigned to this rule for the current membrane, the computation proceeds exactly as for applicable send-out rules, in 5steps, except that rule (7) is replaced by the symmetrical rule ai[ ]0 h→[ e bi]+ h 262 Alberto Leporati et al. Applicable Division Rules If ri is a weak (elementary or non-elementary) division rule [ a ] α h→ [ b ] β h [ c ] γ h and membrane h contains an instance of a , then the computation evolves again as for applicable send-out rules, in 5steps, with the following variations. Rule (7) is replaced by the send-out rule [ai]0 h→[ ]+ h# This rule sets the charge to +, thus signalling that the rule is actually being applied. This fact is recorded by the object α0 i using rule (8) ; the actual division does not happen immediately, but is delayed until the end of the iteration across all rules. The reason for this delay is to comply with the usual semantics of P systems, where internal membranes logically evolve before external ones: if division happened immediately, the internal membranes may evolve differently in the two copies of the membrane, due to the nondeterminism possibly introduced by send-in rules. Applicable Dissolution Rules A dissolution rule ri = [ a ] α h→b is simulated in 5steps as a send-out rule followed by a delayed dissolution; this is recorded, as for division rules, in the second subscript of the object α00 i,i . The actual dissolution is delayed because further object evolution rules might be applicable. Object Evolution Rules An object evolution rule ri = [ a→x ] α h , with x∈Γ? , is simulated in a slightly different way than blocking rules: since they are applied in parallel to all objects a contained in h , this rule cannot change the charge of the membrane to signal its application. The object αi must thus evolve without knowing if and to how many objects the rule riis being applied. In the first step the actual evolution occurs: [ai→exi]0 h(9) [αi→α0 i]0 h where exi is x with all objects tilded and subscripted by i . This leads to the configuration [ viα0 i ] 0 h , where vi is the multiset wi updated according to rule (9) . In the second step the following rule is applied: [α0 i→α00 i⊕]0 h leading to configuration [viα00 i⊕]0 h. The charge is then set to +: [⊕]0 h→[ ]+ h# [α00 i→α000 i]0 h A Toolbox for Simpler Active Membrane Algorithms 263 leading to [ viα000 i ] + h . The objects in Γ and their tilded versions are now primed, while the charge becomes 0: [ci→c0 i]+ hfor c∈Γ [eci→eci 0]+ hfor c∈Γ []+ h→[ ]0 h# [α000 i→α0000 i•]+ h where • works as described above. This leads to the configuration [ v0 iα0000 i• ] 0 h . The last step is as for applicable send-out rules, and leads to [ vi+1 αi+1 ] 0 h or [vi+1 αi+1]+ hdepending on ri+1. Non-Applicable Blocking Rules If ri is a blocking rule with label h and charge α , but the object on the left-hand side of the rule is missing, we reach the configuration [ viα0 i ] 0 h after one step, where vi is wi except for any objects coming from or sent in children membranes. The object α0 i detects that rule ri was not applied by observing the neutral charge of the membrane. The membrane can then evolve as for object evolution rules, leading to configuration [ vi+1 αi+1 ] 0 h or [ vi+1 αi+1 ] + h (depending on ri+1) in 5computation steps. 4.2 Configuration of the Form [wiαi]+ h If the P system reaches configuration [ wiαi ] + h , then rule ri is not applicable either because it involves a label different from h , or a charge different from α on the left-hand side. In that case, the P system must reach configuration [ vi+1 αi+1 ] 0 h (or [ vi+1 αi+1 ] + h if ri+1 has the wrong label or charge), where v is w except for any object coming from or sent in children membranes, after exactly 5steps, in order to keep all membranes synchronised. In this particular configuration, unlike the previous one, the objects of Γ and their tilded counterparts have their subscript incremented without first being primed. First the object αi waits for two steps, and then produces a  ; the object αi is also tilded to record the fact that rule riis not being applied at this time: [αi→eα0 i]+ h[eα0 i→eα00 i]+ h[eα00 i→eα000 i]+ h While the charge is set to 0, the object • (which is either  or ⊕ according to the label and charge of ri+1) is produced: []+ h→[ ]0 h# [eα000 i→eα0000 i•]+ h Finally, all subscripts are incremented: 264 Alberto Leporati et al. [eα0000 i→αi+1]0 h [ci→ci+1]0 hfor c∈Γ [eci→eci+1]0 hfor c∈Γ This leads to the configuration for rule ri+1. Notice that the fact that the objects in Γ (both in plain and tilded versions) are not primed in this simulated micro-step allows them to be sent into a children membrane if rule rirequires so. 4.3 Configuration of the Form [wiαi,j]0 h If the configuration has the form [ wiαi,j ] 0 h , then a blocking rule rj , with j < i , has already been applied to that membrane, and ri is thus necessarily an object evolution rule with label h and charge α . The computation then proceeds as for object evolution rules in Section 4.1, except that the second subscript j of αi,j is also preserved, thus reaching configuration [ vi+1 αi+1,j ] 0 h (or [ vi+1 αi+1,j ] + h ) after 5steps, where v is w updated according to ri and any object coming from or sent in children membranes. 4.4 Configuration of the Form [wiαi,j]+ h If the configuration has the form [ wiαi,j ] + h , then a blocking rule rj , with j < i , has already been applied to that membrane, and ri either has the wrong label or charge, or it is another blocking rule (and thus it is not applicable). In this case, the computation proceeds as in Section 4.2, except that the second subscript jof αi,j is preserved. 4.5 Concluding the Simulation of One Step After having simulated all rules r1r1 · · ·  rm in priority order, the subscripts of the objects inside each membrane will reach the value m + 1. Suppose that all membranes have been set to neutral at that time (as if the non-existing rule rm+1 were always applicable). In order to restore the outer invariant of Section 4, we need to remove the subscripts and the tildes, update the objects representing the charges, and completing the application of dissolution and division rules. The objects in Γ and their tilded counterparts can be immediately rewritten into their final form: [cm+1 →c]0 hfor h∈Λand c∈Γ [ecm+1 →c]0 hfor h∈Λand c∈Γ If a dissolution rule rj involving the membrane being simulated was applied during this simulated step, the actual dissolution can now take place (recall that the object b on the right-hand side of the rule has already been sent out): A Toolbox for Simpler Active Membrane Algorithms 265 [αm+1,j]0 h→# If a weak (elementary or non-elementary) division rule rj involving membrane h was applied, then we can first perform the actual division: [αm+1,j]0 h→[α0 m+1,j]0 h[α00 m+1,j]0 h and then update the simulated charges and create the right-hand side objects in the two copies of h: [α0 m+1,j →β b]0 h[α00 m+1,j →γ c]0 h If a blocking rule rj of the remaining types (send-in or send-out) was applied to the membrane, then we just need to update the charge object to β , the right-hand side charge of rj ; however, this must take two steps to maintain synchronisation with membranes where division was applied: [αm+1,j →α0 m+1,j]0 h[α0 m+1,j →β]0 h Finally, if no blocking rule was applied in membrane h , then we must keep the same charge as in the previous step of Π ; once again, this must take two steps to maintain all membranes synchronised: [αm+1 →α0 m+1]0 h[α0 m+1 →α]0 hfor h∈Λ,α∈Ψ The new configuration of Π0 then corresponds to a reachable configuration of Πaccording to the encoding described above. 4.6 Halting and Output In the simulation of this section, detecting whether a membrane of Π has stopped computing paradoxically requires us to iterate across all rules, thus preventing the simulating P system Π0 to halt. However, according to the results of Section 3, we can always assume the simulated P system Π to be a standard recogniser, and that all membranes assume charge ♠ when they stop computing. Thus, we simulate each membrane as described above until it assumes the charge ♠ . When this happens, the simulating membrane contains the object ♠ ; however, by construction the children of this membrane, if any, have not yet assumed the charge ♠ , as this will propagate there by send-in in the next computation step. Hence, when a simulated membrane reaches charge ♠ , we must perform a last iteration across the rules of Π in order to simulate those send-in rules, and then the simulating membrane can finally halt. This last iteration is needed in order to update the subscripts of the objects ci (with c∈Γ ). Another small modification to be made involves sending out the yes or no object: in Π , the corresponding rules do not generally have the lowest priority, and thus the actual sending out of the result object 266 Alberto Leporati et al. must be delayed in order to be the last action performed by the simulating P system Π0. Halting the simulation of a membrane can thus be performed by simply deleting the object ♠m+1 obtained after the last iteration across the rules: [♠m+1 →]0 hfor h∈Λ(10) The outputting of yes or no by Π0 at the last step can be achieved by replacing any outermost membrane output rules rjof the forms [a]α k→[ ]β kyes [a]α k→[ ]β kno of Πby a rule of the form [a]α k→[ ]β k# [a]α k→[ ]β k# During the subscript-deleting phase of Section 4.5 we can perform the actual output by using one of the following rules: [αm+1,j]0 k→[ ]0 kyes [αm+1,j]0 k→[ ]0 kno (11) Since, by hypothesis, the rest of the P system Π has already halted, the simulation of Π0 in the worst case completes the last iteration across the rules of Π for the innermost membranes by applying a rule of type (10) exactly when an output rule (11) is applied. The P system Π0 halts immediately after. 4.7 Main Result The only remaining detail to consider is the amount of resources needed in order to perform the simulations described in this section and in Section 3. It suffices to observe that all rules of the final P system are obtained by repeating simple patterns with parameters ranging over sets of polynomial size with respect to the description of the simulated P system (e.g., the set of rules of the original P system, its set of labels, the set of integers up to the membrane nesting dept, . . . ). For example, the rules of type (6) can be output by using two nested loops as follows: for h∈Λdo for α∈Ψdo output “♠[ ]α h→[#]♠ h” end end The construction of Π0 can thus be performed in polynomial time. This leads immediately to our main result: A Toolbox for Simpler Active Membrane Algorithms 267 Theorem 1. Let Πbe a generalised confluent recogniser P system using priority and generalised charges working in time t . Then, there exists a standard confluent recogniser P system Π0 without priority and using only two charges having the same result as Π and working in time O ( r× ( d + t )), where r is the number of rules of Π and d its depth. Furthermore, the mapping Π7→ Π0 can be computed in polynomial time with respect to the length of the description of Π.ut 4.8 A Note on Rule Types The construction used to prove Theorem 1 necessarily requires evolution, sendin and send-out rules. Any other type of rule (dissolution, elementary and weak non-elementary division) is only necessary if the original P system Π being simulated employs it. This construction might, in principle, be extended in order to simulate other kinds of rules, provided that the simulating P system Π0 is also allowed to use them. The technical details are, however, necessarily dependent on the specific type of rule. 5 Conclusions The results of this paper show that the number of charges (as long as it is at least two) and the exact accepting conditions of recogniser P systems with active membranes are immaterial, and can always be reduced to two charges and to the standard definition of recogniser without loss of efficiency. This allows us to use as many charges as are convenient for the solution of the current problem, to employ more relaxed halting conditions, and even to add a rule priority. Hopefully, these tools will yield algorithms having less irrelevant technical details and a better focus on the novel techniques and ideas employed. We conjecture that results analogous to those presented in this paper may also be proved for other classes of P systems, therefore further simplifying membrane computing algorithms. For instance, it would be interesting to explore which features (such as charges, rule priorities and accepting conditions) may be added to tissue P systems [ 13 ] without changing their computing power or efficiency. References 1. Alhazov, A., Freund, R., Riscos-Núñez, A.: One and two polarizations, membrane creation and objects complexity in P systems. In: Zaharie, D., Petcu, D., Negru, V., Jebelean, T., Ciobanu, G., Cicortas, A., Abraham, A., Paprzycki, M. (eds.) Proceedings of the Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC’05. pp. 385–394. IEEE (2005) 268 Alberto Leporati et al. 2. Alhazov, A., Leporati, A., Mauri, G., Porreca, A.E., Zandron, C.: Space complexity equivalence of P systems with active membranes and Turing machines. Theoretical Computer Science 529, 69–81 (2014) 3. Alhazov, A., Pérez-Jiménez, M.J.: Uniform solution to QSAT using polarizationless active membranes. In: Durand-Lose, J., Margenstern, M. (eds.) Machines, Computations, and Universality, 5th International Conference, MCU 2007, Lecture Notes in Computer Science, vol. 4664, pp. 122–133. Springer (2007) 4. Ciobanu, G., Marcus, S., Păun, Gh.: New strategies of using the rules of a P system in a maximal way: Power and complexity. Romanian Journal of Information Science and Technology 12(2), 157–173 (2009) 5. Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Riscos-Nuñez, A., Romero- Campero, F.J.: Computational efficiency of dissolution rules in membrane systems. International Journal of Computer Mathematics 83(7), 593–611 (2006) 6. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C.: Membrane division, oracles, and the counting hierarchy. Fundamenta Informaticae 138(1–2), 97–111 (2015) 7. Murphy, N., Woods, D.: The computational power of membrane systems under tight uniformity conditions. Natural Computing 10(1), 613–632 (2011) 8. Murphy, N., Woods, D.: Uniformity is weaker than semi-uniformity for some membrane systems. Foundamenta Informaticae 134(1–2), 129–152 (2014) 9. Păun, Gh.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000) 10. Păun, Gh.: P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages and Combinatorics 6(1), 75–90 (2001) 11. Pérez-Jiménez, M.J., Romero-Jiménez, A., Sancho-Caparrini, F.: Complexity classes in models of cellular computing with membranes. Natural Computing 2(3), 265–284 (2003) 12. Porreca, A.E., Leporati, A., Mauri, G., Zandron, C.: P systems with elementary active membranes: Beyond NP and coNP. In: Gheorghe, M., Hinze, T., Păun, Gh., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, 11th International Conference, CMC 2010, Lecture Notes in Computer Science, vol. 6501, pp. 338–347. Springer (2011) 13. Păun, Gh., Pérez-Jiménez, M.J., Riscos Núñez, A.: Tissue P systems with cell division. International Journal of Computers, Communications & Control 3(3), 295–303 (2008) 14. Sosík, P.: The computational power of cell division in P systems: Beating down parallel computers? Natural Computing 2(3), 287–298 (2003) 15. Zandron, C., Ferretti, C., Mauri, G.: Solving NP-complete problems using P systems with active membranes. In: Antoniou, I., Calude, C.S., Dinneen, M.J. (eds.) Unconventional Models of Computation, UMC’2K, Proceedings of the Second International Conference, pp. 289–301. Springer (2001) 16. Zandron, C., Leporati, A., Ferretti, C., Mauri, G., Pérez-Jiménez, M.J.: On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution. Fundamenta Informaticae 87, 79–91 (2008) Building a basic membrane computer Alejandro Millan, Julian Viejo, Juan Quiros, Manuel J. Bellido, David Guerrero, and Enrique Ostua Grupo ID2 – Universidad de Sevilla (Spain) Email: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected] www.dte.us.es/id2 Summary. In this work, we present the building of two well-known membrane computers (squares generator and divisor test). Although they are very basic machines they present problems common to every P system (competition, parallel execution of rules, membrane dissolution, etc.) that have to be solved in order to get real emulations for them. The presented designs mimic the systems operation in a realistic way, by achieving both maximum parallelism and non-determinism, and demonstrating for the first time that a membrane computer can actually be built in silico. Our architectures fully emulate the membranes behaviour yielding to a performance of one transition per clock cycle, supposing a real physical realization of the mentioned machines. Key words: membrane computing, P system, digital circuit design, parallel computing, reconfigurable hardware, FPGA. 1 Introduction Membrane computing was introduced in 2000 by Gheorghe P˘aun [12]. This topic is based on living cells and the first models are defined as an hierarchical structure of compartments (membranes), which contains objects (chemicals), which evolve according to applicability rules (chemical reactions). However, membrane computing has a very important problem: implementation. This kind of computing is extremely powerful but is a machine-oriented solution so current efforts in this way have been focused on improve the simulation of such system on both software and hardware platforms. Several works exist on membrane computing from the hardware point of view. All of them have been focused on FPGA designing, trying to mimic the internal structure of P systems, in one way or another, into an electronic device. Firstly, in [13], authors present a development in which the membranes of the system evolve in a parallel way although, internally, rules in each membrane are executed sequentially. Also, the general functioning of the system is deterministic: rules are applied by following a pre-established order. 276 Millan et al. Reset indicator). Then, the machine starts computing executions of the P system, yielding the calculated answers to the 4-digit 7-segment display. These executions are carried out in a non-deterministic order but they cover all the possible combinations and generate all squares existing between 12and 632. Once all squares are shown, the machine halts and the Finish indicator is lighted on. For demonstration purposes only, the board clock frequency has been reduced to a human-visible one (ca. 25 Hz) and can be observed through the Clock indicator. Fig. 9. Computer 1 training board emulator: Clock indicator (LD7), Finish indicator (LD6), Master Reset indicator (LD0), Answer (7-segment display), and Master Reset button (BTN0). In a similar way, operation of Computer 2 board (Fig. 10) is also started by pressing the Master Reset button what feeds a random seed to the LFSRs present in the circuit. Then, the machine starts computing executions of the P system (each time a execution finishes the Data Valid indicator is lighted on). The executions are fed with random inputs and the machine shows them continuously on the 7- segment display (Numbers nand k). In order to facilitate humans to understand results, the board pauses execution when the division test is successful during Building a basic membrane computer 277 enough time to read the display. Also for demonstration purposes only, the board clock frequency has been reduced to a human-visible one (ca. 25 Hz) and can be observed through the Clock indicator. Fig. 10. Computer 2 training board emulator: Clock indicator (LD07), Data Valid indicator (LD1), Master Reset indicator (LD0), Number n(first two digits of 7-segment display), Number k(last two digits of 7-segment display), and Master Reset button (BTN0). The hardware details are presented in Table 1 and the device utilization is shown for both cases in Table 2 and Table 3 respectively. As we can observe, both computers consume a small portion of the available resources showing themselves as a very efficient design also in terms of hardware needs. Also, it is noticeable that register width has an important impact on resource utilization: 64-bit in the case of Computer 1 what yields to a maximum amount of ca. 1019 objects of each type (register values are of signed type). These register widths has been chosen according to the 4-digit displays available on the training boards. 278 Millan et al. Computer 1 Computer 2 Target Device xc3s1200e-4fg320 Clock Frequency 50 MHz Performance 50 Mtransition/s Register Width 64-bit 16-bit Table 1. Hardware details. Logic Utilization Used Available Utilization Number of Slice Flip Flops 625 17344 3% Number of 4 input LUTs 2434 17344 14% Number of occupied Slices 1345 8672 15% - Number of Slices containing only related logic 1345 1345 100% - Number of Slices containing unrelated logic 0 1345 0% Total Number of 4 input LUTs 2479 17344 14% - Number used as logic 2434 - Number used as route-thru 45 Number of bonded IOBs 18 250 7% - IOB Flip Flops 2 Number of BUFGMUXs 2 24 8% Number of MULT18X18SIOs 10 28 35% Average Fanout of Non-Clock Nets 2.27 Table 2. Device utilization for Computer 1. Logic Utilization Used Available Utilization Number of Slice Flip Flops 269 17344 1% Number of 4 input LUTs 842 17344 4% Number of occupied Slices 503 8672 5% - Number of Slices containing only related logic 503 503 100% - Number of Slices containing unrelated logic 0 503 0% Total Number of 4 input LUTs 958 17344 5% - Number used as logic 842 - Number used as route-thru 116 Number of bonded IOBs 19 250 7% - IOB Flip Flops 1 Number of BUFGMUXs 2 24 8% Number of MULT18X18SIOs 4 28 14% Average Fanout of Non-Clock Nets 3.25 Table 3. Device utilization for Computer 2. Building a basic membrane computer 279 4 Conclusion In this work, we have shown that it is possible to fully emulate a P system without loosing its intrinsic features of maximal parallelism and non-determinism. With that aim, machines presented in the foundational paper of the discipline (square generator and divisor test) have been built. Our designs mimic the internal structure of the P systems allowing the resulting hardware to perform as the theoretical system should: processing one transition per clock cycle. The systems evolve in a non-deterministic way and rules are applied in a maximal parallel derivation mode; what, to the best of our knowledge, supposes the first real emulation of a P system in-silico. References 1. Alonso, S., Fernandez, L., Arroyo, F., Gil, J.: A Circuit Implementing Massive Parallelism in Transition P Systems. International Journal ”Information Technologies and Knowledge”, vol. 2, pp. 35–42 (2008). 2. Bonde, V., Kale, A.: Design and Implementation of a Random Number Generator on FPGA. International Journal of Science and Research, vol. 4, no. 5, pp. 203–208 (2015). 3. Freund, R., Ibarra, O., Paun, A., Sosik, P., Yen H.: Catalytic P Systems. In ”The Oxford Handbook of Membrane Computing”, pp. 83–117, Oxford University Press (2009). ISBN:9780199556670 4. George, M., Alfke, P.: Linear Feedback Shift Registers in Virtex Devices. Xilinx Application Note, XAPP210 v1.3 (2007). 5. Martinez, V., Fernandez, L., Arroyo, F., Garcia, I.: A HW circuit for the application of Active Rules in a Transition P System Region. Proc. 4th International Conference Information Research and Applications, Varna (Bulgary), pp. 80–87 (2006). ISBN-10: 954-16-0036-0. 6. Martinez, V., Fernandez, L., Arroyo, F., Guiterrez, A.: HW Implementation of a Bounded Algorithm for Application of Rules in a Transition P-System. Proc. 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara (Romania), pp. 32-38 (2006). 7. Nguyen, V., Kearney, D., Gioiosa, G.: Balancing performance, flexibility and scalability in a parallel computing platform for membrane computing applications. Lecture Notes in Computer Science, vol. 4860, pp. 385–413 (2007). DOI:10.1007/978-3-540- 77312-2 24 8. Nguyen, V., Kearney, D., Gioiosa, G.: An implementation of membrane computing using reconfigurable hardware. Computing and Informatics, vol. 27, no. 3+, pp. 551569 (2008). 9. Nguyen, V., Kearney, D., Gioiosa, G.: An Algorithm for Non-deterministic Object Distribution in P Systems and Its Implementation in Hardware. Lecture Notes in Computer Science, vol. 5391, pp. 325–354 (2009). DOI:10.1007/978-3-540-95885-7 24 10. Nguyen, V., Kearney, D., Gioiosa, G.: An extensible, maintainable and elegant approach to hardware source code generation in Reconfig-P. The Journal of Logic and Algebraic Programming, vol. 79, no. 6, pp. 383-396 (2010). DOI:10.1016/j.jlap.2010.03.013 280 Millan et al. 11. Nguyen, V., Kearney, D., Gioiosa, G.: A Region-Oriented Hardware Implementation for Membrane Computing Applications. Lecture Notes in Computer Science, vol. 5957, pp. 385–409 (2010). DOI:10.1007/978-3-642-11467-0 27 12. Paun, G.: Computing with Membranes. Journal of Computer and System Sciences, vol. 61, pp. 108–143 (2000). DOI:10.1006jcss.1999.1693 13. Petreska, B., Teuscher, C.: A Reconfigurable Hardware Membrane System. Lecture Notes in Computer Science, vol. 2933, pp. 269–285 (2004). DOI:10.1007/978-3-540- 24619-0 20 14. Quiros, J., Millan, A., Viejo, J.: Implementacion sobre hardware reconfigurable de una arquitectura no determinista, paralela y distribuida de alto rendimiento, basada en modelos de computacion con membranas (Implementation on reconfigurable hardware of a non-deterministic, parallel, and distributed high performance architecture based on membrane computing models). PhD Thesis (2016). 15. Verlan, S., Quiros, J.: Fast Hardware Implementations of P Systems. Lecture Notes in Computer Science, vol. 7762, pp. 404–423 (2013). DOI:10.1007/978-3-642-36751-9 27 14th Brainstorming Week on Membrane Computing Laura Moreno Valero Universitat de Barcelona Email: [email protected] Three weeks ago we, a group of students from the University of Barcelona, were given the possibility of going to Seville, in order to attend a Workshop on Membrane Computing. The seven of us that went to the Workshop are all physics students and until the day we received the mail making us aware of that event, I had never heard about Membrane Computing, so I was kind of surprised the first time I read about it. In the university we have learned how to program with Python and Fortran. It was mostly on how to deal with physics problems, and how to find a solution using numerical methods. But what we saw when we arrived there was completely different, it was like entering another world of computation. While dealing with physics we are always reminded of how important is to keep in mind the physical part of the problem (i.e. how a given system is supposed to react when a field is applied, or if the result makes sense with what we can see in the reality), when programming with that new computational way you try to think how to model things but once you get it, you abstract (somehow) from reality and work with maths, or that is what I understood the first days. It was really difficult, specially at the beginning, as I was completely lost and maybe it could have been a better idea to have been previously informed about what the talks were about, or even to have an idea of what Membrane Computing meant. During the days I spent there I got to know that this picturesque way of computing is based on a system analogous to how alive cells behave or how elements in these ones evolve, using P-Systems (a computational model based on the structure of living cells that permits to perform calculations). Indeed, the inspiration came from how processes take place in cells. This new computing paradigm makes use of the structure of the cells, working with their different membranes and even with the environment. But it is not only something involving one cell, they also work with multiple ones, and so there are different models on which they can work. The most usual one is the cell-like system, which is the one I have already talked about. There are also other kinds of models, such as tissue-like or neural-like systems; the first ones are typically used to represent interaction between cells, or better said to 282 Laura Moreno Valero implement exchanges of elements between cells. The second one is used to analyse the behaviour of neurons, and tries to represent synapsis’ process. To work with all that stuff, a new language is needed, and so P-lingua takes action. P-lingua is a programming language to define P-Systems and it is highly used, as it is a language close to scientific notation, as well as from my point of view really visual of what it is going on. While we were attending the talks, we were invited to participate by doing a small project where we could use what we were learning, so our first idea was how could we use it in our own field, physics. We decided to reproduce two physical situations in order to see the process: the final result as well as their intermediate stages. These two projects were about: i) the Stern-Gerlach experiment, by modifying it a bit and ii) the Uranium-238 Decay Chain. At the beginning of our project, we tried to program a small code to get a bit used to the language, and I was truly surprised when I saw that it was not that weird to write it, and that by following one example one could understand almost perfectly what we were expressing. Nevertheless, I am aware that I only got a small view of how it works and that, for sure, it turns more difficult when you keep on programing more advanced things. However, even though it was not easy to understand most of the parts of the talks, people was extremely nice with us. One of my biggest fears was to break the dynamic of the event, as we could probably slow down the pace of it with our low level, but it surprised me a lot when everyone was inviting us to make as many questions as we wanted. Of course I did not want to disturb the pace of the event, but sometimes it was almost impossible to follow explanations, although I consider I learned a lot during that week, so to say, we got a slight insight on the general topic, but nothing really deep. Most of the conferences were interesting as it was another way of thinking, one which we are not so used to. Nevertheless, there was one that made me think of other fields and possible further applications. It was about the concept of Eco-P colonies. It is based on systems of only one membrane and in each of them we can find the objects that we want to study or see the final product of evolution. In Eco-P colonies, these objects do interact with a shared environment and this was the main point of the talk, titled P Colonies with Dynamic Environment. In order to evolve, the objects inside the membrane interact with the environment by some rules, specially rewriting and communication ones. The first ones basically transform the object into another one, or even into multiple objects. They are also called evolution rules and are basically applied inside the same membrane/entity (or even called agent), whereas the second kind of rules are based in an exchange between objects inside the membrane and objects outside it (environmental objects, usually symbolized by e). To sum up, Eco-P colonies would be a way to show mechanisms of generation and consumption from the environment. The system halts when no more rules can be applied to the objects, or no more exchange 14th Brainstorming Week on Membrane Computing 283 between the agents and the environment can be done. In fact, before the talk began, Petr Sos´ık, who gave the conference, showed us a video where we could see some bacterias multiplying, and we could see how the growth was really fast. This reminded me of a conference we were given some months ago, about cancer cells and which are their mechanisms to propagate cancer. I was wondering, when I heard about Eco-P colonies and their rules, if they could have some applications to Medicine, by adapting some of their rules to how cancer cells behave, or even in other cases. In fact, Membrane Computing modelizes non-deterministic processes, so somehow we could be able to implement the probabilities of a possible mutation (that produces the beginning of the disease). Another thing that surprised me was the characteristic of maximal parallelism when working with P-systems. At what we are used to, we have an order, so the first written commands are the first to be displayed, whereas in maximal parallelism, more than one rule can be executed at the same time. Indeed, it is based in the fact that the maximum number of rules that can be applied in each step, are applied, maximizing the number of processes that can be done at one time. To sum up, this experience has been really advantageous. First of all because I still do not know which is the field that interests me the most, but I have seen that computation keeps attracting me, and now even more than ever. Secondly, going there has made me realize of how vast this area can be and that it does not only reduce to solve some problems by numerical approximations but they are also a useful tool to visualize some difficult experiments or processes. And to end up with, it was a kind of personal growth, where we got to work together as a team and got the chance to talk with great people that taught us about science in general and more about research. Open Problems, Research Topics, Recent Results on Numerical and Spiking Neural P Systems (The “Curtea de Arge¸s 2015 Series”) Gheorghe P˘aun1, Tingfang Wu2, Zhiqiang Zhang2 1Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania [email protected] 2Key Laboratory of Image Information Processing and Intelligent Control School of Automation, Huazhong University of Science and Technology Wuhan 430074, Hubei, China [email protected], [email protected] Summary. A series of open problems and research topics are formulated, about numerical and spiking neural P systems, initially prepared as a working material for a three months research stage of the second and the third co-author in Curtea de Arge¸s, Romania, in the fall of 2015. Further problems were added during this period, while certain problems were addressed in this time; some details and references are provided for such cases. 1 Introduction In membrane computing there are numerous open problems and research topics in circulation, many of them also collected in systematic lists, compiled, for instance, for the yearly Brainstorming Week on Membrane Computing, see http://ppage.psystems.eu and www.gcn.us.es. Because the present list had initially a working material character, we do not provide here complete references. Furthermore, as the reader is supposed to be a researcher in membrane computing, we do not give basic definitions either (but we give details for the new classes of P systems considered). As a general reference we refer to the Handbook [8]. The list deals only with numerical P systems (in short, NP systems, [7]) and spiking neural P systems (in short, SNP systems, [3]). Some problems are more specific, many others are just general ideas, so that the first step in approaching them implies a formal definition (possibly, of new classes of NP or SNP systems). We recall some details from several papers written in Curtea de Arge¸s during the mentioned period of time. 292 Gh. P˘aun, T. Wu, Z. Zhang matter whether or not their values are zero (we say that we work without the NZP assumption), then the superscript 0 is removed. If one of the parameters m, n, r, k1, k2is not bounded, then we replace it with ∗. Here are part of the results proved in [17]: 1. NαM0NP1(poly1(1), V ar2, Pro2)−SLIN+ 16=∅, α ∈ {one, seq}. 2. SLIN+ 1⊂NαM0NP1(poly1(1), V ar∗, Pro∗), α ∈ {one, seq}. 3. NoneM0NP1(poly1(3), V ar∗, Pro∗) = NRE. 4. NseqM0NP2(poly1(3), V ar∗, Pro∗) = NRE. 5. NoneMENP1(poly1(3), V ar∗, Pro∗) = NRE. 6. NseqMENP2(poly1(3), V ar∗, P ro∗) = NRE. Also the possibility to generate strings with these systems was explored in [17]. N. Associate a language to a computation in an NP system. For instance, the values of a variable can form a string – in general, over an infinite alphabet (like in [2]), or on a finite alphabet. For instance, we can consider the binary string obtained by marking with 0 and 1 the odd and the even values of the distinguished variable. We can also “read” the natural numbers modulo a given constant k≥2, so that we can obtain strings over an alphabet with kletters. O. In particular, we can associate a language to an NP system by considering an external output: we add a variable also to the environment, which gets parts of the production of the skin compartment. This can be used both for computing numbers and strings (in the latter case, following the suggestions from the previous question). NP systems used as string generators were considered in [16]. A string is associated with a computation in a way somewhat similar to that adopted for spiking neural P systems: one just considers a special variable out in the environment which can appear in the repartition protocol of programs in the skin region of a numerical P system. At each step its value is first reset to zero, then it receives a new value. If at one step it receives several values from several programs, all these values are added up and the sum is the value it receives at this step. If the value is a number ibetween 1 to q, for some constant q, then the symbol biis added to the generated string. If at any step variable out receives a value which is greater than qor smaller than 0, then this computation aborts, no result is associated with it. In order to define the generated string, we need to define its end. This is clear in the case when the computation halts (no further program can be applied), and this can be taken as a definition of successful computations in purely enzymatic P systems. In non-enzymatic and in (non-purely) enzymatic systems the computations never halt, and then we define the end of the string by means of a signal, e.g., the step when the system sends out value 0. Because for purely enzymatic systems we have halting at our disposal, in this case we avoid sending out value 0, that is, this case is simply ignored. (For a general definition, however, a decision should be made also for value 0 sent out. A possibility is to proceed as in spiking neural P systems, where in such a case a special symbol, b0, is added to the string.) Open Problems on Numerical and SN P Systems 293 It still remains a case not covered: the steps when the system sends no value to variable out. We have two choices: to forbid such steps, by the definition of correct computations, or to proceed as in the case of spiking neural P systems and to associate the string λto the generated string (the string is not increased, the system can continue working). In this way, we define two languages generated by a numerical P system Π. If at each step a positive value is sent to variable out (with the exception of the last step, for non-enzymatic and for enzymatic P systems, when value 0 is sent out, marking the end), then we denote the generated language by Lres(Π) (with res coming from restricted). If in the steps when no value is sent out (neither 0) we interpret that the system adds λto the generated string, then the generated language is denoted by Lλ(Π). For an easier remembering, we synthesize the previous conventions/definitions in a table: Sending out Non-enzymatic & Enzymatic Purely enzymatic 1,2, . . . , q bibi <0 or > q abort abort 0 end signal ignored here nothing λor forbidden (res)λor forbidden (res) We denote by LαβNP γ m(polyn(r), V ark1, Prok2), α∈ {res, λ},β∈ {E, pE, −}, γ∈ {hal, fin}, the family of languages Lα(Π), generated by βnumerical P systems Π(E= enzymatic, pE = purely enzymatic; if the system is non-enzymatic, then βis omitted) with at most mmembranes, at most k1variables, and at most k2programs, with production functions which are polynomials of degree at most n, with integer coefficients, with at most rvariables in each polynomial; the superscript γ=hal is used for purely enzymatic systems, to indicate that the result is obtained when the system reaches a halting configuration; in the case when the end of the computation is defined by means of a signal (sending value 0 out), then we replace hal by fin. If one of the parameters m, n, r, k1, k2is not bounded, then we replace it with ∗. Here are some of the results proved in [16]: 1. LresβNPγ ∗(poly ∗n(∗), V ar∗, Pro∗)⊆REC,β∈ {E, pE, −},γ∈ {hal, fin}. 2. LresNPfin 1(poly1(1), V ar1, Pro2)−FIN 6=∅. 3. REG ⊆LresNPfin 1(poly1(1), V ar∗, Pro∗). 4. LresNPfin 1(poly1(4), V ar4, Pro4)−REG 6=∅.. 5. LresNPfin 1(poly1(4), V ar7, Pro6)−CF 6=∅. 6. The family LresNP fin 1(poly1(4), V ar4, Pro7) contain non-semilinear languages. 7. LrespENP hal 1(poly1(1), V ar2, Pro2)−FIN 6=∅. 8. FIN ⊂LrespENPhal 1(poly1(1), V ar∗, Pro∗). 9. REG ⊆LrespENPhal 1(poly1(2), V ar∗, Pro∗). 10. LrespENP hal 1(poly1(1), V ar6, Pro4)−REG 6=∅. 294 Gh. P˘aun, T. Wu, Z. Zhang 11. LrespENP hal 1(poly1(1), V ar9, Pro6)−CF 6=∅. 12. The family LrespENP hal 1(poly1(1), V ar7, Pro6) contains non-semilinear languages. 13. RE =LλpENP hal 1(poly1(2), V ar∗, Pro∗). 14. The family LresENPhal 1(poly1(2), V ar4, Pro6) contains non-semilinear languages. P. The external variable can be useful also for considering an NP system as a decidability device: an instance of a decision problem is encoded in the values of certain variables, and the values of a specified variable – maybe the external one (which is not used in any production function) – at a well defined moment (in a halting configuration, if halting can be defined and ensured) is the yes/no answer to the problem instance. Using NP systems in this way, as decidability devices, is a general research topic of definite interest. Which is the efficiency of this approach? Can NP-complete problems be solved in polynomial time in this framework? If not, which ingredients can help? Q. In general, what about NP systems with “active membranes”, i.e., with possibilities of dissolving, creating, dividing membranes? Are these operations useful for speeding-up the computations? R. Related also to the previous questions is the natural one of looking for interesting sequences of numbers and for interesting functions which can be computed by NP systems. Are there hard sequences/functions (hard with respect to Turing machines) which can be computed in a more efficient way with NP systems (maybe endowed with membrane manipulating rules)? S. The answer to the previous question can have a practical interest, e.g., for robot controllers. In this context, an exercise is natural: passing from robots acting in a 2D space, as those considered so far in membrane computing area, to 3D robots (drones, satellites). This is, expectedly, only a programming issue/exercise, but of interest in view of the popularity of 3D machineries which need an automatic (maybe intelligent) controller. T. In robot control there were useful numerical P systems with enzymes controlling the applicability of programs. A natural idea is to count the variables used as enzymes, then to try to keep this number as small as possible without diminishing the computing power (without losing the universality). The numbers of enzymes used so far in proofs is surprisingly large: For instance, the result in [11] can be written as NRE =NgenE∗NP∗(poly1(2), oneP) =NgenE776NP254(poly2(253), allP) (the subscript of E indicates the number of enzymes used) whereas the improvement of the last equality given in [10] can be written as Open Problems on Numerical and SN P Systems 295 NRE =NgenE427NP4(poly1(6), allP). The improvements of the above results in [4] are also not concerned with keeping under control the number of variables used as enzymes. In [18], the following – again surprising – results were obtained: NRE =NaccE1NP1(poly1(2), allP) =NgenE2NP1(poly1(2), oneP) =NaccE1NP1(poly1(2), oneP). What other results about enzymatic numerical P systems remain to be improved from this point of view? (What about small universal numerical P systems?) U. The previous problem is related to another way to control the use of programs, namely by means of thresholds, constants associated with programs, compared with the current values of variables in the production function or with the value of the production itself. See precise definitions in [19] and [15]. Universality results with a small number of thresholds are obtained in these papers. 4 Further Problems for SNP V. In the same way as NP systems can compute (also for robot controllers) functions f:Nn−→ Nm, such a function can be computed also by SNP systems. Can such systems be used for designing robot controllers? Which is the (practical and theoretical) efficiency of such an approach? W. On the one hand, the brain is supposed to be a non-Turing “computer”, on the other hand, it is supposed to have a deterministic conscious part and a nondeterministic unconscious part, the first one problems problems to the latter, this one proposing solutions, which are evaluated by the conscious part, and the process is iterated until either finding the right solution, or the problem is abandoned. Can such a strategy be implemented in terms of SNP systems? Is it possible to devise such a hybrid SNP system able of computing beyond Turing? X. What about extending to SNP systems other ideas currently explored in hypercomputing, see, e.g., [9]? Can they be formulated for SNP systems in such a way to make them compute beyond Turing (as – again – the human brain is supposed to do)? For instance, what about accelerated SNP systems, where the neurons “learn” during the functioning of the system. First time when a neuron uses a rule, the application of the rule lasts one time unit (the time is measured by an external clock, the user clock). Next time (does not matter how many steps the neuron is not working in between), the rule is applied in half of a user time unit – and so on, always half of the duration of the previous rule application. 296 Gh. P˘aun, T. Wu, Z. Zhang Thus, a neuron which works each step, in two external time units will perform an infinity of steps. The example in figure below shows an SN P system with only one spike inside, with neurons 1 and 4 working only once, but with neurons 2 and 3 working each step from step 2 on. Thus, in at most 2 external time units, neurons 2 and 3 send to neuron 4 any number of spikes. When mspikes are present in neuron 4, neuron 4 fires and the computation halts. Thus, irrespective how large is m, starting with only one spike inside, this system will produce mspikes (sent outside) in at most 4 external time units (but working internally a number of steps which depends on m).               =R ? 6 - } R o 1a a→a 2 a→a 3 a→a out am→am Conjectures: 1. Using the acceleration, we can solve NP-complete problems in polynomial time. (The first step is to find a suitable problem to be addressed in this framework.) 2. Accelerated P systems can go beyond Turing (can solve the halting problem – see the example of [1]); can this result be extended to SN P systems? Both these conjectures are, metaphorically, supported by the fact that the brain is efficient and “non-Turing”. Y. Add to SNP systems further biologically-inspired features, to get closer to the brain. Ideally, bring enough further features to the SNP systems so that processes taking place in the “real” brain can be modeled/simulated (at the level of biologists interest). Z. We have left to the end a very promising new class of SNP systems, which are no longer using regular expressions for controlling the application of spiking rules, but instead polarizations are associated with the neurons and the rules. The idea was explored in [12]. For the reader convenience, we recall the definition with full details. Open Problems on Numerical and SN P Systems 297 Aspiking neural P systems with polarizations (in short, a PSN P system) of degree m≥1 is a construct of the form Π= (O, σ1, σ2, . . . , σm, syn, in, out), where 1. O={a}is the singleton alphabet (ais called spike); 2. σ1, . . . , σmare neurons, of the form σi= (αi, ni, Ri),1≤i≤m, where: (a) αi∈ {+,0,−} is the initial polarization of neuron σi; (b) niis the initial number of spikes contained in σi; (c) Riis a finite set of rules of the following two forms: (i) α/ac→a;β, for α, β ∈ {+,0,−}, c ≥1 (spiking rules); (ii) α/as→λ;β, for α, β ∈ {+,0,−}, s ≥1 (forgetting rules); 3. syn ⊆ {1,2, . . . , m}×{1,2, . . . , m}with i6=jfor each (i, j)∈syn, 1≤i, j ≤m (synapses between neurons); 4. in, out ∈ {1,2, . . . , m}indicate the input and output neurons, respectively. Note that the definition of PSN P systems is the same as the usual definition of SN P systems given in the literature, with two differences: the applicability of a rule is not determined by checking the total number of spikes contained in the neuron against a regular expression associated with the rule, but the neurons have charges and a rule can be applied only if the neuron has the charge indicated in the left hand side of the rule. Of course, in order to use a rule, the total number of spikes inside the neuron should not be less than the number of spikes consumed by the rule. Moreover, the neurons not only send out spikes, but also charges, even when using forgetting rules. A spiking rule α/ac→a;βis used as follows. If the neuron σihas the charge α and it contains at least cspikes, then the rule can be applied, and its application means that cspikes are consumed, the neuron fires and produces a spike, which carries the charge β. The spike is replicated and each neuron σjsuch that (i, j)∈ syn receives the spike and the charge β. The output neuron also sends spikes out of the system, but no electrical charge is sent out (it is “lost” in the environment). A forgetting rule α/as→λ;βis applied when the neuron has the charge αand contains at least sspikes; sspikes are removed from the neuron and the charge β is sent to all neurons σjsuch that (i, j)∈syn. (Note that we do not necessarily forget all spikes, as in the case of usual SN P systems, where exactly sspikes should be present in order to use a forgetting rule as→λ.) After a neuron receives charges from other neurons, we perform a computation of charges inside the neuron as described below: 298 Gh. P˘aun, T. Wu, Z. Zhang 1. several positive charges (+), several neutral charges (0), several negative charges (−) lead to one positive charge (+), one neutral charge (0), one negative charge (−), respectively; 2. a positive charge (+) and a negative charge (−) cancel each other and give the neutral charge (0); 3. a positive charge (+) or a negative charge (−) is not changed by a neutral charge (0). We stress that (i) the computation of charges takes no time; (ii) step 1 of the above computation of charges is done first. For example, if a given neuron which is initially neutral receives two positive charges and one negative charge, then first the two positive charges lead to one positive charge, after that the positive charge and the negative charge cancel each other, thus the neuron remains neutral. As usual in SN P systems, a global clock is assumed, marking the time for the whole system, hence the functioning of the system is synchronized. In each time unit, if a neuron σican use one of its rules, then a rule from Rimust be used. If several rules can be used at the same time in a neuron, then the one to be applied is chosen non-deterministically. Thus, the rules are used in a sequential manner in each neuron, but the neurons function in parallel with each other. The configuration of the system is described by both the number of spikes and the charge of each neuron; thus, the initial configuration of the system is C0=hn1, n2, . . . , nm;α1, α2, . . . , αmi. Using the rules as described above, one can define transitions among configurations. A transition between two configurations C1, C2is denoted by C1⇒C2. Any sequence of transitions starting from the initial configuration is called a computation. A computation is successful if it reaches a configuration where no rule can be used in any neuron of the system. We say that the computation is halting. A PSN P system can be used as a generative, an accepting, or a computing device. With any computation, halting or not, we associate a spike train, the sequence of symbols 0 and 1 describing the behavior of the output neuron: 1 indicates a spiking step, 0 indicates a step when no spike exits the system. With a spike train, aresult of a computation can be defined in several ways. For instance, the result of a computation can be defined as usual in general SN P systems: we only consider the first two time instances t1and t2that neuron out spikes and we say that the number t2−t1is computed/generated by Π. The set of all numbers generated in this way by a PSN P system Πis denoted by N2(Π) (the subscript 2 indicates that the computation result is encoded by the time distance between the first two spikes of any computation). In the generative case, the neuron with label in is ignored. In the accepting mode, the neuron with label out is ignored. A number nis introduced in the system, by introducing a sequence 10n−11 in neuron in (two spikes are introduced, at a time distance of nsteps) and this number is accepted if the computation halts. When both an input and an output neuron are considered, the PSN P systems can be used to compute numerical functions. In order to compute a function f: Open Problems on Numerical and SN P Systems 299 Nk→N,knatural numbers n1, . . . , nkare introduced into the system by “reading” from the environment a spike train of the form z= 10n1−110n2−11. . . 10nk−11. Note that exactly k+1 spikes are “read”, that is, after the last spike, it is assumed that no further spike is sent to the input neuron. The result of the computation is also encoded as the distance between the first two spikes emitted by the output neuron with the restriction that the system outputs exactly two spikes and halts (maybe some further steps after the second spike), hence it produces a spike train of the form 0b10r−110dfor some b, d ≥0 with r=f(n1, n2, . . . , nk). The system outputs no spike in the b≥0 steps from the beginning of the computation until the first spike. We denote N2PSNP(chp) the family of all sets of numbers N2(Π) generated by PSN P systems with at most pcharges. The two results proved in [12] are the following: 1. NRE =N2PSNP(ch3). 2. There exists a universal PSN P system (with three charges) for computing functions, having 164 neurons. The proofs are rather complex, at least in comparison with the proofs of the corresponding results for usual SN P systems, and this is due to the fact that the polarizations provide a much weaker control on the applicability of the rules in neurons than the regular expressions. Again, many research topics remain to be explored. Practically the whole program of investigation carried on usual SN P systems has to be explored also for the new type of spiking neural P systems: normal forms (can we get rid of forgetting rules?), using extended rules (producing more than one spike can help, e.g., in simplifying the proofs?), generating strings or infinite sequences, considering asynchronous computations or a parallel/exhaustive use of spiking rules in each neuron, adding astrocytes or other biology inspired ingredients, and so on and so forth. Another idea is to consider cell-like PSN P systems; polarized cell-like SN P systems seem to be challenging to investigate (maybe not universal). There also appear specific open problems. Of a definite interest is the question whether or not the number of electrical charges considered in the universality proof from [12], three, can be decreased. Which is the power of PSN P systems with 2 charges, or even without any charge? Is any of the corresponding classes of computing devices sub-universal? If so, which are the properties (size, closure, decidability) of the corresponding family of sets of numbers or of languages generated? Finally: can the number of neurons in universal PSN P systems be (significantly) decreased? (We are pessimistic about this, as clever codifications in terms of the number of spikes, as usual for standard SN P systems, do not seem to help in the absence of regular expressions.) Definitely, we believe that SN P systems with polarizations deserve further research efforts. Acknowledgments. This work of T. Wu and Z. Zhang was supported by the National Natural Science Foundation of China (61033003, 91130034, and 300 Gh. P˘aun, T. Wu, Z. Zhang 61320106005), Ph.D. Programs Foundation of Ministry of Education of China (2012014213008), and the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012). References 1. C. Calude, Gh. P˘aun: Bio-steps beyond Turing, CDMTCS Research Report 226, Univ. of Auckland (November 2003), and BioSystems, 77 (2004), 175–194 2. J. Dassow, G. Vaszil: P finite automata and regular languages over countable infinite alphabets. Proc. WMC 2006, Leiden, The Netherlands (H.J. Hoogeboom et al., eds.), LNCS 4361, Springer, 2006, 367–381. 3. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. 4. A. Leporati, A.E. Porreca, C. Zandron, G. Mauri: Improving universality results on parallel enzymatic numerical P systems. Proceedings of 11th Brainstorming Week on Membrane Computing, Sevilla, February 2013, Fenix Editora, Sevilla, 2013, 177–200. 5. A. Leporati, A.E. Porreca, C. Zandron, G. Mauri: Enzymatic numerical P systems using elementary arithmetic operations. Membrane Computing. Proc. 14th Intern. Conf., CMC2013, Chi¸sin˘au, August 2013, LNCS 8340 (A. Alhazov et al., eds.), Springer, Berlin, 2014, 249–264. 6. A.B. Pavel, C.I. Vasile, I. Dumitrache: Robot localization implemented with enzymatic numerical P systems. Proc. Conf. Living Machines 2012, LNCS 7375, Springer, 2012, 204–215. 7. Gh. P˘aun, R. P˘aun: Membrane computing and economics: Numerical P systems. Fundamenta Informaticae, 73 (2006), 213–227. 8. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. 9. A. Syropoulos: Hypercomputation: Computing Beyond the Church-Turing Barrier. Springer, Berlin, 2008. 10. C.I. Vasile, A.B. Pavel, I. Dumitrache: Universality of enzymatic numerical P systems. International Journal of Computer Mathematics, 90(4) (2013), 869–879. 11. C.I. Vasile, A.B. Pavel, I. Dumitrache, Gh. P˘aun: On the power of enzymatic numerical P systems. Acta Informatica, 49(6) (2012), 395–412. 12. T. Wu, A. P˘aun, Z. Zhang, L. Pan: Spiking neural P systems with polarizations. Submitted, 2015. 13. T. Wu, Z. Zhang, L. Pan: On string languages generated by cell-like spiking neural P systems. Submitted, 2015. 14. T. Wu, Z. Zhang, Gh. P˘aun, L. Pan: Cell-like spiking neural P systems. Submitted, 2015. 15. Z. Zhang, L. Pan: Numerical P systems with production thresholds. Submitted, 2015. 16. Z. Zhang, T. Wu, L. Pan, Gh. P˘aun: On string languages generated by numerical P systems. Submitted, 2015. 17. Z. Zhang, T. Wu, A. P˘aun, L. Pan: Numerical P systems with migrating variables. Submitted, 2015. 18. Z. Zhang, T. Wu, A. P˘aun, L. Pan: Universal enzymatic numerical P systems with a small number of enzymatic variables. Submitted, 2015. 19. Z. Zhang, J. Xu, L. Pan: Numerical P systems with thresholds. Submitted, 2015. Individual memory about the 14th Brainstorming Week on Membrane Computing Ariadna Ribes Metidieri Universitat de Barcelona Email: [email protected] Summary. The main objective of this memory is to stand out one of the research methods for developing new P system models observed during the 14th Brainstorming Week on Membrane Computing. Firstly, a general overview of P systems is provided. To continue, the use of register machines in order to justify completeness and universality is justified. And to end up, an example of the method is provided. 1 Motivation and experience The motivation for investigating further into this subject arose when observing that new computational model could be proposed. However, computability (the model’s capability of acting as a computer) was always required, meaning that each new proposed model was tested versus Turing completeness. i.e., every proposed model should be demostrated to be capable of performing a computation. The proof of the universality of the P systems can be attained using different methods, but the utilization of the Register Machines was widely promoted. Moreover, through ’Rudi’s fancy homework’ we learned that register machines were in fact, simple but really useful interesting devices. 2 General Overview Membrane computing is a biologically-inspired research branch in the field of computer science which starts from the assumption that processes taking place in the structure of a living cell can be interpreted as a computation and it gathers the study of different kinds of P systems. P systems are the devices used in this new computing paradigm which performs calculations based on the idea of a hierarchical arrangement of membranes acting as channels of communication. These systems are inspired in cellular structures, being the cell-like, tissue-like and Spiking Neural P systems current developed models [1]. All three models are based on cells, but seems important to recall that they are formal models which should not be considered as representations of the truth. 308 Patricia Ribes Metidieri For instance, if the states being passed are polarisations Q={+,−,0}(which represent the electrical charge of the membrane), a possible state combining function would assign positive polarisation to the neuron receiving the spikes if more positive than negative polarisations were received, negative polarisation in the opposite case and null polarisation if the number of received + and −polarisations were the same. Finally, the time between firing and spiking is 0 for all the neurons. In contrast with SN P systems, where computational completeness is achieved by allowing the non-realistic notion that the number of spikes within each cell is not bounded, the ESN P systems with Transmittable States are powerful enough for universal computation considering the number of spikes in each active neuron reduced to 1 and replacing the unbounded number of spikes to an unbounded number of neurons. This model can reproduce the rules of Conway’s Game of Life using only 2 states Q={0,1}(which represent ”dead” and ”alive”) and, since this kind of cellular automata has the power of a universal Turing machine, by reproducing the rules of the Game, the computational completeness of the ESN P systems with Transmittable States is proved. References 1. Gh. P˘ aun Membrane Computing: An Introduction 2. J. M. Cecilia, J. M. Garc´ ıa, G. D. Guerrero, M. A. Mart´ ınez-del-Amor, I. P´ erez-Hurtado, M. J. P´ erez-Jim´ enez Simulation of P systems with active membranes on CUDA 3. J. Wang, L. Zou, H. Peng, G. Zhang An extended Spiking Neural P System for fuzzy knowledge representation 4. M. Ionescu, Gh. P˘ aun, T. Yokomori Spiking Neural P Systems 5. R. Freud, S. Ivanov Extended SNP systems with States [Document text truncated for crawler view.]