Fifth Brainstorming Week on Membrane Computing.Sevilla, January 29–February 2, 2007 : RGNC REPORT 01/2007

Fifth Brainstorming Week on Membrane Computing Sevilla, January 29–February 2, 2007 Miguel Angel Guti´errez-Naranjo, Gheorghe P˘aun, Alvaro Romero-Jim´enez, Agust´ın Riscos-N´u˜nez Editors Fifth Brainstorming Week on Membrane Computing Sevilla, January 29–February 2, 2007 Miguel Angel Guti´errez-Naranjo, Gheorghe P˘aun, Alvaro Romero-Jim´enez, Agust´ın Riscos-N´u˜nez Editors RGNC REPORT 01/2007 Research Group on Natural Computing Sevilla University F´enix Editora, Sevilla, 2007 c Autores ISBN: 978-84-611-6776-0 Dep´osito Legal: SE-2563–07 Edita: F´enix Editora C/ Patricio S´aenz 13, 1 B 41004 Sevilla [email protected] Telf. 954 41 29 91 Preface This volume contains most of the papers emerged from the Fifth Brainstorming Week on Membrane Computing (BWMC), held in Sevilla, from January 29 to February 2, 2007, in the organization of the Research Group on Natural Computing from the Department of Computer Science and Artificial Intelligence of Sevilla University. The first edition of BWMC was organized at the beginning of February 2003 in Rovira i Virgili University, Tarragona, and the next three editions took place in Sevilla at the beginning of February 2004, February 2005, and February 2006, respectively. Keeping the tradition of previous meetings in this series, the fifth BWMC was conceived as a period of active interaction among the participants, with the emphasis on exchanging ideas and cooperation, hence with only a few (“provocative”) presentations scheduled in the first days of the meeting and with most of the time devoted to the joint work. The efficiency of this type of meetings was again proved to be very high and the present volume proves this assertion. Pleasantly enough, after almost eight years since the research in this area was initiated, membrane computing is still an expanding research field, both with many theoretical issues of current interest, new problems and new research ideas, and with a growing number of applications, especially in biology and medicine. 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 the papers from these volumes will be considered for publication in a special issues of International Journal of Unconventional Computing (after the first BWMC, a special issue of Natural Computing – volume 2, number 3, 2003, and a special issue of New Generation Computing – volume 22, number 4, 2004, were published; papers from the second BWMC have appeared in a special issue of Journal of Universal Computer Science – volume 10, number vi Preface 5, 2004, as well as in a special issue of Soft Computing – volume 9, number 5, 2005; a selection of papers written during the third BWMC have appeared in a special issue of International Journal of Foundations of Computer Science – volume 17, number 1, 2006); after the fourth BWMC a special issue of Theoretical Computer Science was edited – volume 372, numbers 2-3, 2007. Other papers elaborated during the fifth 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 Milano web page http://psystems.disco.unimib.it (with a mirror in China, at http://bmc.hust.edu.cn/psystems). The list of participants as well as their email addresses are given below, with the aim of facilitating the further communication and interaction: 1. Ardelean Ioan, Institute of Biology of the Romanian Academy, Bucharest, Romania, [email protected] 2. Balbont´ın-Noval Delia, University of Sevilla, Spain, [email protected] 3. Bernardini Francesco, Leiden University, The Netherlands, [email protected] 4. Bianco Luca, University of Verona, Italy, [email protected] 5. Busi Nadia, University of Bologna, Italy, [email protected] 6. Cazzaniga Paolo, University of Milano-Bicocca, Italy, [email protected] 7. Colomer Cugat M. Angels, University of Lleida, Spain, [email protected] 8. Cord´on Franco Andr´es, University of Sevilla, Spain, [email protected] 9. D´ıaz-Pernil Daniel, University of Sevilla, Spain, [email protected] 10. Ferretti Claudio, University of Milano-Bicocca, Italy, [email protected] 11. Freund Rudolf, Technical University Wien, Austria, [email protected], [email protected] 12. Garc´ıa Arnau Marc, Polytechnical University of Madrid, Spain, [email protected] 13. Gheorghe Marian, University of Sheffield, United Kingdom, [email protected] 14. Graciani D´ıaz Carmen, University of Sevilla, Spain, [email protected] 15. Guti´errez-Naranjo Miguel Angel, University of Sevilla, Spain, [email protected] Preface vii 16. Ionescu Mihai, University of Tarragona, Spain, mihai [email protected] 17. Leporati Alberto, University of Milano-Bicocca, Italy, [email protected] 18. Mardare Radu, University of Trento, Italy, [email protected] 19. Mauri Giancarlo, University of Milano-Bicocca, Italy, [email protected] 20. Nepomuceno-Chamorro Isabel, University of Sevilla, Spain, [email protected] 21. Nepomuceno-Chamorro Juan Antonio, University of Sevilla, Spain, [email protected] 22. P˘aun Gheorghe, Institute of Mathematics of the Romanian Academy, Bucharest, Romania, and University of Sevilla, Spain, [email protected], [email protected] 23. P´erez-Jim´enez Mario de Jesus, University of Sevilla, Spain, [email protected] 24. Pescini Dario, University of Milano-Bicocca, Italy, [email protected] 25. Potapov Igor, University of Liverpool, United Kingdom, [email protected] 26. Ramirez Martinez Daniel, Univ. of Sevilla, Spain, [email protected] 27. Riscos-N´u˜nez Agust´ın, University of Sevilla, Spain, [email protected] 28. Romero-Campero Francisco Jos´e, University of Sevilla, Spain, [email protected] 29. Romero Jim´enez Alvaro, University of Sevilla, Spain, [email protected] 30. Sancho Caparrini Fernando, University of Sevilla, Spain, [email protected] 31. Sburlan Drago¸s, Constant¸a University, Romania, [email protected] 32. Sempere Luna Jos´e Mar´ıa, Polytechnical University of Valencia, Spain, [email protected] 33. Vaszil Gy¨orgy, Hungarian Academy of Sciences, Budapest, Hungary, [email protected] 34. Verlan Sergey, University of Paris 12, Creteil, France, [email protected] 35. Yokomori Takashi, Waseda University, Japan, [email protected] 36. Zandron Claudio, University of Milano-Bicocca, Italy, [email protected] viii Preface As mentioned above, the meeting was organized by the Research Group on Natural Computing from Sevilla University (http://www.gcn.us.es)– and all the members of this group were enthusiastically involved in this (not always easy) work. The meeting was supported from various sources: (i) Proyectos de Investigaci´on TIN2005–09345–C04–01 y TIN2006–13425 del Ministerio de Educaci´on y Ciencia of Spain, (ii) Grupo de Investigaci´on en Computaci´on Natural (PAI TIC 193) de Junta de Andalucia, (iii) III Plan Propio de la Universidad de Sevilla, as well as by the Department of Computer Science and Artificial Intelligence from Sevilla University. Gheorghe P˘aun Mario de Jes´us P´erez-Jim´enez (Sevilla, April 10, 2007) Contents Partial Versus Total Halting in P Systems A. Alhazov, R. Freund, M. Oswald, S. Verlan ............................ 1 Magnetotactic Bacteria and Their Significance for P Systems and Nanoactuators I.I. Ardelean, M. Ignat, C. Moisescu ................................... 21 Networks of Cells and Petri Nets F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan ................ 33 Extended Spiking Neural P systems with Excitatory and Inhibitory Astrocytes A. Binder, R. Freund, M. Oswald, L. Vock .............................. 63 Information Theory over Multisets C. Bonchi¸s, C. Izba¸sa, G. Ciobanu ..................................... 73 VisualTissue: A Friendly Tool to Study Tissue P Systems Solutions for Graph Problems R. Borrego-Ropero, D. D´ıaz-Pernil, J.A. Nepomuceno .................. 87 Towards a Causal Semantics for Brane Calculi N. Busi ................................................................. 97 Subset Sum with Tissue P Systems with Cell Division D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez ................................. 113 Polarizationless P Systems with Active Membranes Working in the Minimally Parallel Manner R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez ............................. 131 Spiking Neural P Systems: Stronger Normal Forms M. Garc´ıa-Arnau, D. P´erez, A. Rodr´ıguez-Paton, P. Sosik ............. 157 6 A. Alhazov, R. Freund, M. Oswald, S. Verlan computation of Πyielding a vector of non-negative integers for the numbers of terminal symbols in the output membrane i0; observe that here we do not count the non-terminal objects present in the output membrane. The set of results of all halting computations possible in Πis denoted by P s (Π), respectively. Below, we shall consider variants of P systems using only rules of very restricted types α. The family of all sets of vectors of non-negative integers computable by P systems with dmembranes and using rules of type αis denoted by P sgOPd(α, max, H). When using the minimally parallel derivation mode, in each derivation step we choose a multiset of rules from the Riin such way that to this chosen multiset no rule from a set Rjfrom which no rule has been taken so far, could be added anymore to be applied in parallel with the rules already chosen. In the asynchronous and the sequential derivation mode, in each derivation step we apply an arbitrary number of rules/ exactly one rule, respectively. The corresponding families of sets of vectors of non-negative integers generated by P systems with dmembranes and using rules of type αare denoted by P sgOPd(α, X, H), X∈ {min, asyn, sequ}. If instead of the total halting we take partial halting, i.e., computations halting as soon as in at least from one set of rules no rule is applicable anymore, the corresponding families are denoted by P sgOPd(α, X, h), X∈ {max, min, asyn, sequ}. All these variants of P systems can also be considered as accepting devices, the input being given as the numbers of objects in the distinguished membrane i0. The corresponding families of sets of vectors of non-negative integers accepted by P systems with dmembranes and using rules of type αare denoted by P saOPd(α, X, Y ), X ∈ {max, min, asyn, sequ},Y∈ {H, h}. In this case, it also makes sense to consider deterministic P systems, i.e., systems where for each configuration obtained in this system we can derive at most one configuration. The corresponding families are denoted by DP saOPd(α, X, Y ). If we only count the number of terminal objects and do not distinguish between different (terminal) objects, in all the definitions given above, we replace P s by N. When the parameter dis not bounded, it is replaced by ∗. In the following, we now consider several restricted variants of membrane rules with permitting contexts well known from the literature. P systems with symport/antiport rules For definitions and results concerning P systems with symport/antiport rules, we refer to the original paper [18] as well as to the overview given in [22]. An antiport rule is a rule of the form u[x→x[uusually written as (x, out;u, in), ux 6=λ. Asymport rule is of the form [x→x[ or u[→[uusually written as (x, out), x6=λ, or (u, in), u6=λ, respectively. The weight of the antiport rule (x, out;u, in) is defined as max {|x|,|u|}. Using only antiport rules with weight kinduces the type αusually written as antik. The weight of a symport rule (x, out) or (u, in) is defined as |x|or |u|, respectively. Using only symport rules with weight kinduces the type αusually written as Partial Versus Total Halting in P Systems 7 symk. If only antiport rules (x, out;u, in) of weight ≤2 and with |x|+|u| ≤ 3 as well as symport rules of weight 1 are used, we shall write anti20. P systems with conditional uniport rules Aconditional uniport rule is a rule of one of the forms ab [→b[a, [ab →a[b, a[b→[ab ,b[a→ab [ , with a, b ∈V; in every case, the object ais moved across the membrane, whereas the object bstays where it is. Using only rules of that kind induces the type uni1,1. Conditional uniport rules were first considered in [24] for the case of tissue P systems, showing computational completeness with maximal parallelism and total halting (using 24 cells). P systems with boundary rules and evolution/communication P systems In P systems with boundary rules as defined in [4], evolution rules as well as communication rules with permitting contexts are considered. Usually, we only consider evolution rules that are non-cooperative, i.e., of the form a→vwith a∈Vand v∈V∗; a rule a→v∈Ricorresponds to [a→[v∈Riin our general notation. The communication rules are symport or antiport rules with permitting contexts, i.e., of the form u w[x z→x w[u z. In [5], boundary rules of the form u[x→v[yare considered, i.e., rewriting on both sides of the membrane. In evolution/communication P systems as introduced in [6], we allow non-cooperative evolution rules as well as antiport (of weight k) and symport rules (of weight l), and we denote this type of rules by (ncoo, antik, syml). 3 Results After recalling some general results for the new variant of partial halting already established in [13], which immediately yield comparable computational completeness results in the case of antiport P systems for total and partial halting, we prove that P systems with permitting contexts working in the sequential, in the asynchronous or even in the minimally parallel derivation mode and with partial halting can only generate Parikh sets of matrix languages (regular sets of non-negative integers). On the other hand, specific variants of P systems with permitting context such as P systems with antiport rules, P systems with symport rules, P systems with conditional uniport rules, and evolution/communication P systems together with the newly introduced variant of minimal parallelism and with total halting are computationally complete. 3.1 General Observations Looking carefully into the definitions of the derivation modes as well as the halting modes explained above, we observe the following general results already established in [13]: 8 A. Alhazov, R. Freund, M. Oswald, S. Verlan Theorem 1. Any variant of P systems yielding a family of sets of non-negative integers Fwhen working in the derivation mode X,X∈ {max, min, asyn, sequ}, with only one set of rules assigned to a single membrane and stopping with total halting yields the same family Fwhen working in the derivation mode Xwith only one set of rules assigned to a single membrane when stopping with partial halting, too. Theorem 2. Any variant of P systems yielding a family of sets of non-negative integers Fwhen working in the derivation mode X,X∈ {asyn, sequ}, with only one set of rules assigned to a single membrane and stopping with total or partial halting, respectively, yields the same family Fwhen working in the minimally parallel derivation mode and stopping with the corresponding halting mode, too. For any P system using rules of type α, with a derivation mode X,X∈ {min, asyn, sequ}, and partial halting, we only get Parikh sets of matrix languages (regular sets of non-negative integers): Theorem 3. For every X∈ {min, asyn, sequ}, PsgOP∗(α, X, h)⊆P sMAT λand NgOP∗(α, X, h)⊆NREG. Proof. We only prove P sgOP∗(α, X, h)⊆P sMAT λ; the second inequality NgOP∗(α, X, h)⊆NREG is a direct consequence of the first one, having in mind that NREG =PsMATλ(1). Hence, let us start with a P system Π= (V, T, E, µ, w1, . . . , wd, R1, . . . , Rd, io) using rules of a specific type α, working with the derivation mode X. The stopping condition h– partial halting – then guarantees that in order to continue a derivation there must exist a sequence of rules hr1, . . . , rdiwith ri∈Ri, 1 ≤i≤d, such that all these rules are applicable in parallel. We now consider all functions δwith δ(i, r)∈ {0,1}and δ(i, r) = 1 if and only if the rule r∈Ri, 1 ≤i≤d, is assumed to be applicable to the current sentential form in a matrix grammar GM=VM, T , S, Mgenerating representations of all possible configurations computable in the given P system Πwith the representation of an object ain membrane ias (i, a). We start with the matrix (S→Kh (w)) where h(w) is a representation of the initial configuration. A derivation step in Πthen is simulated in GMas follows: (i) We non-deterministically choose some δas described above and use the matrix (K→K(δ)). Afterwards, we use the matrix (K(δ)→K0(δ), s1, ..., sm) where each subsequence sj, 1 ≤j≤m, checks the applicability of a rule r∈Riwith δ(i, r) = 1. For checking the applicability of u w[x z→v w[y z∈Ri, we have to check for the appearance of uw in membrane ˆı(the outer region of membrane i) and for the appearance of xz in the (inner) region of membrane i. This can be done by the subsequence ((ˆı, uw)→(ˆı, uw),(ˆı, uw)→(ˆı, uw),(i, xz)→(i, xz),(i, xz)→(i, xz)), where (i, v)→(i, v), for v=v1...vh,vj∈V, 1 ≤j≤h,h≥0, is a shortcut for the sequence ((i, v1)→(i, v1), ..., (i, vh)→(i, vh)) etc. (ii) After that, we non-deterministically guess a sequence of rules hr1, . . . , rdi with ri∈Ri,ri=u(i) w(i)[x(i) z(i)→v(i) w(i)[y(i) z(i), and δ(i, ri) = 1, 1 ≤ Partial Versus Total Halting in P Systems 9 i≤d, such that all these rules are applicable in parallel. This can be checked by the corresponding matrix (K0(δ)→K00 (δ), t1, ..., td, t0 1, ..., t0 d) with the subsequences ti,t0 i, 1 ≤i≤d, being defined (in the shortcut notation as above) by ti=(ˆı, u (i)) →ˆı, u (i),(i, x (i)) →i, x (i) and t0 1= ˆı, u (i)→(ˆı, u (i)) ,i, x (i)→(i, x (i)). Observe that only the objects in u(i) and x(i) are assigned to the rule ri, whereas the permitting contexts w(i) and z(i) may be contexts for another rule or be affected themselves by another rule, and, moreover, that the applicability of the rules themselves has already been checked in (i). (iii) Finally, we take different matrices depending on the derivation mode: 1. In the sequential derivation mode, we only have to take all possible matrices simulating the application of one rule u w[x z→v w[y z∈Riwith δ(i, r) = 1: (K00 (δ)→Khˆı(v)hi(y),(ˆı, u)→λ, (i, x)→λ), where the morphisms hjare defined by hj(a) = (j, a), 0 ≤j≤d,a∈V, except h0(a) = λfor a∈E (these symbols, by definition, are available in an unbounded number in the environment). 2. In the asynchronous derivation mode, we have to allow an arbitrary number of rules to be applied in parallel; we simulate the application of rules sequentially, priming the results such that they cannot be used immediately. Finally, if for the current derivation step, the application of no further rule is intended, we can deprime the result symbols to be available for the simulation of the next derivation step. In sum, we use the matrices (K00 (δ)→K000 (δ)), (K000 (δ)→K000 (δ)h0 ˆı(v)h0 i(y),(ˆı, u)→λ, (i, x)→λ) – where the morphisms h0 jare defined by h0 j(a) = (j, a0), 0 ≤j≤d,a∈V, except h0 0(a) = λfor a∈E – for every rule u w[x z→v w[y z∈Riwith δ(i, r) = 1, as well as K000 (δ)→K(δ), K(δ)→K(δ),(j, a0)→(j, a), 0 ≤j≤d,a∈V, and finally K(δ)→K. 3. For the minimally parallel mode, instead of (K00 (δ)→K000 (δ)) as in 2, we simulate the application of a sequence of rules hr1, . . . , rdiwith ri∈Ri, 1 ≤i≤d,ri=u(i) w(i)[x(i) z(i)→v(i) w(i)[y(i) z(i), and δ(i, ri) = 1 such that all these rules are applicable in parallel, which is accomplished by the matrix K00 (δ)→K000 (δ)h0 ˆ 1(v)h0 1(y)...h0 ˆ d(v)h0 d(y), ˆ 1, u (1)→λ, (1, x (1)) →λ, ..., ˆ d, u (d)→λ, (d, x (d)) →λ. As a technical detail we have to mention that it does not matter whether all the primed symbols are deprimed again, this would just make them unavailable during the next steps. Any sentential form containing primed symbols is considered to be non-terminal, hence, it cannot contribute to L(GM). Moreover, we have to point out that every symbol e∈Efrom the environment being available there in an unbounded number neither needs to be checked for appearance in ˆ 1 ( = 0) nor to be generated/eliminated or primed/deprimed, i.e., rules like (0, e)→λ, (0, e)→(0, e), (0, e)→(0, e) have to be omitted. 10 A. Alhazov, R. Freund, M. Oswald, S. Verlan Finally, we may stop the simulation of computation steps of Πand use the matrices (K→F), (F→F, (i, a)→(i, a)) for every object aand every membrane i, and the final matrix (F→λ) for generating a terminal string of GM. Now, we have to extract the representations of final configurations from L(GM): For every possibility of choosing a sequence of rules hr1, . . . , rdiwith ri∈Ri, 1 ≤i≤d, such that all these rules are applicable in parallel, we construct a regular set checking for the applicability of this sequence in any possible representation of configurations of Π; then we take the union of all these regular sets and take its complement thus obtaining a regular set R. In L(GM)∩Rwe then find at least one representation for every final configuration of computations in Π, but no representation of a non-final configuration. Finally, let gbe a projection with g((i, a)) = λfor every i6=i0as well as g((i0, a)) = λfor a∈VrTand g((i0, a)) = afor a∈T. Due to the closure properties of MAT λ, we obtain Ps (g(L(GM)∩R)) = Ps (Π)∈P sMAT λ. 3.2 Results for Symport/Antiport Systems The following results are well known (e.g., see [20]; for an overview of actual results also see [22]): Theorem 4. P sgOP1(anti20, max, H) = DP saOP1(anti20, max, H) = PsRE. Theorem 5. For every X∈ {asyn, sequ}, PsgOP∗(anti∗, X, H) = PsgOP1(anti20, X, H) = PsMATλand NgOP∗(anti∗, X, H) = NgOP1(anti20, X, H) = NREG . Recently, for minimal parallelism, the following result was obtained, see [7]: Theorem 6. NgOP3(anti2, min, H) = NRE. We shall improve this result by showing that only two membranes are needed: Theorem 7. P sgOP2(anti20, min, H) = PsRE. Proof. We only give a sketch of the proof, because the basic ideas are the same as in the usual proofs showing computational completeness for antiport P systems. Now let M= (n, B, P, p0, ph) be a register machine generating an output vector of dimension k(≤n); then we construct the P system Partial Versus Total Halting in P Systems 11 Π= (V, T, V, µ, p0, ZX, R1, R2,2) , V={p, p0, p00, p000,˜p, ˜p0,˜p00,¯p, ¯p0,¯p00 |p∈B} ∪ {X, Y, Z, Z0}∪{Ai|1≤i≤n}, T={Ai|1≤i≤k}, µ= [1[2]2]1, R1=R1,A ∪R1,S ∪R1,F , R1,A ={(p, out;Arq, in),(p, out;Ars, in)|p: (A(r), q, s)∈P}, R1,S ={(p, out;p0p00, in),(p00 Ar, out;p000, in),(p00 X, out; ¯p, in), (p000X, out; ˜p, in),(¯p, out; ¯p0X, in),(¯p0, out; ¯p00Y, in), (¯p00, out;s, in),(˜p, out; ˜p0X, in),(˜p0, out; ˜p00Y, in), (˜p00, out;q, in)|p: (S(r), q, s)∈P}, R1,F ={(p0Y, out;Z0, in)|p∈Br{ph}} ∪ {(Z0, out),(ZX, out;Z0, in)}, R2=R2,A ∪R2,S ∪R2,F , R2,A ={(Ai, in)|1≤i≤k}, R2,S ={(X, out;p0, in)|p∈Br{ph}} ∪ {(Z, out;XY, in),(Z, in)}, R2,F ={(p0Y, out;ph, in)|p∈Br{ph}} ∪ {(ZX, out;ph, in),(ph, out)}. An ADD instruction p: (A(r), q, s)∈Pis simulated by using one of the rules (p, out;Arq, in), (p, out;Ars, in) assigned to membrane 1; in case ris an output register, the terminal symbol Aris moved into the output region 2 by using (Ar, in) from R2. A SUB instruction p: (S(r), q, s)∈Pis simulated by using the rules from R1,S and R2,S in parallel. The final procedure in Πstarts when the final label phappears; as the number of symbols p0equals the number of symbols Yas they have been introduced when simulating a SUB instruction, we finally eliminate pairs p0Yfrom the system using the rules from R1,F and R2,F until finally only phremains in the skin membrane and the desired output is found in the second membrane region, without any additional symbols remaining there anymore. The general result in Theorem 1 and the special result in Theorem 4 immediately yield the following one: Corollary 1. P sgOP1(anti20, max, h) = DP saOP1(anti20, max, h) = P sRE. With the other derivation modes and partial halting, we only get Parikh sets of matrix languages (regular sets of non-negative integers), which is an immediate consequence of Theorem 3: Corollary 2. For every X∈ {min, asyn, sequ}, PsgOP∗(anti∗, X, h) = P sgOP1(anti20, X, h) = P sMAT λand NgOP∗(anti∗, X, h) = NgOP1(anti20, X, h) = NREG. For symport rules, the following result is known (e.g., see [22]): Theorem 8. P sgOP2(sym2, max, H) = PsaOP2(sym2, max, H) = PsRE. Computational completeness can also be obtained with minimal parallelism and total halting, whereas as a direct consequence of Theorem 3, we only get Parikh sets of matrix languages (regular sets of non-negative integers) with partial halting: 12 A. Alhazov, R. Freund, M. Oswald, S. Verlan Theorem 9. P sgOP2(sym3, min, H) = PsRE. Proof. Let M= (n, B, P, p0, ph) be a register machine generating an output vector of dimension k(≤n); then we construct the P system Π= (V, T, E, µ, p0, w1, w2, R1, R2,2) , V={p, p0, p00, p000,˜p, ˜p0,˜p00 ,˜p000,¯p, ¯p0,¯p00,¯p000 ,ˆp, ˆp0|p∈B} ∪ {Ai|1≤i≤n}, T={Ai|1≤i≤k}, E=Vr{p0 h}∪{p0, p000,˜p00 ,¯p, ¯p0,¯p000,ˆp0|p∈B} µ= [1[2]2]1, w1={p0, p0 h}∪{p0, p000,˜p00 ,¯p, ¯p000 |p∈B}, w2={ˆp0,¯p0|p∈B}, R1=R1,A ∪R1,S ∪R1,F , R1,A ={(pp0, out),(p0Arp00, in),(p00 p000, out),(p000q, in),(p000s, in) |p: (A(r), q, s)∈P, 1≤r≤k} ∪ {(pp0, out),(p0Arq, in),(p0Ars, in) |p: (A(r), q, s)∈P, k < r ≤n}, R1,S ={(pp0, out),(˜p˜p0p0, in),(˜p0˜p00Ar, out), (˜p00 ˜p000, in),(¯pp000 ˜p000, out),(¯pp000q, in), (˜p˜p0¯p0, out),(¯p0¯p00 , in),(¯p¯p00 ¯p000 , out),(¯p¯p000s, in) |p: (S(r), q, s)∈P}, R1,F ={(ˆpiˆp0 i¯p0 i, out)|1≤i≤l} ∪ ˆp0 iˆp0 i+1, in|1≤i < l ∪ {(php0 h, out),(p0 hˆp1, in)}, R2=R1,A ∪R1,S ∪R2,F , R2,A ={(Ai, in)|1≤i≤k}, R2,S ={(˜p¯p, in),(˜p¯p0, out),(¯p0˜p000, in),(¯p0¯p00 , in), (¯p˜p000, out),(¯p¯p00 , out)|p: (S(r), q, s)∈P}, R2,F ={(ˆpi, in),(ˆpi, out),(ˆpiˆp0 i¯p0 i, out)|1≤i≤l}. An ADD instruction p: (A(r), q, s)∈P,k < r ≤n, is simulated by sending out the label of the instruction ptogether with p0which returns with Aras well as the label of the next instruction qor sto be simulated. The simulation of an ADD instruction p: (A(r), q, s)∈P, 1 ≤r≤k, takes two steps more – after sending out p, p0we return with p0and Aras well as with p00 which is sent out together with p000;p000 then returns with the label of the next instruction qor sto be simulated, whereas in the meantime Arhas got the chance to enter membrane 2. In the case of a SUB instruction p: (S(r), q, s)∈P,p0returns with ˜pand ˜p0. Whereas ˜penters membrane 2 together with ¯p, ˜p0gets the chance to take one copy of Arout of region 1 using the rule (˜p0˜p00 Ar, out). Depending on whether this rule had to be applied or not, the simulation proceeds until finally the label of the corresponding instruction to be simulated next is brought in together with p000 or ¯p000 , respectively. We should like to mention that all the symbols from VrEused during the simulation finally have returned to their original locations. When the computation of the register machine stops, the label phappears; in order to clean the elementary membrane region 1 from non-terminal symbols we Partial Versus Total Halting in P Systems 13 have to use the rules from R1,F and R2,F ; the labels from Bare assumed to be ordered in a sequence p1to pl. The symbols ¯p0 iare taken out one after the other using the rules (ˆpiˆp0 i¯p0 i, out); the rules (ˆpi, in) and (ˆpi, out) could be used for an unbounded number of steps, but for obtaining a terminating computation at some moment the rule (ˆpiˆp0 i¯p0 i, out) has to be used twice. The computation halts when all ¯p0 ihave been taken out. Corollary 3. For every X∈ {min, asyn, sequ}, PsgOP∗(sym∗, X, h) = P sMAT λand NgOP∗(sym∗, X, h) = NREG. 3.3 Results for P Systems with Conditional Uniport Rules Using only conditional uniport rules of type uni1,1, we again obtain computational completeness, even with the minimally parallel derivation mode, together with total halting, whereas, as a direct consequence of Theorem 3, with partial halting we only get Parikh sets of matrix languages (regular sets of non-negative integers) with the minimally parallel derivation mode. Theorem 10. P sgOP13 (uni1,1, X, H) = P sRE, for every X∈ {min, max}. Proof. We only give a sketch of the proof showing how register machine instructions can be simulated, using the following membrane structure: [1[2[20]20]2[3[6]6[7[70]70]7[8[80]80]8]3[4]4[5[50[500 ]500 ]50]5]1 Throughout the proof we will use a specific notation for the conditional uniport rules to illustrate the trajectories of the objects, in a more relaxed way also allowing symport rules of weight one (observe that we could use dummy objects as conditions). Now let ibe a membrane and ˆıbe the surrounding membrane (for the skin membrane 1 this is the environment 0) ; then we use the following notations (a, b are arbitrary objects): (i, a,ˆı) represents [i a→a[i, (ˆı, a, i) represents a[i→[i a, (i, a →ˆı, b) represents b[i a→ab [i, (ˆı, a →i, b) represents a[i b→[i ab , (i, a [b]→ˆı) represents [i ab →a[i b, (ˆı, a [b]→i) represents ab [i→b[i a. Moreover, we will use the shortcut notation (A, B;i1, . . . , ik;j1, . . . , jk−1) which corresponds to the following group of rules: 14 A. Alhazov, R. Freund, M. Oswald, S. Verlan 0 1    AAAAAAA A @@@ 2 20 5 @@@ @ 50 500 3    6 @@@ 8 80 7 70 4 Fig. 1. Membrane structure (it, B, jt) (jt, B, j0 t) (j0 t, B, jt) (it, A[B], it+1) (it, B →it+1, A) for all 1 ≤t≤k−1 Informally, this means that the symbols Aand Btravel together from membrane i1 to membrane ikfollowing the path i1, . . . , ik. The rules above permit to implement this behavior in 2ksteps, because if something else happens, then symbol Bwill be trapped between membranes jtand j0 t. Of course, we assume that Bcan never go out from membrane jtand that Bcannot interact with other symbols during its move along the path. The system is constructed as follows: membrane 8 holds the current state, membrane 7 holds values of registers, membranes 4, 5 and 6 hold additional symbols. Membrane 2 and all primed membranes are used to trap symbols. For simulating an ADD instruction, the state symbol from membrane 8 travels with an accompanying symbol (from membrane 6) to membrane 5. The accompanying symbol then brings a second accompanying symbol from the environment and both of them move the new state and a copy of the register object Arto the corresponding membranes. After that, the first accompanying symbol returns to its original location. Partial Versus Total Halting in P Systems 15 The SUB instruction is simulated in an even easier way. The state symbol brings two symbols from membrane 6 to membrane 3. While it travels with one of these symbols to membrane 5, the second one tries to decrement the register. Now depending on the position of this second symbol (membrane 3 if the register is zero, or membrane 1 if the register is not zero) the corresponding new state is chosen. We remark, that finally all involved symbols return to their original locations. Moreover, we always move groups of two symbols and if a rule not conforming to the scenario above is applied, then one of these symbols is trapped. In more detail, for the simulation of an ADD instruction p: (A(r), q, s) the following rules are used: I. (Ip, p; 3,1,5; 7,2) II. (Tp, Ip; 5,1; 50) III. (Ip, Ar; 1,3,7; 2,8) IV. (Xp, q; 1,3,8; 2,7) V. (Xp, s; 1,3,8; 2,7) 1.(8, p, 3) 2.(6, Ip→3, p) 3.(3, Ip,6) 4.(7, Ip,3) 5.(0, Ar→1, Ip) 6.(0, Xp→1, T 00 p) 7.(5, T0 p→1, Tp) 8.(5, q →1, Tp) 9.(5, s →1, Tp) 10.(1, T 0 p,5) 11.(1, Tp[q],5) 12.(1, Tp[s],5) 13.(4, T00 p→1, T0 p) 14.(1, T00 p,4) 15.(1, Tp,2) 16.(1, Xp,2) 17.(2, Tp,20) 18.(2, Xp,20) 19.(20, Tp,2) 20.(20, Xp,2) 21.(8, Xp,80) The simulation usually starts with pin membrane 8, with Ipbeing in membrane 6, and q, s in membrane 5,respectively. Symbol pgoes to membrane 3 and brings there symbol Ipfrom membrane 6. After that they both travel to membrane 5. There symbol Ipis moved together with symbol Tpto membrane 1. After that Ipbrings one Arfrom the environment and they travel together to membrane 7 and continue afterwards to membrane 3 and 6. In the meanwhile, symbol Tpin membrane 1 brings T0 pand qor s(in this order, otherwise the state symbol will be trapped in membrane 2). At the same time when q(or s) is brought in membrane 1, symbol T00 pis brought into membrane 1 by T0 p. After that symbol Tpis sent to membrane 5 and at the same time symbol Xpis brought into membrane 1 by the symbol T00 p. Finally, symbols Xpand q(or s) go together to membrane 8. We remark that the rules 3, 10 or 14 may be used instead of some rules of the chain presented above. But in this case symbol por symbol Tpwill be trapped. We also remark that Xpand qwill be ready to move to membrane 3 after Ipand Arhave arrived there. 22 I.I. Ardelean, M. Ignat, C. Moisescu trilaminate structure, the magnetosome membrane. The discovery of MTB stimulated interest among microbiologists, physicists, engineers, geologists, chemists (Mann et al., 1990; Sch¨uler and Frankel, 1999) and today the subject has become a bona fide field of research in microbiology (Bazylinski and Frankel, 2004). Probably it is the time for MTB to receive more attention from P systems, too. Here we put forward that MTB or isolated magnetosomes are significant for membrane computing for the following reasons: 1. The synthesis of magnetite from iron salts is a complex process involving both plasma and magnetosome membranes (Sch¨uler, 2002, 2004). Furthermore, isolated magnetosomes devoid of their membranes are no longer organized in an oriented chain; thus, the magnetosome membrane seems to be essential for the chain arrangement of magnetosomes both in vivo and in vitro, and this membrane has not been yet the subject of any P systems approach. 2. This process – not yet known in detail – could offer the possibility for P systems to develop quantitative discrete models for synergic biochemical and biophysical processes occurring at those biological membranes. This mathematical description could be further used for: a) to better understand the overall process of magnetosome formation and its regulation, by identification of still unknown functional proteins and/or regulatory components, by the use of different strategies developed within P systems; (i) metabolic P graphs (MPG) seems appropriate to identify new functional and regulatory components in different biological processes (Manca, 2006) not yet exploited with respect to MTB; (ii) as well as the proposed mesoscopic approach which is more tractable than the microscopic chemistry, but it provides a finer and better understanding than the macroscopic chemistry modeled by ordinary differential equations (P´erez- Jim´enez et al., 2006); b) on line control of an in vitro reactor able to mimic the function of both plasma and magnetosome membranes in order to convert soluble nonmagnetic iron salts to magnetic nanocrystals. 3. MTB or isolated magnetosomes can contribute to the connection between P systems and the emerging domain of nanobiotechnology with special emphasis on the following: i) the construction of nanoobjects and their precise deposition/localization: MTB synthesize magnetic nanocrystals which can follow precise movements, orientations, and depositions by the use of either magnetotactic behavior of MTB or by (rather strong) external magnetic fields (see bellow); ii) to offer the opportunity to P systems to develop a software for discontinuous controlling and modelling of microdevices to be constructed (see below) for precise and oriented movement and deposition of MTB and their magnetosomes; Magnetotactic Bacteria and Their Significance for P Systems 23 iii) to monitor the precise and oriented movement and deposition of MTB which transport at their cell surfaces different chemically linked molecules of functional significance, as for example immunoglobulins (see below). 4. Oriented MTB/magnetosomes chains could be used for the construction of magnetic logic gates. There are already experimental reports showing the increasing scientific interest in precise deposition of biotic magnetic crystals for the construction of magnetic logic gates able to execute logical NAND and NOR operations (Haque et al., 2004). These pioneering experimental results are directly related to the emerging filed of quantum dot magnetic computing from which there are expected huge effects on the speed of computation and on a new proposed generation of computers based on magnetism rather than electricity. We put forward that magnetic properties of single domain magnetic nanocrystals produced by MTB could be more appropriate than abiotic magnetic nanocrystals for the construction of magnetic logic gates and for the already proposed generation of computers based on magnetism rather than electricity. The properties of these magnetic computers could be further improved by the use of P system based software; this proposal is sustained by the already contribution from P systems to the field of quantum dot magnetic computing (Leporati et al., 2006; Leporati and Felloni, 2007). 2 Magnetotactic Bacteria The morphology of single celled MTB is diverse (spirilla, vibrioids, cocci, rods to ovoid) and there are reports on multicelled magnetotactic prokaryotes. MTB’s main functional characteristic is magnetotaxis, the orientation along the Earth’s geomagnetic field lines (Blakemore, 1975). Magnetotaxis is determined by the presence inside the cell of particles named magnetosomes (Frenkel and Blackmore, 1980; Frenkel et al., 1997) Magnetosomes were originally defined as intracellular, magnetic singledomain (SD) crystals of a magnetic iron mineral that are enveloped by a trilaminate structure, the magnetosome membrane (MM). In other words, a magnetosome consists of magnetic iron mineral particles (the inorganic phase) enclosed within a membrane (the organic phase). In Figure 1 there is presented an original image of M. gryphiswaldense cell. The organic phase (the magnetosome membrane or the magnetosome vesicle), consists in Magentospirillum strains (M. magnetotacticum or M. gryphiswaldense) of a bilayer of about 3-4 nm containing phospholipids and proteins. In the last few years the study of the proteins found in magnetosome membranes has raised a special interest because it was expected that these proteins would enable the processes of mineral formation of nanocrystals to be regulated by biochemical pathways (Sch¨uler and Frankel, 1999; Bazylinski and Frankel, 2004). The magnetosome particle is characterized by a nearly perfect crystallinity and the size and morphology of magnetic crystals are species specific and uniform 24 I.I. Ardelean, M. Ignat, C. Moisescu Fig. 1. Transmission electron microscope image of an intact cell of Magnetospirilum gryphyswaldense; one can see the chain of magnetosomes as dark bodies inside the bacterial cell (light grey). within a single cell, for example, in M. gryphiswaldense the dimension of magnetosomes is around 45 nm (Sch¨uler, 2004). This uniformity is an advantage of biogenic magnetic nanocrystals of MTB used for different bio(nano)technological application (Sch¨uler and Frankel, 1999; Bazylinski and Frankel, 2004), as compared with biogenic magnetic nanocrystals produced by other types of bacteria or by artificial/abiogenic magnetic nanocrystals obtained by man using different physical/chemical protocols (Matsunaga, 1991; Sch¨uler and Frankel, 1999). Biogenic magnetic nanocrystal can be produced by metabolic activities of dissimilatory iron-reducing bacteria and sulphate-reducing bacteria. This process is known as biologically induced mineralization. However, unlike the mineral particles in the magneto-tactic bacteria, biologically induced mineralization is not controlled by the organism and is characterized by no uniformity in size distributions and non-unique crystal habits. Magnetotactic Bacteria and Their Significance for P Systems 25 We believe that the uniformity of biogenic magnetic nanocrystals of MTB can be further exploited for the construction of magnetic logic gates at nanometre level, with better results than the use of either abiotic magnetic nanocrystals or those produced by dissimilatory iron-reducing bacteria and sulphate-reducing bacteria. It is still an enigma on how MM actually work in the process of controlled mineralization of iron during the process of magnetosome formation, but pioneering work had identified both at genetic and proteomic level the genes and magnetosome membrane proteins involved in magnetite formation. When the precise biological knowledge of the proteins/items involved in the magnetic nanocrystal formation will be achieved, it is expected that P systems could develop a model of this membrane processes, as it already started to carry out for other biological processes occurring at/within membranes: respiratory electron transport (Ardelean and Cavaliere, 2003; Ardelean et al., 2004; Cavaliere and Ardelean, 2006) the function of mechanosensitive channels (Ardelean et al., 2006) and many other processes (Ciobanu et al., 2006). medskip Magnetotaxis. The passive orientation of MTB along the Earth’s geomagnetic field lines is called magnetotaxis (Blakemore, 1975). Magnetotaxis is determined by the presence of magnetosomes. Dead cells containing magnetosomes also align along the geomagnetic field lines (around 0.05 mT), whereas alive MTB with no magnetosomes, do not align. When magnetosomes are arranged in a single chain, as in the Magnetospirillum species, magnetostatic interactions between the single-magnetic domain particles cause the particle magnetic moments to spontaneously move parallel to each other along the chain direction. This results in a permanent magnetic dipole associated with the chain with a natural magnetization approaching the saturation magnetization and is sufficiently large enough to be oriented along the geomagnetic field at an ambient temperature (Frankel and Blakemore, 1980). It is proposed that in natural environments magnetotaxis enables the cells to locate and maintain an optimal position in water columns or in sediments, with respect to their main metabolically needs: molecular oxygen and organic nutrients. It is our hope that carefully deposition of MTB by the use of P systems-based models of magnetotactic behavior of intact cells during chemotaxis, and gently liberation of intact magnetosomes chains (retaining the surrounding membrane of each individual magnetosome particle) could be used for the construction of magnetic logic gates. Magnetomanipulation of MTB. The orientation of MTB along the lines of magnetic field can be used to obtain in the lab surfaces covered by cells aligned with respect to the direction of the imposed magnetic field generated by two magnetic bars. This magnetomanipulation of magnetosome containing cells depends on their magnetotactic movement. In Figure 2 there are presented original images (optical microscope) concerning the experimental orientation of intact MTB on glass by the use of an external magnetic field; for the sake of simplicity the microscope images are accompanied by schematic drawings illustrating more clearly the orientation of MTB cells. 26 I.I. Ardelean, M. Ignat, C. Moisescu Fig. 2. The orientation of MTB along the lines of magnetic field; original optical microscope images (bright field, cells colored by basic fuxine) and schematic drawings: up = horizontal, center = vertical, and bottom = mixed (horizontal–vertical) orientation of MTB. Magnetotactic Bacteria and Their Significance for P Systems 27 Controlled assembly of magnetic nanoparticles into ordered structures was demonstrated by manipulating magnetotactic bacteria in a fluid with microelectromagnets (Lee et al., 2004). The advantage of using magnetotactic bacteria cells is that the cellular bodies enclosing the magnetic chains prevent the magnetic aggregation of the bacteria, making it possible to use the bacteria as a carrier of ordered magnetic nanoparticles. Microelectromagnets, consisting of multiple layers of lithographically patterned conductors, generate versatile magnetic fields on micrometer length scales, allowing sophisticated control of magnetotactic bacteria inside a microfluidic chamber (Lee et al., 2004). A single bacterium was stably trapped and its orientation was controlled; multiple groups of bacteria were assembled in a fluid. After positioning the bacteria, their cellular membranes were removed by cell lysis, leaving a chain and a ring of magnetic nanoparticles on a substrate. Thus, the authors demonstrated that the magnetic nanoparticles grown by the bacteria can be assembled into ordered structures. The new proposed approach, combining biomineralization and micromanipulation, can become a new method for growing and assembling nanoparticles into customized structures. Moreover, though integrated sensory means and new algorithms, the magnetotactic bacteria-based system could adapt or change the direction of motion from new occurring conditions (Lee et al., 2004). It is our claim that a P system-based program could be more appropriate to model and control the direction of motion of these magnetotactic bacteria and to obtain ordered cells with magnetosomes useful for the construction of magnetic logic gates. The following picture suggests the use of a carefully designed (and constructed!) microdevice for true bacterial races! The development of future autonomous bacterial microrobots (Martel, 2006) is another trend in which MTB can be involved. Acting like a compass, this chain of magnetosomes enables the bacteria to orient themselves and swim along the lines of a magnetic field. Hence, the basic control method consists of modifying the swimming paths of the MTB with the generation of local directional magnetic fields using small programmed electrical currents passing through special embedded conductor networks. This new method referred to as controlled bacterial micro-actuation is a serious candidate for its integration in future untethered microrobots operating in an aqueous medium, as originally proposed by the authors (Martel, 2006). The implementation of such bio-carriers with (non magnetic) micro-objects being propelled by a single MTB was also demonstrated. The effect of various diameters MTB-pushed beads on the velocity of this bio-carrier and the retarding effect caused by the proximity of the walls of the microchannels were also investigated. Thus by exploiting the motility of MTB, the electrical energy required to propel such a robot is null and the authors estimate that by pushing the limit of miniaturization or feature sizes to what is possible with actual microfabrication methods, a small current as low as 100 µA could be sufficient to control groups of pre-selected and most responsive MTB from a microcircuit embedded in the microrobot. 28 I.I. Ardelean, M. Ignat, C. Moisescu Fig. 3. Schematic picture of a microdevice for bacterial races (bacteriodrome?). In our opinion such un-tethered microrobots could be used to transport biogenic magnetite produced by other bacterial cells, attached at their surface, and to release these nanocrystals at precise sites. Furthermore the concept of controlled bacterial micro-actuation (Martel, 2006) can be applied to obtain regular arrays of MTB which can be the basis for the construction of magnetic logic gates. We have already designed a magneto-mechanical model of MTB with special emphasis on possible application in the field of nanoactuation (fore more details, see Ignat and Ardelean, 2004; Ignat et al. 2005, 2007). For example, the magnetosome chain microstructure can be moved and controlled with a 3 D system using magnetic levitation that represents an interesting microrobotic element. The nanostructure of MTB suggests a nano- or micromanipulator structure which includes a flexible chain support with flexible joins and with magnetic elements which are small permanent magnets. These micromanipulator systems basically work within small magnetic gaps between the electromagnets (which generate the variable magnetic fields) and the motile chain. In Figure 4 there are presented some proposed structures for either flexible or rigid manipulators. Our proposal to use magnetosomes, biogenic magnetic crystals covered by their biological membrane, as natural materials for the construction of magnetic logic gates and to construct nanoacutators based on either MTB or isolated intact magnetosomes could be helpful for the bottom up construction of a P systems- Magnetotactic Bacteria and Their Significance for P Systems 29 Fig. 4. Microarchitecture of nano or micro-magneto-manipulators. based computer using natural components (biogenic magnetic nanocrystals) and P system-based software. This proposal for the use of natural components for in vitro implementation of P systems and for the construction of a P system-based computer is in the line with the progresses made in the last four decades in incorporating different biological molecules into artificial membranes (Ottowa and Tien, 2002) which opened the way towards an in vitro implementation of P systems (see Ardelean, 2006, for more details). Acknowledgements Thanks are due to CEEX-MATNANTCH PROGRAME for partly supporting the work (Contract 2037/2006) and to both CEEX-MATNANTCH PROGRAME and THE ORGANIZING COMMITTEE for financial support to attend the 5th Brainstorming Week on Membrane Computing, Sevilla, 2007. References 1. I.I. Ardelean (2006): Biological roots and applications of P systems. Further suggestions. In [12], 1–17. 2. I.I. Ardelean, D. Besozzi, M.H. Garzon, G. Mauri, S. Roy (2006): P system models for mechanosensitive channels. In [8], 43–81. 3. I.I. Ardelean, D. Besozzi, C. Manara (2004): Aerobic respirations a bio-logic circuit containing molecular logic gates. In Pre-Proc. of Fifth Workshop on Membrane 30 I.I. Ardelean, M. Ignat, C. Moisescu Computing, WMC5 (G. Mauri, Gh. P˘aun, C. Zandron, eds.), Universita di Milano- Bicocca, June 14-16, 2004, 119–125. 4. I.I. Ardelean, M. Cavaliere (2003): Modelling biological processes by using a probabilistic P system software. Natural Computing, 2 (2003), 173–197. 5. D.A. Bazylinski, R.B. Frankel (2004): Magnetosome formation in prokaryotes. Nature Reviews, 2 (2004), 217–230. 6. R.P. Blakemore (1975): Magnetotactic bacteria. Science, 190 (1975), 377–379. 7. M. Cavaliere, I. Ardelean (2006): Modelling respiration in bacteria and respiration/photosynthesis interaction in cyanobacteria. In [8], 129–159. 8. G. Ciobanu, M. P´erez-Jim´enez, Gh. P˘aun, eds. (2006): Applications of Membrane Computing. Springer-Verlag, Berlin. 9. R.B. Frankel, D.A. Bazylinski, M.S. Johnson, B.L. Taylor (1997): Magneto-aerotaxis in marine coccoid bacteria. Biophys. J., 73 (1997), 994–1000. 10. R.B. Frankel, R.P. Blakemore (1980): Navigational compass in magnetic bacteria. J. Magnet Magnet Matter, 15-18 (1980), 1562–1564. 11. S.A. Haque, M. Yamamoto, R. Nakatani, Y. Endo (2004): Magnetic logic gate for binary computing, Science and Technology of Advanced Materials, 5, 1-2 (2004), 79– 82. 12. H.J. Hoogeboom, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds. (2006): Proc. Workshop on Membrane Computing, WMC7, Leiden, The Netherlands, LNCS 4361, Springer- Verlag, Berlin. 13. M. Ignat, I.I. Ardelean (2004): Distinct nanobiological structure: magnetotactic bacteria. Models and applications in the electromechanical nanoactuation. Romanian Journal of Physics, 9-10 (2004), 835–847. 14. M. Ignat, I.I. Ardelean, J. Pintea, Cr. Cojocaru (2005): Experimental aspects and magnetic characterization of Magnetospirillum gryphiswaldense.Proceedings of The 4th National Conference on New Research Trends in Material Science, ARM 4, September 2005, vol. I, 433–441. 15. M. Ignat, G. Z˘arnescu, S. Soldan, I.I. Ardelean, C. Moisescu (2007): Magnetomechanic model of the magnetotactic bacteria. Applications in the microactuator field. Journal of Optoelectronics and Advanced Materials, 9, 4 (2007), 1169–1172. 16. H. Lee, A.M. Purdon, V. Chu, R.M. Westervelt (2004): Controlled assembly of magnetic nanoparticles from magnetotactic bacteria using microelectromagnets arrays. Nano Lett., 4, 5 (2004), 995–998. 17. A. Leporati, S. Felloni (2007): Three “quantum” algorithms to solve 3-SAT. Theoretical Computer Science, 372, 2-3 (2007), 196–217. 18. A. Leporati, G. Mauri, C. Zandron (2005): Quantum sequential P systems with unit rules and energy assigned to membranes. In Membrane Computing: 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005 (R. Freund, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.), LNCS 3850, Springer-Verlag, Berlin, 310–325. 19. V. Manca (2006): MP Systems approaches to biochemical dynamics: biological rhytms and oscillations. In [12], 86–100. 20. S. Mann, N.H.C. Sparks, R.G. Board (1990): Magnetotactic bacteria: microbiology, biomineralization, palaeomagnetism and biotechnology. Adv. Microbiol. Physiol, 31 (1990), 125–181. 21. S. Martel (2006): Controlled bacterial micro-actuation. In Proc. of the Int. Conf. on Microtechnologies in Medicine and Biology, Okinawa, Japan, May 9-12, 2006. 22. T. Matsunaga (1991): Applications of bacterial magnets. Trends Biotechnology, 9 (1991), 91–95. Magnetotactic Bacteria and Their Significance for P Systems 31 23. A. Ottova, H.T. Tien (2002): The 40th anniversary of bilayer lipid membrane research. Bioelectrochemistry, 56 (2002), 171–173. 24. Gh. P˘aun (2000): Computing with membranes. Journal of Computer and Systems Sciences, 61 (2000), 108–143. 25. Gh. P˘aun (2001): From cells to computers. Computing with membrane (P systems). BioSystems, 59 (2001), 139–158. 26. Gh. P˘aun (2002): Membrane Computing. An Introduction. Springer-Verlag, Berlin. 27. M.J. P´erez-Jim´enez, F.J. Romero-Campero (2006): P systems, a new computational modelling tool for Systems Biology. Transactions on Computational Systems Biology, VI. Lecture Notes in Bioinformatics, 4220, 176–197. 28. D. Sch¨uler (2002): The biomineralization of magnetosomes in Magnetospirillum gryphiswaldense. Int. Microbiol., 5 (2002), 209–214. 29. D. Sch¨uler (2004): Molecular analysis of a subcellular compartment: the magnetosome membrane in Magnetospirillum gryphiswaldense. Arch. Microbiol., 181 (2004), 1–7. 30. D. Sch¨uler, R.B. Frankel (1999): Bacterial magnetosomes: microbiology, biomineralization and biotechnological applications. Appl. Microbiol. Biotechnol., 52 (1999), 464–473. 38 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan rule has the form u→(u1, t1)(u2, t2). . . (uq, tq) with u∈V∗, for all 1 ≤r≤q, ur∈V∗and tr∈ {here, out, inj}. If such a rule is associated to a region i, then multiset ucan be replaced by multisets u1, u2, . . . , uqand each multiset uris moved across the membranes depending on the target tr:urremains inside membrane i when tr=here,uris moved outside membrane iwhen tr=out,uris moved into region jwhen tr=injwith ja membrane directly contained into region i. A basic P system can be represented as an NC which has as many cells as the membranes in the P system and which contains, for every region iof the P systems, for every evolution rule u→(u1, t1)(u2, t2). . . (uq, tq) associated to region i, an interaction rule (u, i)→(u1, j1)(u2, j2). . . (uq, jq), with distinct j1, j2, . . . , jq, such that, for all 1 ≤r≤q, if tr=here, then jr=i; if tr=inj, then jr=j; if tr=out, then jris equal to the index of the directly upper region. Example 2. P systems with boundary rules [4] extend basic P systems with rules which allow direct interactions between the inside and the outside of a region. In their most general form (e.g., see [5]), boundary rules are of the form u[iv→u0[iv0 with ithe index of a membrane in the system and u, v, u0, v0∈V∗, for Vthe alphabet of the system. These rules can be represented in NC’s as interactions of the form (u, j)(v, i)→ (u0, j)(v0, i) with jthe membrane which directly contains membrane i. In this way, we can for instance capture the features of symport/antiport rules [18]: •an antiport rule (x, in;y, out) associated to membrane iis no more than an interaction rule (x, j)(y, i)→(y, j)(x, i) with jthe membrane which directly contains membrane i; •a symport rule (x, out) associated to membrane iis no more than an interaction rule (x, i)→(x, j) with jthe membrane which directly contains membrane i; •a symport rule (x, in) associated to membrane iis no more than an interaction rule (x, j)→(x, i) with jthe membrane which directly contains membrane i. Example 3. An evolution-communication model of tissue P systems is proposed in [3] that is based on graphs of cells where each cell contains a multiset of objects and a finite set of rules of the forms x→y(transformation rules) and (x;y, in) (communication rules) with x, y two multisets over a given alphabet. A transformation rule x→yassociated to a cell ispecifies that a multiset xplaced inside cell ican be replaced by a multiset ywhich remains inside cell i. A communication rule (x;y, in) associated to a cell iinstead specifies that, in presence of a multiset x, a multiset ycan be moved from a neighboring cell jnon-deterministically chosen into cell i. Such a tissue P system can be represented as an NC with the same number of cells which contains an interaction rule (x, i)→(y, i), for every transformation rule x→yassociated to cell iof the tissue P system, and a set of interaction rules {(x, i)(y, j)→(xy, j)| {i, j}is an edge of the graph underlying the tissue P system}, for every communication rule (x;y, in) in the tissue P system associated to cell i. Networks of Cells and Petri Nets 39 We now pass to precisely define the execution semantics of networks of cells by identifying different strategies for the application of the rules. To this aim, we first give the following definitions. Definition 2 (configuration). Let Π= (V, w1, w2, . . . , wn, R)be a network of cells. A configuration of Πis any tuple (w0 1, . . . , w0 n)with wi∈O∗, for all 1≤i≤ m. The initial configuration of Πis the tuple (w1, . . . , wn). Definition 3 (multiset of applicable rules). Let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n)be a configuration of Π. A multiset of applicable rules (w.r.t. Πand C)is any function ΓC:R→Nsuch that, for all 1≤i≤n,(Fr∈R(lhsi(r))ΓC(r))vw0 i. Free parallelism Free parallelism means that, in each step, any multiset of applicable rules can be used to make an NC transit from a configuration to another one by applying all the selected rules in parallel at the same time. In membrane computing literature, this semantics is also called asynchronous behavior (e.g., see [9]). Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Πtransits in one step from configuration Cto configuration C0in a freely-parallel way, and we write C⇒free C0, if there is a multiset of applicable rules ΓCsuch that, for all 1 ≤i≤n,w00 i= (w0 i\(Fr∈R(lhsi(r))ΓC(r))) ∪(Fr∈R(rhsi(r))ΓC(r)). Thus, in a freely-parallel step, an arbitrary multiset of applicable rules is selected and these rules are applied in parallel by consuming all the multisets on their left-hand sides and producing all the multisets on their right-hand sides in the respective places. Sequential execution Sequential execution means that, in each step, only one rule is applied to make an NC transit from a configuration to another one. Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Πtransits in one step from configuration Cto configuration C0in a sequential way, and we write C⇒seq C0, if C⇒free C0for some multiset of applicable rules ΓCwith |ΓC|= 1. Thus, a sequential step is a freely-parallel step where the number of rules used is equal to 1. Maximal parallelism Maximal parallelism means that, in each step, any maximal multiset of applicable rules can be used to make an NC transit from a configuration to another one by 40 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan applying all the selected rules in parallel at the same time; a maximal multiset of applicable rules is any multiset of applicable rules to which no other rules can be added so to obtain another multiset of applicable rules. Maximal parallelism is the type of behavior which was associated to membrane systems in their original definition [17], and it is the semantics most commonly adopted in the area of membrane computing (e.g., see [1], [18]). Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Πtransits in one step from configuration Cto configuration C0in a maximallyparallel way, and we write C⇒max C0, if C⇒free C0for some multiset of applicable rules ΓCsuch that, for all r∈R, there is 1 ≤i≤nwith lhs(r)i6=λand lhsi(r)6v (w0 i\(Fr∈R(lhsi(r))ΓC(r))). Thus, a maximally-parallel step is a freely-parallel step where rules are applied in parallel in an exhaustive way: once the multisets on the left-hand side of these rules are consumed, no other rule has to be applicable to the objects left inside the cells. Locally-maximal parallelism Locally-maximal parallelism, which was introduced in [13], specifies that, in each step, if a cell is involved in the application of (at least) one rule, then a maximal number of objects are consumed in this cell by applying in parallel as many rules that involve this cell as possible. Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Πtransits in one step from configuration Cto configuration C0in a locallymaximally-parallel way, and we write C⇒lmax C0, if C⇒free C0for some multiset of applicable rules ΓCsuch that, for all 1 ≤i≤n, if there is r0∈Rwith ΣC(r0)>0 and lhsi(r0)6=λ, then, for all r∈Rwith lhs(r)i6=λ, there is 1 ≤j≤nwith lhs(r)j6=λand lhsj(r)6v (w0 j\(Fr∈R(lhsj(r))ΓC(r))). Thus, a locally-maximally parallel step is a freely-parallel step where if a cell is involved in the application of one rule, then a maximal number of rules involving this cell is applied in parallel at the same time. In other words, in a locallymaximally parallel step, every cell that gets involved tries to participate in as many interactions as possible depending on the objects currently available inside the cell and on the presence of other cells competing for the same objects. Minimal parallelism Minimal parallelism, which was introduced in [6], means that, in each step, every cell that can participate in at least one interaction must get involved in the application of at least one rule. Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Networks of Cells and Petri Nets 41 Πtransits in one step from configuration Cto configuration C0in a minimallyparallel way, and we write C⇒min C0, if C⇒free C0for some multiset of applicable rules ΓCsuch that, for all 1 ≤i≤n, if there is no r0∈Rwith ΓC(r0)>0 and lhsi(r0)6=λ, then, for all r∈Rwith lhs(r)i6=λ, there is 1 ≤j≤nwith lhs(r)j6=λand lhsj(r)6v (w0 j\(Fr∈R(lhsj(r))ΓC(r))). Thus, a minimally-parallel step is a freely-parallel step where a maximal number of cells, which are selected depending on the current distribution of objects inside the cells, evolve in parallel at the same time; each one of the selected cells has to participate in at least one interaction, and no other rule has to be applicable in parallel at the same time that involve any cell different from the selected ones. Example 4. Let UNO = (V, aa, aa, bb, c, R) be an NC where Rcontains the following interaction rules: 1. (a, 1) →(a, 1)(a, 2), 2. (a, 1) →(a, 1)(b, 3), 3. (c, 4)(a, 2)(b, 3) →(b, 2)(a, 3), 4. (b, 2) →(b, 2)(c, 4), 5. (c, 4)(b, 3) →(cc, 4)(b, 3), 6. (c, 4)(b, 2) →(bb, 3), 7. (c, 4)(a, 1) →(a, 4)(a, 2)(a, 3). This NC has rules with input radius at most 2 and cooperation degree 1. The initial configuration is given by the tuple C0= (aa, aa, bb, c). To the initial configuration, we can apply rule 1 with multiplicity at most 2, rule 2 with multiplicity at most 2, rule 3 with multiplicity at most 1, rule 5 with multiplicity at most 1, and rule 7 with multiplicity at most 1. However, with respect to C0, it is not possible to apply all these rules in parallel (e.g., only one rule between rules 3, 5 and 7 can be applied because cell 4 contains only one object c). Thus, in the case of free-parallelism, for any configuration C0obtained by applying any combination of the aforementioned rules that is a multiset of applicable rules, we have C0⇒free C0. For instance, if rule 1 is applied with multiplicity 2 and rule 3 is applied with multiplicity 1, we have C0⇒(aa, aaab, ab, λ). In the case of sequential execution, only one of the aforementioned rules is going to be applied with multiplicity 1 to the initial configuration. This gives us five possible transitions: C0⇒seq (aa, aaa, bb, c) when rule 1 is applied, C0⇒seq (aa, aa, bbb, c) when rule 2 is applied, C0⇒seq (aa, ab, ab, λ) when rule 3 is applied, C0⇒seq (aa, aa, bb, cc) when rule 5 is applied and C0⇒seq (a, aaa, abb, a) when rule 7 is applied. If maximal parallelism is adopted, then a maximal number of the aforementioned rules is applied to the initial configuration C0. Specifically, we have the following possibilities: rule 1 (rule 2) applied with multiplicity 2 in parallel with another rule chosen between rules 3 and 5; rule 1 applied in parallel with rule 2 (both with multiplicity 1) together with another rule chosen between rules 3 and 42 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan 5; rule 1 (rule 2) applied with multiplicity 1 in parallel with rule 7. For instance, if we choose this latter combination, we have C0⇒max (a, aaaa, abb, a). In the case of locally-maximal parallelism, we have to make sure that if a cell evolves by means of at least one rule, then all other rules affecting that same cell that can be applied in parallel are effectively applied within the same step of execution. Specifically, for the initial configuration C0, this means that whenever rule 1, or 2 (rule 7) is used, then another rule chosen between rules 1, 2 and 7 (rules 1 and 2) is always applied in parallel in the same step. On the other hand, we have C0⇒lmax (aa, ab, ab, λ) by just applying rule 3 because there are no other rules involving cell 2, or 3 or 4 that can be applied in parallel at the same time. Also, we have C0⇒seq (aa, aa, bb, cc) by just applying rule 5 because there are no other rules involving cell 3 or 4 that can be applied in parallel at the same time. In the case of minimal parallelism, a maximal number of cells evolve in parallel at the same time with each one of the selected cells participating in at least one interaction. Specifically, for the initial configuration C0, this means that rule 3 (rule 5) is always used in parallel with at least an application of rule 1 or 2. However, with respect to C0, we have C0⇒min (a, aaa, abb, aa) by just applying rule 7 because there are no rules involving cells 2 or 3 which can be applied in parallel at the same time. Remark 1. Locally-maximal parallelism was introduced in [13, 12] only for the basic model of P systems where rules are precisely assigned to regions delimited by membranes and the left-hand side of every rule involves only objects inside the region which the rule is assigned to. Therefore, locally-maximal parallelism is defined in [13, 12] by simply stating that, in each step, a certain number of membranes is selected and a maximal number of rules is applied inside each one of these membranes. In the case of NC’s, interaction rules may involve objects placed inside different cells, hence locally-maximal parallelism is defined with respect to a certain group of cells: in each step, a multiset of applicable rules can be used only if it is maximal with respect to the cells which appear on the left-hand side of the rules in it. However, if the rules of NC’s are restricted to have input radius equal to 1, then the present notion of locally-maximal parallelism is consistent with the semantics given in [13, 12] for the basic model of P systems. Remark 2. The minimally-parallel semantics for NC’s is not defined in terms of number of rules which are applied inside the cells, as in [6], but it is defined with respect to the number of cells which can evolve in parallel at the same time. Specifically, in each minimally-parallel step, a multiset of applicable rules can be used only if there are no cells which do not appear on the left-hand side of any rule in it and which some rules can be applied to; the multiset of applicable rules has not to be maximal neither locally nor globally though. Minimal parallelism was instead defined in [6] for P systems with symport/antiport where every membrane has its own set of rules, hence, in each step, for each one of these sets of rules, if there is a rule which is applicable, then at least one rule from that set is going to be applied irrespective of the fact that an antiport rule involves two distinct Networks of Cells and Petri Nets 43 regions at the same time. Therefore, although symport/antiport can be expressed as interaction rules of NC’s, the notion of minimal parallelism proposed in [6] for symport/antiport differs from the one considered here because interaction rules of NC’s are not assigned a priori to any cell. However, if rules of NC’s are restricted to have input radius equal to 1, then our minimally-parallel semantics for NC’s is consistent with the idea from [6], that is, in each step, if at least one rule may be used inside a region, then at least one rule is applied inside that region. Remark 3. From a computational point of view (in the usual sense of membrane computing), if we consider NC’s operating according to maximal parallelism, then it is obvious that they are computationally complete and that the hierarchy on the number of cells collapses at level 1. Moreover, the universality results obtained for catalytic P systems and evolution-communication P systems (e.g., see [14], [3], [10]) can be directly transferred to NC’s: NC’s with rules of input radius at most 2 are computationally complete and, for such systems, the hierarchy on the number of cells collapses at level 2. More precisely, for NC’s corresponding to catalytic P systems, we have universality for input radius at most 1 and cooperation degree at most 2 [10], whereas, for evolution-communication P systems, we have universality for input radius at most 2 and cooperation degree at most 1 when antiport rules are used, or for input radius at most 1 and cooperation degree at most 2 when symport rules are used [14]. On the other hand, the computational power of NC’s operating in a sequential manner, in a freely-parallel manner, in a locally-maximal parallel manner, or in a minimally parallel manner requires further investigations. 4 PT Nets with Localities We introduce the class of Petri nets called place-transition nets with localities in the form reported in [12]. Definition 4 (PTL-net). APT-net with localities (a PTL-net, for short) is a construct: N= (P, T, W, M0, L), where 1. Pis a finite set of symbols whose elements are called places, 2. Tis a finite set of symbols whose elements are called transitions, 3. W: (P×T)∪(T×P)→Nis the weight function, 4. M0∈P∗is a multiset over Pcalled the initial marking, 5. L:T→Nis a locality mapping; and such that P∩T=∅. PTL-nets are usually represented by diagrams where places are drawn as circles, transitions are drawn as squares, and a directed arc (x, y) is added between xand yif W(x, y)≥1. Moreover, transitions are annotated with their localities and the 44 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan arcs are annotated with their weights if these are 2 or more. Localities are used to partition the set of transitions into subsets of transitions which logically belongs to distinct locations. Given a PTL-net N, the pre- and post-multiset of a transition tare respectively the multiset preN(t) and the multiset postN(t) such that, for all p∈P,|p|preN(t)= W(p, t) and |p|postN(t)=W(t, p). A configuration of N, which is called a marking, is any multiset over P; in particular, for every p∈P,|p|Mrepresents the number of tokens present inside place p. Then, we recall from [12] the notion of an execution mode for a PTL-net by giving the following definitions. Definition 5 (free-enabled). Let N= (P, T, W, M0, L)be a PTL-net and let M be a marking of N. A multiset of transitions U∈T∗is free-enabled at marking Mif (Ft∈T(preN(t))|t|U)vM. Definition 6 (seq-enabled). Let N= (P, T, W, M0, L)be a PTL-net and let M be a marking of N. A multiset of transitions U∈T∗is seq-enabled at marking M if Uis free-enabled at marking Mand |U|= 1. Definition 7 (max-enabled). Let N= (P, T, W, M0, L)be a PTL-net and let Mbe a marking of N. A multiset of transitions U∈T∗is max-enabled at marking Mif Uis free-enabled at marking Mand, for all t∈T,preN(t)6v (M\(Ft∈T(preN(t))|t|U)). Definition 8 (lmax-enabled). Let N= (P, T, W, M0, L)be a PTL-net and let M be a marking of N. A multiset of transitions U∈T∗is lmax-enabled at marking Mif Uis free-enabled at marking Mand, for all l∈L(T), if there is t∈T with L(t) = land |U|t>0, then, for all t0∈Twith L(t0) = l,preN(t0)6v (M\(Ft∈T(preN(t))|t|U)). Definition 9 (min-enabled). Let N= (P, T, W, M0, L)be a PTL-net and let M be a marking of N. A multiset of transitions U∈T∗is min-enabled at marking Mif Uis free-enabled at marking Mand, for all l∈L(T), if there is no t∈T with L(t) = land |U|t>0, then, for all t0∈Twith L(t0) = l,preN(t0)6v (M\(Ft∈T(preN(t))|t|U)). Definition 10 (m-execution). Let N= (P, T, W, M0, L)be a PTL-net and let m∈ {free, seq, max, lmax, min}. The m-execution of Nis the relationship ;m⊆P∗×P∗such that, for all M, M0∈P∗,M;mM0iff, M0= (M\(Ft∈T(preN(t))|t|U)) for some U∈T∗which is m-enabled at marking M. Thus, an m-execution of a PTL-net Nrepresents a transition step which makes possible to derive a new marking from a given one by firing a certain number of transitions in parallel at the same time. The firing of each transition results in the consumption of its pre-multiset of places from the given marking and in the production of its post-multiset of places in the new marking; the number of transitions that can fire in parallel within a transition step depends on the execution Networks of Cells and Petri Nets 45 mode m ∈ {free, seq, max, lmax, min}and it has to be consistent with the current availability of tokens inside each place (i.e., for each place, the number of its tokens consumed cannot be greater than its multiplicity in the current marking). Specifically, the aforementioned execution modes identify the following behaviors for a PTL-net: •free-execution: in each transition step, an arbitrary number of transitions fire by providing that these constitute a free-enabled multiset of transitions (i.e., the union of their pre-multisets has to be contained in the current marking). •seq-execution: in each transition step, only one transition fires that is chosen amongst those whose pre-multiset of place is contained in the current marking (i.e., in order to fire, a transition has to be enabled at the current marking); •max-execution: in each transition step, a maximal number of transitions fire by providing that these constitute a free-enabled multiset of transitions which no other transition can be added to in order to obtain another free-enabled multiset of transitions (i.e., the selected transitions has to consume a maximal number of places so that no other transition can fire in parallel at the same time); •lmax-execution: in each transition step, an arbitrary set of localities is selected and, for each one of these localities, a maximal number of transitions fire (i.e., for each selected locality, a maximal number of places is consumed so that no other transition belonging to the same locality can fire in parallel at the same time); •min-execution: in each transition step, for each locality such that there is at least one enabled transition associated to that locality, at least one transition fire (i.e., the selected multiset of transitions has to involve a maximal set of localities, although the number of firing transition belonging to the same locality has not necessarily to be maximal with respect to the current marking). Notice that seq-execution is called min-execution in [13, 12], whereas the present notion of min-execution is introduced as a counterpart of the minimally-parallel semantics previously used in the area of membrane computing [6]; this latter notion of minimal parallelism is in fact not considered in [13, 12]. 5 Network of Cells versus PTL-nets We start by extending to the class of network of cells the basic construction devised in [7, 12, 13] to transform membrane systems into “equivalent” PTL-nets. Definition 11. Let Π= (V, w1, w2, . . . , wn, R)be a network of cells. 1. The extended alphabet of Π, denoted by EΠ, is the set {(a, i)|a∈V, 1≤i≤ n}. 2. For all 1≤i≤n, the ilabeling of Πis the mapping hi,Π :V∗→E∗ Πsuch that, for all a∈V,hi,Π (a) = (a, i)and, for all u, v ∈V∗,hi,Π (uv) = hi,Π (u)h(v). 46 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan 3. For all r∈Rof the form (u1, i1). . . (uk, ik)→(v1, j1). . . (vh, jh), the cell-labeled version of r, denoted by CL(r), is the (multiset rewriting) rule hi1,Π (u1). . . hik,Π (uk)→hj1,Π (v1). . . hjh,Π (vh). Thus, for all 1 ≤i≤n, the ilabeling assigns to every object of a given multiset the label i; the cell-labeled version of an interaction rule is a multiset rewriting rules where the localization of the multisets inside the cells is given by the labels assigned to the objects. This idea of assigning a label to the objects in order to represent their localization inside the cells is central to the following construction which shows how to define a corresponding PTL-net for every network of cells. Definition 12 (corresponding PTL-net). Let Π= (V, w1, w2, . . . , wn, R) be a network of cells where rules in Rare labeled in a one-to-one manner with values in {1,2, . . . , |R|}. The PTL-net corresponding to Πis N(Π) = (EΠ,{1,2, . . . , |R|}, W, M0, L), where: for all p∈EΠ,t∈ {1,2, . . . , |R|}, W(p, t) = miff tis the label of a rule r∈Rwith m=|lhs(CL(r))|p, and W(t, p) = miff tis the label of a rule r∈Rwith m=|rhs(CL(r))|p; M0=h1,Π (w1)h2,Π (w2). . . hn,Π (wn); for all t∈ {1,2, . . . , |R|},L(t) = 0. Thus, an NC Πis transformed into a PTL-net which contains a place for each cell in Πand for each object possibly present inside this cell, and a transition for each rule in Π. More precisely, in the corresponding PTL-net, occurrences of the same symbol inside different cells are represented as occurrences of tokens inside different places, each one of them identifying the presence of that symbol inside a certain cell. The consumption of objects from certain places and the production of new objects in other cells are then reflected in the movement of tokens between the respective places; pre- and post-multisets of the transitions in fact correspond to left-hand sides and right-hand sides of the rules in Πrespectively. As an example, we show in Figure 1 the PTL-net corresponding to the NC UNO of Example 4. Next, similar to what was done in [13, 12], we introduce the notion of equivalence between the behavior of an NC and that of its corresponding PTL-net. Definition 13 (m-equivalence). Let Π= (V, w1, w2, . . . , wn, R)be a network of cells and let N(Π)be its corresponding PTL-net. For m∈ {free, seq, max, lmax, min}, we say that Πis m-equivalent to N(Π), and we write Π≡mN(Π), if, for every two configurations C= (w0 1, . . . , w0 n),C0= (w00 1, . . . , w00 n)of Π,C⇒mC0iff h1,Π (w0 1). . . hi,n(w0 n);mh1,Π (w00 1). . . hi,n(w00 n). Thus, it is easy to see that the following proposition holds. Proposition 5.1 For any network of cells Π, for m∈ {free, seq, max}, we have that Π≡mN(Π). On the other hand, since all the transitions of the corresponding PTL-net are assigned to the same locality, we have that, for some network of cells Π,Π6≡lmax N(Π) and Π6≡min N(Π). However, we can think of choosing a different locality Networks of Cells and Petri Nets 47 Fig. 1. PTL-net N(UNO) with its initial marking. mapping for the construction of Definition 12 in order to establish the equivalence between the locally-maximal (or minimally-parallel) semantics of networks of cells and the locally-maximal (or minimally-parallel) execution of the corresponding PTL-net. To this aim, given an NC Π= (V, w1, w2, . . . , wn, R), and a function F:{1, . . . , |R|} → N, it is useful to consider the PTL-net N(Π, F) which is constructed as the one of Definition 12 except for the locality mapping which is replaced by F. Thus, we can ask whether, for any NC Π= (V, w1, w2, . . . , wn, R), there exists a F:{1, . . . , |R|} → Nsuch that Π≡lmax N(Π, F) (or Π≡min N(Π, F)), or not. Proposition 5.2 There exists a network of cells Πwith 3rules such that, for all F:{1,2,3} → N, we have that Π6≡lmax N(Π, F ). Proof. Let DUE = ({a, b}, aa, bb, R) be an NC where Rcontains: rule (a, 1) → (aa, 1) labeled by 1, rule (a, 1)(b, 2) →(a, 2)(b, 1) labeled by 2, and rule (b, 2) → (bb, 2) labeled by 3. Then, let us suppose that DUE ≡lmax N(DUE, F) for some F:{1,2,3} → N. By Definition 12, PTL-net N(DUE, F) is the PTL-net (P, T, W, M0, L) with P={(a, 1),(a, 2),(b, 1),(b, 2)},T={1,2,3},W((a, 1),1) = 1, W(1,(a, 1)) = 2, 54 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan NC Representation As pointed out in Section 5, it is possible to find different NC’s corresponding to the PTL-net of Figure 3. Here, in order to model the aforementioned producer/consumer system, we consider an NC PC with 3 cells. Cell 1 represents the producer, cell 2 represents the consumer, whereas cell 3 represents the buffer. Cell 1 stores an object which specifies the states of the producer; this can be either A(“ready to produce”) or B(“ready to deliver”). Similarly, cell 2 stores an object which specifies the state of the consumer; this can be either G(“ready to remove”) or H(“ready to consume”). Cell 3 instead stores an object representing the state of the buffer, either F(“filled”) or E(“empty”). The initial configuration is the tuple (A, G, E). The desired behavior is then implemented by considering the following rules: 1. (A, 1) →(B, 1), 2. (B, 1)(E, 2) →(A, 1)(F, 3), 3. (G, 2)(F, 3) →(H, 2)(E, 3), 4. (H, 2) →(G, 2). Yet again, we have that: •the application of the rules is sequential and freely-parallel; •the maximally-parallelism is deterministic; •irrespectively of the semantics, in each step, at least one rule is always applicable; •irrespectively of the semantics, the consumer can consume only after having received an item from the buffer; •irrespectively of the semantics, after having produced an item, the producer has to deliver it into the buffer before returning to producer; the delivering can take place only when the buffer has been emptied. Also, the PT-net N(PC) is the same as the PTL-net of Figure 3 except for the naming of places and transitions (i.e., they define two isomorphic graphs). In fact, rule 1 corresponds to transition pin the PT-net of Figure 3, rule 2 corresponds to transition din the PT-net of Figure 3, rule 3 corresponds to transition rin the PT-net of Figure 3, and rule 4 corresponds to transition cin the PT-net of Figure 3. Moreover, for F:{1,2,3,4} → Nsuch that F(1) = F(2), F(3) = F(4) and F(1) 6=F(3), we have that PC ≡lmax N(P C, F) and PC ≡min N(P C, F). The vice versa is also true: for the PTL-net of Figure 3, if transitions pand dare assigned to a certain locality (i.e., the producer) and transition rand c to another one (i.e., the consumer), then, for m ∈ {free, seq, max, lmax, min}, PTL-net of Figure 3 is m-equivalent to PC. Therefore, for this version of the producer/consumer system, there is a sort of direct transcription of the PTL-net model into an NC model whose rules are able to represent exactly the same type of interactions between a producer and a consumer. Networks of Cells and Petri Nets 55 Remark 4. For the present version of producer/consumer, the fundamental properties are: there is always a transition enabled (liveness), the producer always alternates between “ready to consume” and “ready to deliver”, and the consumer always alternates between “ready to remove” and “ready to consume”. These properties are formally proved in [20] for the PTL-net of Figure 3 and these results can be directly transferred to our NC model; at some extent, this gives a flavor of the sort of properties which could be proved for NC’s (or any other membrane systems) by using techniques developed in the area of Petri nets. Next, we describe an evolution-communication model of the producer/consumer systems that is not a direct translation of the PTL-net solution from [20] but is inspired by the idea of P systems as systems where transformations involve only objects inside one specific cell and communication is responsible for moving objects from one cell to the other. In other words, we consider an NC with interaction rules of input radius 1 which does not rely on the simultaneous synchronization of two different cells. Similarly to what was done before, we consider an NC PC1 with 3 cells: cell 1, the producer, cell 2, the consumer, and cell 3, the buffer. The initial configuration of PC1 is the tuple (A, G, E). Cell 1 always moves from state A(“ready to produce”) to B(“ready to deliver”) by replacing in its inside object Awith object B. In state B, after having received an object Efrom cell 3 (i.e., after having been notified that the buffer is empty), cell 3 produce in its inside an object Aand object F; object Fis then sent to cell 3 to fill the buffer. In state G(“ready to remove”), cell 2 always waits to receive an object Ffrom cell 3 in order produce in its inside an object H (representing state “ready to consume”) and an object E; object Eis then sent to cell 3 to notify that the buffer is now empty. This behavior is implemented by means of the following rules: 1. (A, 1) →(B, 1), 2. (E, 3) →(E, 1), 3. (BE, 2) →(AF, 1), 4. (F, 1) →(F, 3), 5. (F, 3) →(F, 2), 6. (GF, 2) →(HE, 2), 7. (H, 2) →(G, 2), 8. (E, 2) →(E, 3). Thus, all these rule have input radius equal to 1 and interactions between cell 1 (cell 2) are achieved through an effective exchange of objects. However, irrespectively of the semantics adopted, the aforementioned fundamental properties can still be observed: at any time, at least one rule is applicable, the producer always alternates between “ready to consume” and “ready to deliver”, and the consumer always alternates between “ready to remove” and “ready to consume”. Moreover, the producer can deliver only when the buffer is empty, and the consumer can 56 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan remove only when the buffer is filled. Also, notice that PC1 is somehow “more concurrent” than PC: there is always some communication which can be executed in parallel with the internal change of state. Nevertheless, maximal parallelism still leads to a deterministic behavior for PC1 and the movement of objects Eand F does not affect the behavior of producer and consumer. PTL-net N(PC1) is given in Figure 4. Fig. 4. PTL-net N(P C1) with its initial marking. Remark 5. The solution based on the NC P C uses rules of input radius at most 2 and cooperation degree at most 1, whereas the solution based on the PC1 uses rules of input radius at most 1 and cooperation degree at most 2. In some sense, this shows a trade-off between the cooperation at level of cells and the cooperation at the level of objects. Remark 6. If we do not consider the names of places and transitions, the PTL-net of Figure 4 is the same as the PTL-net of Figure 3 excepts for the presence of some “unary” transitions which correspond to the movement of objects Eand F between cell 1, cell 2 and cell 3. Indeed, by using standard structural methods of Petri nets (e.g., see [11]), the aforementioned transitions could be removed so to have a PTL-net which is the same as the one of Figure 3 and inherits the same structural properties proved in [20]. Thus, the translation into PTL-net allows us to relate two different models of NC’s in terms of structural properties which are somehow hidden in the two different types of rules used. 7 Dining Philosophers We consider a distributed system where each resource is shared by two components, and each subsystem simultaneously requires two resources in order to start its Networks of Cells and Petri Nets 57 activities. The problem of modeling such a resource sharing scenario is classically formulated as the problem of the dining philosophers: five philosophers are sitting around a table, each philosopher has his own plate and can be eating or thinking (i.e., not eating). In order to eat, a philosopher needs two forks, but there are only two forks next to each plate so that no two neighboring philosophers may be eating simultaneously. PTL-net representation The five philosophers are denoted by A,B,C,Dand E; the five forks are denoted by f0,f1,f2,f3and f4. For each X∈ {A, B, C, D, E}, we denote by l(X) its left fork and by r(X) its right fork. Specifically, we set: l(A) = f0,r(A) = f1, l(B) = f1,r(B) = f2,l(C) = f2,r(C) = f3,l(D) = f3,r(D) = f4,l(E) = f4and r(E) = f0(i.e. Asits between Eand B,Bsits between Aand C,Csits between Band D,Dsits between Cand E, and Esits between Dand A). Thus, a PTL-net FDP is constructed that contains: for each X∈ {A, B, C, D, E}, a place Xt(“Xtis thinking”) and a place Xe(“Xeis eating”), for each 0 ≤i≤4, a place fi(“fiis available”), for each X∈ {A, B, C, D, E}, a transition Xp(“Xpicks up forks”) with preF DP (Xp) = l(X)Xtr(X) and postF DP (Xp) = Xe, and a transition Xr(“Xreturns forks”) with preF DP (Xr) = Xeand postF DP (Xr) = l(X)Xtr(X). The initial marking of FDP is AtBtCtDtEtf0f1f2f3f4(i.e., all philosophers are thinking and all forks are available). Figure 5 depicts the sub-net of an FDP modeling a philosopher. This classical PTL-net model of the dining philosophers is taken from [20]. At the initial marking AtBtCtDtEtf0f1f2f3f4, for X∈ {A, B, C, D, E}, each transition Xp(“Xpicks up forks”) is enabled by giving all philosophers a chance to start eating. However, irrespectively of the execution mode adopted, no two neighboring philosophers can start eating at the same time because they share one fork and, for all 0 ≤i≤4, ficontains only one token. Thus, in the first step, depending on the execution mode, a certain number of philosophers which are not neighbors start eating by firing at least one transition Xp, whereas the other philosophers keep thinking. Then, depending on the execution mode, some other philosophers may start eating, whereas the eating philosophers may release their forks and return thinking, and so on. The fundamental property of the PTL-net FDP is that it avoids the deadlocks: FDP never produces a marking which no transition is enabled at. Moreover, from time to time, FDP offers every philosopher the chance to start eating (i.e., it avoids scenarios where no philosopher can ever start eating), although fairness is not guaranteed (i.e., there may be some philosophers which always alternate between thinking and eating with the other philosophers thinking indefinitely). Yet again, this structural properties are formally proven in [20]. 58 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan Fig. 5. PTL-net representation of a dining philosopher with its initial marking. NC Representation By starting from the PTL-net FDP, we construct an NC PH with 6 cells: cell 1 represents philosopher A, cell 2 represents philosopher B, cell 3 represents philosopher C, cell 4 represents philosopher D, cell 5 represents philosopher E, and cell 6 representing the table. If we denote by ph(i) the philosopher represented by cell i, for all 1 ≤i≤5, then cell ialways contain either an object ph(i)t(“ph(i) is thinking”) or an object ph(i)e(“ph(i) is eating”). Also, as in the previous PTL-net representation, for each X∈ {A, B, C, D, E}, we denote by l(X) its left fork and by r(X) its right fork. Cell 6, the table, always contain the currently available forks: the availability of a fork fi, for all 0 ≤i≤4, is represented as occurrence of an object fiinside cell 6. The initial configuration of PH is the tuple (At, Bt, Ct, Dt, Et, f0f1f2f3f4). The behavior of the five dining philosophers is then implemented by means of a set of rules which, for all 1 ≤i≤5, contains the rules: 1. (ph(i)t, i)(l(ph(i)) r(ph(i)),6) →(ph(i)e, i), 2. (ph(i)e, i)→(ph(i)t, i)(l(ph(i)) r(ph(i)),6). Specifically, for all 1 ≤i≤5, rule 1 models transition ph(i)p(“ph(i) picks up forks”) of the PTL-net FDP , whereas rule 2 models transition ph(i)r(“ph(i) returns forks) of the PTL-net FDP. In fact, the NC PH is the PTL-net N(FDP, C) with C(At) = C(Ae) = 1, C(Bt) = C(Be) = 2, C(Ct) = C(Ce) = 3, Networks of Cells and Petri Nets 59 C(Dt) = C(De) = 4, C(Et) = C(Ee) = 6, and C(fi) = 6 for all 0 ≤i≤4. Therefore, even for the NC PH, we can say that deadlock is avoided. Another NC representation of the five dining philosophers can be obtained by distributing the forks to five different cells. Specifically this means considering an NC PH1 obtained from PH by removing cell 6 and adding a cell 6 + i, for all 0 ≤ i≤4; each cell 6+icontains an occurrence of object fiwhenever fork fiis available. The initial configuration of PH1 is the tuple (At, Bt, Ct, Dt, Et, f0, f1, f2, f3, f4,). Then, for all 1 ≤i≤n, the new set of rules contains the rules: 1. (ph(i)t, i)(l(ph(i)), c(l(ph(i))))(r(ph(i)), c(r(ph(i))) →(ph(i)e, i), 2. (ph(i)e, i)→(l(ph(i)), c(l(ph(i))))(r(ph(i)), c(r(ph(i)))). where, for all 1 ≤i≤5, c(l(ph(i))) and c(r(ph(i))) denote the respective locations of these two forks. The NC PH1 contains rules of input radius at most 3 and cooperation degree at most 1, and it corresponds to the PTL-net N(FDP, C) with C(At) = C(Ae) = 1, C(Bt) = C(Be) = 2, C(Ct) = C(Ce) = 3, C(Dt) = C(De) = 4, C(Et) = C(Ee) = 6, and C(fi) = 6 + ifor all 0 ≤i≤4. Therefore, with respect to their PTL-net representation, the NC PH and NC PH1 cannot be distinguished. 8 Discussion Networks of cell (NC’s, for short) are a general class of P systems which encompass the essential features of evolution/communication of both P systems and tissue P systems. Rules in NC’s allow different cells to synchronize in order to consume some multisets from their inside and produce some new multisets inside some other cells. As we have seen, this means that we can express within the framework of NC’s both forms of coupled transports, like boundary rules and standard evolution rules with communication controlled by targets here, in, out. However, the structure of an NC does not necessarily corresponds to a graph or a tree; NC’s of cells abstract from the underlying structure by focusing only on the interactions which can take place between the cells present in the system. In fact, these cells can be equally thought as being physically connected in some way which makes possible for the interactions to take place, or as randomly bumping into each other and interacting whenever it is possible. In a sense, such an approach is closer to the idea of a Petri net as a collection of transitions which can fire when certain resources become available, with some of these transitions competing for the same set of resources. The difference is that in NC’s resources are objects which are specifically placed inside certain cells. This has led us to two important observations: •Despite being able to translate every NC into a PTL-net by using a construction analogous to the one used in [7, 13, 12], in the case of locally-maximal parallelism and minimal parallelism, it is not always possible for the corresponding PTL-net to mimic the behavior of the original network of cells; locally-maximal 60 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan parallelism for PTL-nets is defined with respect to the localities which are assigned to the transitions; these localities then determine which transitions can possibly fire in parallel at the same time irrespectively of the places involved; rules of NC’s involving more than one cells are instead not assigned a priori to any cell, and locally-maximally parallelism and minimal parallelism are defined with respect to a cell that can get involved in some interactions from time to time depending on a particular distribution of objects; •For a given PTL-net, it is possible to find different corresponding NC’s depending on the way places are assigned to the cells; the only restriction is that multiple occurrences of the same place has to remain confined within the same cell; for instance, for the five dining philosophers, it has been possible to produce two NC-based models: one with 6 cells and rules of input radius 2, and another one with 10 cells and rules of input radius 3. In other words, in P systems, one naturally reasons about components (e.g., producer, consumer, buffer) and these are usually seen as being separate cells (or membranes). Also, one naturally distinguishes between operations affecting the inner state of a membrane and the operations involving interactions between different membranes. Moreover, in membrane systems, the inner state of a membrane can be given by an arbitrarily large multiset; this allows us to combine cooperation at the level of objects with interaction between different cells. Petri nets, with their graphical notation, are centered around the idea of resources which have to be acquired (tokens inside places) before certain actions can be taken; this facilitates the reasoning about properties like causality (the execution of certain actions depends on the execution of some others), concurrency (certain group of action can always be executed in parallel), and conflicts (certain actions compete with some others for the usage of certain resources); in membrane systems, these structural properties instead remains somehow hidden in the formalism used for representing the rules. The present research can be continued in several directions. For instance, from a computational point of view, although we know that NC’s with a maximallyparallel semantics are computationally complete, the computational power of NC’s of cells with other semantics deserves further investigations especially for what concerns the size and types of rules used. Moreover, as pointed out in [24], interaction rules of NC’s can express forms of cooperative communication other than symport/antiport or conditional uniport, and the computational power of these forms of communication is not yet fully understood. Then, for what concerns the relationships between P systems and Petri nets, as observed in [12], other features of P systems (without being limited to NC’s) may or may not be representable in Petri nets. However, for some classes of P systems, their Petri-net representation offers the possibility of analyzing their behavior with respect to certain structural properties which can be formally proved for Petri nets and which are thoroughly managed through a plethora of tools [2]. Finally, we remark that, although one may see Petri nets as a low-level implementation of P systems, there are classes of high-level Petri Nets (e.g., colored Petri nets [11], objects nets [11], system nets Networks of Cells and Petri Nets 61 [20]) with features usually not considered for P systems, such as: types, variables, and predicates. The need for these features in P systems may be checked for specific modeling purposes against appropriate case-studies. Acknowledgements The research of Francesco Bernardini is supported by NWO, Organisation for Scientific Research of The Netherlands, project 635.100.006 “VIEWS”. References 1. The P systems web page. http://psystems.disco.unimib.it. 2. Petri nets world - Petri nets tools database. http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/quick.html. 3. F. Bernardini and M. Gheorghe. Cell Communication in Tissue P Systems: Universality Results. Soft Computing, 9, 9 (2005), 640–649. 4. F. Bernardini and V. Manca. P Systems with Boundary Rules. In Gh. P˘aun, G. Rozenberg, A. Salomaa, and C. Zandron, editors, Membrane Computing. International Workshop, WMC-CdeA 02, Curtea de Arge¸s, Romania, August 19-23, 2002. Revised Papers. Volume 2597 of Lecture Notes in Computer Science, Springer, 2003, 107–118. 5. F. Bernardini, F.J. Romero-Campero, M. Gheorghe, and M.J. P´erez-Jim´enez. A Modelling Approach Based on P Systems with Bounded Parallelism. In H.J. Hoogeboom, Gh. P˘aun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, Seventh International Workshop, WMC7, Leiden, The Netherlands, July 2006. Volume 4361 of Lecture Notes in Computer Science, Springer, 2007, 49–65. 6. G. Ciobanu, L. Pan, Gh. P˘aun, M.J. P´erez-Jim´enez. P systems with minimal parallelism. Theoretical Computer Sci., to appear. 7. S. Dal Zilio and E. Formenti. On the Dynamics of PB Systems: A Petri Net View. In C. Mart´ın-Vide, G. Mauri, Gh. P˘aun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, International Workshop, WMC 2003, Tarragona, Spain, July, 17-22, 2003, Revised Papers. Volume 2933 of Lecture Notes in Computer Science, Springer, 2004, 153–167. 8. J. Desel, W. Reisig, and G. Rozenberg, editors. Lectures on Petri Nets and Concurrency. Volume 3098 of Lecture Notes in Computer Science. Springer, 2004. 9. R. Freund. Asynchronous P Systems and P Systems Working in the Sequential Mode. In G. Mauri, Gh. P˘aun, M. J. P´erez-Jim´enez, G. Rozenberg, and A. Salomaa, editors, Membrane Computing. International Workshop, WMC 2004, Milan, Italy, June 2004. Revised and Invited Papers. Volume 3365 of Lecture Notes in Computer Science, Springer, 2005, 36–62. 10. R. Freund, L. Kari, M. Oswald, and P. Sos´ık. Computationally Universal P Systems without Priorities: Two Catalysts are Sufficient. Theoretical Computer Science, 330 2 (2005), 251–266. 11. C. Girault and R. Valk. Petri Nets for Systems Engineering. Springer, 2003. 12. J. Kleijn and M. Koutny. Synchrony and Asynchrony in Membrane Systems. In H.J. Hoogeboom, Gh. Paun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing, Seventh International Workshop, WMC7, Leiden, The Netherlands, July 2006. Volume 4361 of Lecture Notes in Computer Science, Springer, 2007, 66–85. 62 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan 13. J. Kleijn, M. Koutny, and G. Rozenberg. Towards a Petri Net Semantics for Membrane Systems. In R. Freund, Gh. P˘aun, G. Rozenberg, and A. Salomaa, editors, Membrane Computing: 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised, Selected and Invited Papers. Volume 3850 of Lecture Notes in Computer Science, Springer, 2006, 292–309. 14. S.N. Krishna and A. P˘aun. Results on Catalytic and Evolution-Communication P Systems. New Generation Computing, 22, 4 (2004), 377–394. 15. C. Martin-Vide, Gh. P˘aun, J. Pazoz, and A. Rodriguez-Paton. Tissue P Systems. Theoretical Computer Sci., 296, 2 (2003), 295–326 16. C. Mart´ın-Vide, Gh. P˘aun, and G. Rozenberg. Membrane Systems with Carriers. Theoretical Computer Science, 270, 1-2 (2002), 779–796. 17. Gh. P˘aun. Computing with Membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 18. Gh. P˘aun. Membrane Computing. An Introduction. Springer, Berlin, 2002. 19. Gh. P˘aun, Y. Sakakibara, and T. Yokomori. Membrane Systems on Graphs of Restricted Forms. Publicationes Mathematicae Debrecen, 60 (2002), 635–660. 20. W. Reisig. Elements of Distributed Algorithms. Modelling and Analysis with Petri Nets. Springer, 1998. 21. W. Reisig and G. Rozenberg, editors. Lectures on Petri Nets I: Basic Models. Volume 1491 of Lecture Notes in Computer Science. Springer, 1998. 22. W. Reisig and G. Rozenberg, editors. Lectures on Petri Nets II: Applications. Volume 1492 of Lecture Notes in Computer Science. Springer, 1998. 23. G. Rozenberg and A. Salomaa, editors. Handbook of Formal Languages, volume 1–3. Springer, 1997. 24. S. Verlan, F. Bernardini, M. Gheorghe, and M. Margenstern. Generalized Communicating P Systems. Submitted, 2007. 25. S. Verlan, F. Bernardini, M. Gheorghe, and M. Margenstern. Computational Completeness of Tissue P Systems with Conditional Uniport. In H.J. Hoogeboom, Gh. P˘aun, G. Rozenberg, and A. Salomaa, editors. Membrane Computing, Seventh International Workshop, WMC7, Leiden, The Netherlands, July 2006. Volume 4361 of Lecture Notes in Computer Science, Springer, 2007, 521–535. Extended Spiking Neural P systems with Excitatory and Inhibitory Astrocytes Aneta Binder1, Rudolf Freund1, Marion Oswald1, Lorenz Vock2 1Vienna University of Technology Faculty of Informatics Favoritenstr. 9, 1040 Vienna, Austria {ani,rudi,marion}@emcc.at 2Medical University of Vienna W¨ahringer G¨urtel 18-20, 1090 Vienna, Austria [email protected] Summary. We investigate an extended model of spiking neural P systems incorporating astrocytes and their excitatory or inhibitory influence on axons between neurons. Using very restricted variants of extended spiking neural P systems with excitatory and inhibitory astrocytes we can easily model Boolean gates like NAND-gates as well as discrete amplifiers. 1 Introduction In this paper we integrate several models describing the functioning of the human brain based on the biological background. New models in the area of neural computation were introduced based on the observation that neurons send electrical impulses (also called spikes) along axons to other neurons, e.g., see [4], [11], [12]. P systems (membrane systems) were introduced as a formal model describing the hierarchical structure of membranes in living organisms and the biological processes in and between cells (an introduction to this field can be found in [17], for the actual state of the art in this area we refer the reader to [23]). Combining the ideas of P systems and spiking neurons, a new variant of socalled tissue P systems (see [13]) called spiking neural P systems was investigated, e.g., see [8], [18]. An extended version of spiking neural P systems allowing to send different informations along the axons between two neurons was investigated in [1]. In spiking neural P systems (see [8]), the contents of a neuron consists of a number of so-called spikes. The rules assigned to a cell allow us to send information to other neurons in the form of electrical impulses – spikes – which are summed up at the target cell; the application of the rules depends on the contents of the neuron. In [1], an extended version of this original model of spiking neural P systems was 70 Extended SN P systems with Excitatory and Inhibitory Astrocytes &% '$ a a→a  ? p -&% '$ a→a q - C    ?   @ @ @ @@ @    r ≤2|1 ? A ? B Fig. 5. NAND-gate. is sent to neuron q, whereas if less than two input spikes arrive in astrocyte r, then no spike will reach the output neuron q. If both inputs (Aand B) represent the same signal, i.e., if A=B, then neuron qwill get a spike if and only if A= 1. The NAND-gate is shown in Figure 5: again A, B are the inputs, Cis the output; the neuron pis a source sending out one spike in each time step which only reaches neuron qif the axon is not inhibited by the astrocyte which reaches the inhibitory threshold 2 if and only if both inputs Aand Bare 1. Any network of NAND-gates and AND-gates (only needed as identities keeping a signal as it is for one time step) of depth nyields the result of the computation with a delay of n, i.e., given the input at time t, the corresponding output appears at time t+n. 3.3 A Discrete Amplifier The ESNPA system depicted in Figure 6 represents a discrete amplifier which, as soon as the input from Bgoes beyond the given threshold k, from the input x given at Ecomputes the function f(x) = nx at C. We have to remark that the rules al→algiven in the neurons pand qrepresent the (theoretically infinite) set of rules {a}∗/al→al|l∈N(for practical applications, an upper bound can be assumed). 4 Conclusion The model we discussed in this paper is already very powerful from a theoretical point of view as elaborated in the preceding section. On the other hand, for specific applications, especially in the area of artificial neural networks and self-organizing feature maps, an extended version where we allow the dynamic evolution of new A. Binder et al. 71 - E &% '$ al→al p -&% '$ al→al q - C    ?   @ @ @ @@ @    ≥k| ∗ n r ? B Fig. 6. An ESNPA amplifier. connections between neurons, could be useful; the influence of the already existing astrocytes on these new axons plays an important role. Another variant to be considered in the future are networks where part of the network may be destroyed which also has an interesting biological background. In this case, the ability of such a complex network to reorganize itself is the most challenging aspect of this variant. Other variants may allow one astrocyte to influence more than one axon, eventually even in a different way and on the other hand, one axon may be influenced by several astrocytes, again eventually in a different way (in an inhibitory or excitatory way). For example, in this way more complex functions can be described by a single “unit” (circuit). References 1. A. Alhazov, R. Freund, M. Oswald and M. Slavkovik, Extended Spiking Neural P Systems Generating Strings and Vectors of Non-Negative Integers, in: H. J. Hoogeboom, Gh. Paun, G. Rozenberg (eds), Pre-proceedings of the 7th Workshop on Membrane Computing WMC7, 2006, pp. 88-101. 2. F. Buarque de Lima Neto and P. de Wilde, Venn-like models of neo-cortex patches, International Joint Conference on Neural Networks, 2006, pp.89–96. 3. R. Freund and M. Oswald, Extended spiking neural P systems with inhibitory axons, in: M. Sugisaka, H. Tanaka, Proc. International Symposium on Artificial Life and Robotics, Beppu, Oita, Japan, 2007. 4. W. Gerstner, W. Kistler, Spiking Neuron Models. Single Neurons, Populations, Plasticity. Cambridge Univ. Press, 2002. 5. C. Giaume and K. Mc Carthy, Control of gap-junctional communication in astrocytic networks., Trends Neuroscience 15, 1995, pp. 5535–5550. 6. P. Guthrie, J. Knappenberger, M. Segal, M. Bennet, A. Charles and S. Kater., ATP released from astrocyte mediates glial calcium waves.,J Neuroscience 19, 1999, pp. 520–528. 72 Extended SN P systems with Excitatory and Inhibitory Astrocytes 7. F. He and Ye. Sun, Glial cells more than support cells?, Int J Biochem Cell Biol. 39(4), 2007, pp. 661–665. 8. M. Ionescu, Gh. P˘aun and T. Yokomori, Spiking neural P systems, Fundamenta Informaticae 71, 2–3, 2006, pp. 279–308. 9. J. Kleijn and M. Koutny, Processes of nets with range arcs, CS-TR 985, School of Computing Science, Newcastle University, Oct. 2006. 10. T. Kohonen, Self-Organizing Maps, 3rd ed., Springer-Verlag, Berlin, 2001. 11. W. Maass, Computing with spikes, Special Issue on Foundations of Information Processing of TELEMATIK 8, 1, 2002, pp. 32–36. 12. W. Maass and C. Bishop (eds), Pulsed Neural Networks. MIT Press, Cambridge, 2003. 13. C. Mart´ın-Vide, J. Pazos, Gh. P˘aun and A. Rodr´ıguez-Pat´on, A new class of symbolic abstract neural nets: Tissue P systems, in: Proceedings of COCOON 2002, Singapore, Lecture Notes in Computer Science 2387, Springer-Verlag, Berlin, 2002, pp. 290–299. 14. S. Mennerik and C. Zorumski, Glial contribution to excitatory neurotransmission in cultural hippocampal cells., Nature 368, 1994, pp. 59–62. 15. W. Nett, S. Oloff and K. McCarthy, Hippocampal astrocytes in situ exhibit calcium oscillations that occur independent of neuronal activity., J Neurophysiol. 87(1), 2002, pp. 528–537. 16. R. Parri and V. Crunelli, An astrocyte bridge from synapse to blood flow., Nat Neurosci 6(1), 2003, pp. 5-6. 17. Gh. P˘aun, Computing with Membranes: An Introduction. Springer, Berlin, 2002. 18. Gh. P˘aun, M.J. P´erez-Jim´enez and G. Rozenberg, Spike trains in spiking neural P systems, Intern J Found Computer Sci, to appear (also available at [23]). 19. G. Perea and A. Araque, Communication between astrocytes and neurons: a complex language. Journal of Physiology Paris 96, 2002, 199–207. 20. J. Porter and Kd. Mc Carthy, Astrocytic neurotransmitter receptors in situ and in vivo., Prog Neurobiol. (51), 1997, pp. 7817–7830. 21. X. Shen and P. de Wilde, Long-term neuronal behavior caused by two synaptic modification mechanisms. Neurocomputing 70, 7-9, 2007, 1482–1488. 22. G. Rozenberg and A. Salomaa (eds), Handbook of Formal Languages (3 volumes). Springer, Berlin, 1997. 23. The P Systems Web Page, http://psystems.disco.unimib.it Information Theory over Multisets Cosmin Bonchi¸s1, Cornel Izba¸sa1, Gabriel Ciobanu2 1Research Institute “e-Austria” Timi¸soara, Romania {cosmin, cornel}@ieat.ro 2“A.I. Cuza” University, Faculty of Computer Science and Romanian Academy, Institute of Computer Science [email protected] “The words, the sad words, Sometimes surround the time As a pipe, the water which flows within.” Nichita St˘anescu Summary. Starting from Shannon theory of information, we present the case of producing information in the form of multisets, and encoding information using multisets. We compute the entropy of a multiset information source by constructing an equientropic string source (with interdependent symbols), and we compare this with a string information source with independent symbols. We then study the encoder and channel part of the system, obtaining some results about multiset encoding length and channel capacity. 1 Motivation The attempt to study information sources which produce multisets instead of strings, and ways to encode information on multisets rather than strings, originates in observing new computational models like membrane systems which employ multisets [5]. Membrane systems have been studied extensively and there are plenty of results regarding their computing power, language hierarchies and complexity. However, while any researcher working with membrane systems (called also P systems) would agree that P systems process information, and that living cells and organisms do this too, we are unaware of any attempt to precisely describe natural ways to encode information on multisets or to study sources of information which produce multisets instead of strings. One could argue that, while some of the information in a living organism is encoded in a sequential manner, like in DNA for example, there might be important molecular information sources which involve multisets (of molecules) in a non-trivial way. A simple question: given a P system with, say, 2 objects aand 3 objects b from a known vocabulary V(suppose there are no evolution rules), how much 74 C. Bonchi¸s, C. Izba¸sa, G. Ciobanu information is present in that system? Also, many examples of P systems perform various computational tasks. Authors of such systems encode the input (usually numbers) in various ways, some by superimposing a string-like structure on the membrane system [1], some by using the natural encoding or the unary numeral system, that is, the natural number nis represented with nobjects, for example, an. However, just imagine a gland which uses the bloodstream to send molecules to some tissue which, in turn, sends back some other molecules. There is for sure an energy and information exchange. How to describe it? Another, more general way to pose that question is: what are the natural ways to encode numbers, and more generally, information on multisets, and how to measure the encoded information? If membrane systems, living cells and any other (abstract or concrete) multiset processing machines are understood as information processing machines, then we believe that such questions should be investigated. According to our knowledge, this is the first attempt of such an investigation. We start from the idea that a study of multiset information theory might produce interesting, useful results at least in systems biology; if we understand the natural ways to encode information on multisets, there is a chance that Nature might be using similar mechanisms. Another way in which this investigation seems interesting to us is that there is more challenge in efficiently encoding information on multisets, because they constitute a poorer encoding media compared to strings. Encoding information on strings or even richer, more organized and complex structures are obviously possible and have been studied. Removing the symbol order, or their position in the representation as strings can lead to multisets carrying a certain penalty, which deserves a precise description. Order or position do not represent essential aspects for information encoding; symbol multiplicity, a native quality of multisets, is enough for many valid purposes. We focus mainly on such “natural” approaches to information encoding over multisets, and present some advantages they have over approaches that superimpose a string structure on the multiset. Then we encode information using multisets in a similar way as it is done using strings. There is also a connection between this work and the theory of numeral systems. The study of number encodings using multisets can be seen as a study of a class of purely non-positional numeral systems. 2 Entropy of an Information Source Shannon’s information theory represents one of the great intellectual achievements of the twentieth century. Information theory has had an important and significant influence on probability theory and ergodic theory, and Shannon’s mathematics is a considerable and profound contribution to pure mathematics. Shannon’s important contribution comes from the invention of the sourceencoder-channel-decoder-destination model, and from the elegant and general solution of the fundamental problems which he was able to pose in terms of this model. Shannon has provided significant demonstration of the power of coding with delay Information Theory over Multisets 75 in a communication system, the separation of the source and channel coding problems, and he has established the fundamental natural limits on communication. As time goes on, the information theoretic concepts introduced by Shannon become more relevant to day-to-day more complex process of communication. 2.1 Short Review of Shannon Information Theory We use the notions defined in the classical paper [6] where Shannon has formulated a general model of a communication system which is tractable to a mathematical treatment. Definition 1. The quantity His a reasonable measure of choice or information. Consider an information source modeled by a discrete Markov process. For each possible state iof the source there is a set of probabilities pi(j) associated to the transitions to state j. Each state transition produces a symbol corresponding to the destination state, e.g., if there is a transition from state ito state j, the symbol xjis produced. Each symbol xihas an initial probability pi∈1..n corresponding to the transition probability from the initial state to each state i. We can also view this as a random variable Xwith xias events with probabilities pi, X =x1x2··· xn p1p2··· pn. There is an entropy Hifor each state. The entropy of the source is defined as the average of these Hiweighted in accordance with the probability of occurrence of the states: H(X) = X i PiHi=−X i,j Pipi(j) log pi(j) (1) Suppose there are two symbols xi, xjand p(i, j) is the probability of the successive occurrence of xiand then xj.The entropy of the joint event is H(i, j) = −X i,j p(i, j) log p(i, j) The probability of symbol xjto appear after the symbol xiis the conditional probability pi(j). String Entropy Consider an information source which produces sequences of symbols selected from a set of nindependent symbols xiwith probabilities pi. The entropy formula for such a source is given in [6]: H(X) = n X i=1 pilogb 1 pi 76 C. Bonchi¸s, C. Izba¸sa, G. Ciobanu 2.2 Multiset Entropy We consider a discrete information source modeled by a discrete-time first-order Markov process (or Markov chain) which produces multiset messages (as opposed to string messages). A message is a multiset of symbols. To compute the entropy of such a source, we construct an equientropic source which produces strings with mutually dependent symbols. Each string produced by this equientropic source is an exponent of a multiset produced by the multiset source, because a multiset is a string equivalence class. The entropy of such a source is computed by Shannon’s formula 1, where Pi is the probability of state i, and pi(j) is the transition probability from state ito state j. To compute the probability of the state iwe must first observe what is specific for the multisets. The corresponding state trees are presented in the next figures.                           ? ? ?        = ZZZZZZZZ~         AAAAU     JJJ J^ AAA AU     @@@@ @R S0 S1S2S3 S4S5S6S7S8S9S10 S11 S12 x1 x2 x3 x1x2 x3x1x2 x3x1x2 x3 Fig. 1. String source states tree We take the Pifor the first level of the tree, and because P0= 1 we get: Pi=P0p0(i) = pi(2) To compute the transition probability pi(j) we know that for multisets p(i, j) = 0 for i > j. Let Nbe the number of all symbols (with repetition allowed). Then the most probable number of symbols xjis pjN. For i≤j, in order to obtain jafter i, we observe that the symbols xi>j cannot be produced. Therefore, the probability to obtain jafter iis given by the number of favorable cases over all possible cases Information Theory over Multisets 77                     ? ?        = SSSSS Sw ? AAA AU     ? JJJ J^     S0 S1S2S3 S4S5S6S8S9S12 x1 x2 x3 x1 x2 x3x2x3x3 Fig. 2. Multiset source states tree pi(j) = pjN N− i−1 X j=1 pjN =pj n X j=i pj namely pi(j) =    0, i > j pj Pn j=ipj , i ≤j(3) Theorem 1. The entropy formula of a multiset generating information source is: H(X) = − n X i=1 pi n X j=i pj Pn k=ipk log pj Pn k=ipk.(4) Proof. From 1, 2, and 3 we infer H(X) = −X i,j,i≤j pi pj Pn k=ipk log pj Pn k=ipk =− n X i=1 pi n X j=i pj Pn k=ipk log pj Pn k=ipk. Proposition 1. When the events are equiprobable, i.e., pi=1 n, then 78 C. Bonchi¸s, C. Izba¸sa, G. Ciobanu H(X) = log n! n. Proof. We substitute 1 nfor piin equation (4), and get H(X) = − n X i=1 1 n n X j=i 1 n Pn j=i 1 n log 1 n Pn j=i 1 n!! =−1 n n X i=1 n X j=i 1 n−i+ 1 log 1 n−i+ 1 =−1 n n X i=1 1 n−i+ 1 log 1 n−i+ 1n X j=i 1 =1 n n X i=1 log(n−i+ 1) =1 n n X i=1 log i=log n! n. String Source Entropy vs. Multiset Source Entropy Theorem 2. The entropy of a multiset-producing source is lower than or equal to the entropy of an equiprobable string-producing source: Hmultiset ≤Hstring(xi−equiprobable) Proof. We know that Pn i=1 pi= 1 ⇒Pn k=ipk≤1⇒ pj Pn k=ipk≥pj(5) Gibbs inequality suppose that P={p1, p2,...,pn}is a probability distribution. Then for any other probability distribution Q={q1, q2,...,qn}the following inequality holds − n X i=1 pilog pi≤ − n X i=1 pilog qi(6) Then Information Theory over Multisets 79 Hm(X) = − n X i=1 pi n X j=i pj Pn k=ipk log pj Pn k=ipk(5) ≤ ≤ − n X i=1 pi n X j=i pj Pn k=ipk log pj=− n X i=1 pi Pn k=ipk n X j=i pjlog pj (6) ≤ (6) ≤ − n X i=1 pi Pn k=ipk n X j=i pjlog qj with Qi={qj|where, j=i, n and Pn j=iqj= 1}, and qj=1 n−i+ 1: − n X i=1 pi Pn k=ipk n X j=i pjlog qj=− n X i=1 pi Pn k=ipk n X j=i pjlog 1 n−i+ 1 =− n X i=1 pi Pn k=ipklog 1 n−i+ 1n X j=i pj= n X i=1 pilog(n−i+ 1) ≤ ≤ n X i=1 pilog n= log n=Hstring(X)xi−equiprobable Corollary 1. When Xis equiprobable, Hm≤Hs. Proof. For pi=1 nwe have Hmultiset =1 n n X i=1 log i=log n! n≤log n=Hstring Maximum Entropy for a Multiset Source For a multiset source, equiprobable events do not generate the maximum entropy. This is obtained by maximizing expression 4, which seems difficult in the general case, but we give an example for the simplest case - with two events (a binary multiset source): X=x1x2 p1p2 The multiset entropy for these events is: Hmultiset(X) = −p1(p1log p1+ p2log p2). Let p=p1⇒Hmultiset(X) = −p[plog p+ (1 −p) log(1 −p)].Since this function has only one maximum in [0,1], we need to solve: H0 multiset(X) = 2p[log(1 −p)−log p]−log(1 −p) = 0. A numerical solution is p≈0.703506. The maximizing probability distribution is X≈x1x2 0.703506 0.296494and the maximum entropy is Hmultiset(X)≈0.427636 < Hstring(Xequiprobable ) = log 2 ≈0.6931472. VisualTissue: A Friendly Tool to Study Tissue P Systems Solutions for Graph Problems Rafael Borrego-Ropero, Daniel D´ıaz-Pernil, Juan A. Nepomuceno Escuela T´ecnica Superior de Ingener´ıa Inform´atica Universidad de Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain {rborrego,sbdani,janepo}@us.es Summary. P systems can be classified in two main groups: P systems with the membrane structure described by a tree, and tissue P systems with the membranes placed in the nodes of an arbitrary graph. NP-complete problems have been solved in linear time by trading space for time in the framework of recognizing tissue P systems with cell division. The design of this kind of systems is not an easy task to understand. In this paper we present a software application to help the design of solutions to NP-complete problems in the framework of recognizing tissue P systems with cell division. VisualTissue application can be downloaded from the web: www.visualtissue.es.kz. 1 Introduction Membrane Computing is an emergent branch of Natural Computing introduced by Gh. P˘aun in [9], which, considering as computations the processes that take place into living cells, constructs a new non-deterministic model of computation. In membrane computing there are two types of frameworks: P systems with the membrane structure described by a tree, inspired from the cell, and tissue P systems with the membranes placed in the nodes of an arbitrary graph. The second type corresponds to the idea of forming a network of membranes linked in a specific manner and working together, [10]. In both types, the main idea is having multisets of objects placed in compartments and evolving according to given rules in a synchronous non-deterministic maximally parallel manner. In the last years, this new field has been addressed in different ways: the study of computational properties such as computational power or complexity classes, definition of new variants of membrane systems closer to biological reality, using Membrane Computing as a new framework for performing biological simulations, etc. In the P systems web page [18] several softwares can be found. Most of them are 88 R. Borrego-Ropero, D. D´ıaz-Pernil, J.A. Nepomuceno thought in order to run an experiment which is built using some kind of membrane system as a simulation framework, for example, for simulating biological systems, as in [14]. On the other hand, another group of software applications are thought as an easy way of visualizing the computations of a P system, [8], that is to say, as a learning tool. In this paper we present a new visual tool called VisualTissue which have been developed in order to help users to understand the computations of tissue P systems with cell division. We have considered the reference [4], which solves 3-col problem in the framework of tissue P systems with cell division. Polynomial solutions to NP-complete problems in Membrane Computing are done by trading time for space, in a theoretical way. Although real implementations of such systems are no possible, because it should be necessary to implement the maximal parallelism in some way, there are very interesting problems to threat in this framework, for example, the P6=NP conjecture [13]. Our tool helps the user to understand the performance of one class of such systems. This paper is organized as follows: in Section 2 tissue P systems with cell division and the 3-col problem are explained, in Section 3 the VisualTissue application software is presented and some of the most important implementation aspects are commented. Finally, ideas for future work are formulated. 2 Tissue P Systems with Cell Division We will give a definition of this model, but first we briefly recall some of the concepts used later. 2.1 Preliminaries An alphabet,Σ, is a non empty set, whose elements are called symbols. An ordered sequence of symbols is a string. The number of symbols in a string uis the length of the string, and it is denoted by |u|. As usual, the empty string (with length 0) will be denoted by λ. The set of strings of length nbuilt with symbols from the alphabet Σis denoted by Σnand Σ∗=∪n≥0Σn. A language over Σis a subset from Σ∗. Amultiset mover a set Ais a pair (A, f) where f:A→Nis a mapping. If m= (A, f) is a multiset, then its support is defined as supp(m) = {x∈A|f(x)> 0}and its size is defined as Px∈Af(x). A multiset is empty (resp. finite) if its support is the empty set (resp. finite). If m= (A, f) is a finite multiset over A, then it will be denoted by m= {{a1,...,ak}}, where each element aioccurs f(ai) times, or by a string containing the symbols a1,...,ak. Agraph Gis a pair G= (V, E) where Vis the set of vertices and Eis the set of edges, each one of which is a (unordered) pair of (different) vertices. If {u, v} ∈ E, we say that uis adjacent to v(and also vis adjacent to u). The degree of v∈V is the number of adjacent vertices to v. VisualTissue: A Graphical Simulator of Tissue P Systems 89 In what follows, we assume that the reader is already familiar with the basic notions and terminology underlying P systems. For details, see [10]. 2.2 Tissue P Systems with Cell Division In the first definition of the model of tissue P systems [6, 7] the membrane structure does not change along the computation. Based on the cell-like model of P systems with active membranes, Gh. P˘aun et al. presented in [12] a new model of tissue P systems with cell division. The biological inspiration is clear: alive tissues are not static network of cells, since cells are duplicated via mitosis in a natural way. The main features of this model, from the computational point of view, are that cells are not polarized (the opposite holds in the cell-like model of P systems with active membranes, see [10]); the cells obtained by division have the same labels as the original cell and if a cell is divided, its interaction with other cells or with the environment is blocked during the mitosis process. In some sense, this means that while a cell is dividing it closes the communication channels with other cells and with the environment. Formally, a tissue P system with cell division of degree q≥1 is a tuple of the form Π= (Γ, w1,...,wq,E,R, i0), where: 1. Γis a finite alphabet, whose symbols will be called objects. 2. w1,...,wqare strings over Γ. 3. E ⊆ Γ. 4. Ris a finite set of rules of the following forms: (a) Communication rules: (i, u/v, j), for i, j ∈ {0,1,2,...,q}, i 6=j,u, v ∈Γ∗. (b) Division rules: [a]i→[b]i[c]i, where i∈ {1,2,...,q}and a, b, c ∈Γ. 5. i0∈ {0,1,2,...,q}. A tissue P system with cell division of degree q≥1 can be seen as a set of q cells (each one consisting of an elementary membrane) labeled by 1,2, . . ., q. We shall use 0 to refer to the environment, and i0denotes the output region (which can be the region inside a cell or the environment). The communication rules determine a virtual graph, where the nodes are the cells and the edges indicate if it is possible for pairs of cells to communicate directly. This is a dynamical graph, as new nodes can appear produced by the application of division rules. The strings w1,...,wqdescribe the multisets of objects placed in the qcells of the system. We interpret that E ⊆ Γis the set of objects placed in the environment, each one of them in an arbitrarily large amount of copies. A communication rule (i, u/v, j) can be applied over two cells iand jsuch that uis contained in cell iand vis contained in cell j. The application of this rule means that the objects of the multisets represented by uand vare interchanged between the two cells. 90 R. Borrego-Ropero, D. D´ıaz-Pernil, J.A. Nepomuceno The division rule [a]i→[b]i[c]ican be applied to a cell icontaining object a. The application of this rule divides this cell into two new cells with the same label. All the objects in the original cell are replicated and copied in each of the new cells, with the exception of the object a, which is replaced by the object bin the first new cell and by cin the second one. Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel way. In one step, each object in a cell can only be used for one rule (non-deterministically chosen when there are several possibilities), but any object which can participate in a rule of any form must do it, i.e., in each step we apply a maximal set of rules. This way of applying rules has only one restriction: when a cell is divided, the division rule is the only one which is applied for that cell in that step; the objects inside that cell do not evolve in that step. 2.3 Recognizing Tissue P Systems with Cell Division NP-completeness has been usually studied in the framework of decision problems. Let us recall that a decision problem is a pair (IX, θX) where IXis a language over a finite alphabet (whose elements are called instances) and θXis a total boolean function over IX. In order to study the computing efficiency for solving NP-complete decision problems, a special class of tissue P systems with cell division is introduced in [12]: recognizing tissue P systems. The key idea of such recognizing system is the same one as from recognizing P systems with a cell-like structure. Recognizing cell-like P systems were introduced in [15] and they are the natural framework to study and solve decision problems within Membrane Computing, since deciding whether an instance has an affirmative or negative answer is equivalent to deciding if a string belongs or not to the language associated with the problem. In the literature, recognizing cell-like P systems are associated in a natural way with P systems with input. The data related to an instance of the decision problem has to be provided to the P system in order to compute the appropriate answer. This is done by codifying each instance as a multiset placed in an input cell. The output of the computation (yes or no) is sent to the environment. In this way, cell-like P systems with input and external output are devices which can be seen as black boxes, in the sense that the user provides the data before the computation starts, and then waits outside the P system until it sends to the environment the output in the last step of the computation. A recognizing tissue P system with cell division of degree q≥1 is a tuple Π= (Γ, Σ, w1,...,wq,E,R, iin, i0), where: •(Γ, w1,...,wq,E,R, i0) is a tissue P system with cell division of degree q≥1 (as defined in the previous section). VisualTissue: A Graphical Simulator of Tissue P Systems 91 •The working alphabet Γhas two distinguished objects yes and no, present in at least one copy in some initial multisets w1, ..., wq, but not present in E. •Σis an (input) alphabet strictly contained in Γ. •iin ∈ {1,...,q}is the input cell. •The output region i0is the environment. •All computations halt. •If Cis a computation of Π, then either the object yes or the object no (but not both) must have been released into the environment, and only in the last step of the computation. The computations of the system Πwith input w∈Γ∗start from a configuration of the form (w1, w2,...,wiin w,...,wq;E), that is, after adding the multiset w to the contents of the input cell iin. The multiset wis recognized by Πif and only if the object yes is sent to the environment, in the last step of the corresponding computation. Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the environment associated to the corresponding halting configuration of C. 2.4 A Solution to the 3–coloring Problem Ak–coloring (k≥1) of an undirected graph G= (V, E) is a function f:V→ {1,...,k}, where the numbers are interpreted as colors. We say that Gis k– colorable if there exists a k–coloring, f, such that f(u)6=f(v) for every edge {u, v} ∈ E(such a k–coloring fis said to be valid). The 3–coloring problem is the following: given an undirected graph G, decide whether or not Gis 3-colorable; that is, if there exists a valid 3–coloring of G. This problem is related to the famous Four Color Conjecture (solved by Appel and Haken [2, 3]). It is a particular case of the colorability problem: Given an undirected graph Gand a number k, decide whether Gis k-coloreable. The NP- completeness of the 3–coloring problem was proved by Stockmeyer [16] (see [5]). First of all we define a polynomial encoding of the 3–coloring problem in a family Πof P systems constructed as in [4]. Let u= (V, E) be an instance of the problem, with nvertices and medges. Then we consider a size mapping on the set of instances defined as s(u) = hn, mi. The codification of the instance will be the multiset cod(u) = {{Aij :{Ai, Aj} ∈ E∧1≤i < j ≤n}} ∪ {{wq}}. The recognizing tissue P system with cell division that was used to solve the 3–coloring problem in [4] is defined as follows. For each n, m ∈N, we consider the system Π(hn, mi) = (Γ(hn, mi), Σ(n), w1, w2(n),R(hn, mi),E(hn, mi), iin, i0) where: •Γ(hn, mi) is the set 92 R. Borrego-Ropero, D. D´ıaz-Pernil, J.A. Nepomuceno {Ai, Ri, Ti, Bi, Gi, Ri, Bi, Gi: 1 ≤i≤n} ∪ {ai: 1 ≤i≤2n+m+dlog me+ 11} ∪ {ci: 1 ≤i≤2n+ 1} ∪ {di: 1 ≤i≤ dlog me+ 1} ∪ {fi: 2 ≤i≤m+dlog me+ 6} ∪ {Aij , Pij , Pij , Rij , Bij , Gij : 1 ≤i < j ≤n} ∪ {b, D, D, e, T, S, N, [, yes,no} •Σ(n) = {Aij : 1 ≤i < j ≤n} •w1={{a1, b, c1,yes,no}} •w2(n) = {{D, A1,...,An}} • R(hn, mi) is the set of rules: 1. Division rules: r1,i ≡[Ai]2→[Ri]2[Ti]2for i= 1,...,n r2,i ≡[Ti]2→[Bi]2[Gi]2for i= 1,...,n 2. Communication rules: r3,i ≡(1, ai/ai+1,0) for i= 1,...,2n+m+dlog me+ 10 r4,i ≡(1, ci/c2 i+1,0) for i= 1,...,2n r5≡(1, c2n+1/D, 2) r6≡(2, c2n+1/d1D, 0) r7,i ≡(2, di/d2 i+1,0) for i= 1,...,dlog me r8≡(2, D/e f2,0) r9,i ≡(2, fi/fi+1,0) for i= 2,...,m+dlog me+ 5 r10,ij ≡(2, ddlog me+1Aij /Pij ,0) for 1 ≤i < j ≤n r11,ij ≡(2, Pij /Rij Pij ,0) for 1 ≤i < j ≤n r12,ij ≡(2, Pij /Bij Gij ,0) for 1 ≤i < j ≤n r13,ij ≡(2, RiRij /RiRj,0) for 1 ≤i < j ≤n r14,ij ≡(2, BiBij /BiBj,0) for 1 ≤i < j ≤n r15,ij ≡(2, GiGij /GiGj,0) for 1 ≤i < j ≤n r16,j ≡(2, RjRj/[, 0) for 1 ≤j≤n r17,j ≡(2, BjBj/[, 0) for 1 ≤j≤n r18,j ≡(2, GjGj/[, 0) for 1 ≤j≤n r19 ≡(2, e [/λ, 0) r20 ≡(2, e fm+dlog me+6/T, 0) r21 ≡(2, T/λ, 1) r22 ≡(1, b T/S, 0) r23 ≡(1, S yes/λ, 0) r24 ≡(1, b a2n+m+dlog me+11/N, 0) r25 ≡(1, N no/λ, 0) • E(hn, mi) = Γ(hn, mi)− {yes,no} •iin = 2 is the input cell. •i0= 0 is the output region. VisualTissue: A Graphical Simulator of Tissue P Systems 93 3 A Look Inside VisualTissue VisualTissue is a visual software application to understand the design of solutions for NP-complete problems, in the framework of recognizing tissue P system with cell division. Some programming decisions have been taken in order to develop the application. We have chosen C# as programming language because it is a portable and a powerful object-oriented programming language. A great graphical package is available with the language so that C# is a good language for developing a visual tool. The software follows the Model-View-Controller (MVC), an architecture model of software development used in interactive systems. Three different parts or layers can be distinguished: data handling layer, algorithmic or business logic layer, and user interface or graphical layer. With this, it is easier to do maintenance of the code. Rules system Data handling User interface Fig. 1. Model-View-Controller architecture software The application can handle data stored in XML and normal text files, which are compatible with Algraf Project, [19]. XML files can be easily generated and it is the best way to interact with data generated by other programs. Rules of the systems are fixed for the solution of each problem. In a future version, the user will be able to introduce his own tissue P system rules in order to study other possible solutions. The algorithmic layer implements a recognizing tissue P system with cell division. All rules are applied in a non deterministic and maximal parallel way. The design of the tissue P system machine for solving the problem is non-deterministic until the 2nstep. Every computation path reaches the same configuration in 2n steps, and after that the machine is deterministic and confluent. Consequently, we have chosen only a computation path in order to implement the tissue P system in the software, namely the one determined by the lexicographical election of the rules in non-deterministic steps. Other graph problems solutions can be easily added. The graphical layer allows the user a visual and friendly interaction with the application. At the end of the simulation one can see the colored graph result of the problem if the answer is yes. 94 R. Borrego-Ropero, D. D´ıaz-Pernil, J.A. Nepomuceno Fig. 2. Firstly, the graph to be studied must be drawn. A small screen show us wether it is 3-colorable or not. 3.1 An User Overview of the Application This software tool allows us to follow step by step the execution of tissue P system with membrane division when solving the 3-col problem, [4]. The answers for a specific problem will be yes or no, and the colored graph is provided if it is possible. The user basically can do three different operations to run the system: •Load or draw with the mouse the graph which is going to be studied. Several graphical options are available in the main window. Graphs can be handled in a easy way and images can be saved as image files or pdf files. •Choose tissue 3-col algorithm in order to carry out the simulation. A second screen is showed in which each computation step can be observed. For each step, a graphical situation can be viewed and the different rules applied in each step are written in the bottom of the screen. The picture can be easily handled and each moment of the performance of the algorithm, and can be saved in different images format, or press the buttons with arrows to move between steps. •Choose GO TO option to go directly to a specific step of the system. VisualTissue software is available on the web, at: www.visualtissue.es.kz VisualTissue: A Graphical Simulator of Tissue P Systems 95 Fig. 3. The performance of the tissue P system can be observed step by step. 4 Future Works Future works will be focused on different improvements as, for example: to handle input files of rules, work with other graph problems, consider other kinds of tissue P systems rules such as membrane creation, etc. One of the most interesting future tasks will be to build a software which simulates a Spiking Neural P system, extending this graphical tool. This future software task will be not only a way of visualizing the performance of the system, but also a framework to do simulations with Spiking Neural P systems too. References 1. B. Alberts, A. Johnson, J. Lewis, M. Raff, K. Roberts, P. Walter: The Molecular Biology of the Cell. Fourth Edition, Garland Publ. Inc., London, 2002. 2. K. Appel, W. Haken: Every planar map is 4-colorable - 1: Discharging. Illinois Journal of Mathematics, 21 (1977), 429–490. 3. K. Appel, W. Haken: Every planar map is 4-colorable - 2: Reducibility. Illinois Journal of Mathematics, 21 (1977), 491–567. 4. D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: A linear–time tissue P system based solution for the 3–coloring problem. Theoretical Computer Science, to appear. 102 N. Busi causal operator containing the cause name associated to the drip(σ) action. Thus, we obtain the following causal reactions: drip(σ).drip(ρ)(| |)h;∅ −−→ {h}:: drip(ρ)(| |)◦σ(| |)k;{h} −−−→ {k}:: 0(| |)◦σ(| |)◦ρ(| |) The decoration h;∅of the first reaction means that the first reaction is labeled with the causal name hand that its set of causes is empty. The decoration k;{h} of the second reaction means that the second reaction has associated the causal name k, and it is caused by the reaction named h(i.e., the first reaction). The process {h}:: drip(ρ) means that the first action performed by process drip(ρ) is caused by the reaction named h. Note that – for the sake of brevity – process {k}:: 0 is decorated only with the immediate cause {k}, as the whole set of causes, i.e., {h, k}can be easily constructed. To lighten the notation, in the following we will drop the parentheses surrounding the set of causes, if this creates no confusion. The other kind of causality, i.e., synchronization causality, arises when two processes synchronize on complementary actions. Consider the system drip(σ1).maten.drip(τ1)(| |)◦drip(σ2).mate⊥ n.drip(τ2)(| |) The mate reaction can be performed when both the actions drip(σ1) and drip(σ2) have been performed; hence, it is caused by both actions. We obtain the following: drip(σ1).maten.drip(τ1)(| |)◦drip(σ2).mate⊥ n.drip(τ2)(| |)h1;∅ −−−→ h1:: maten.drip(τ1)(| |)◦drip(σ2).mate⊥ n.drip(τ2)(| |)◦σ1(| |)h2;∅ −−−→ h1:: maten.drip(τ1)(| |)◦h2:: mate⊥ n.drip(τ2)(| |)◦σ1(| |)◦σ2(| |)k;h1,h2 −−−−−→ k:: (drip(τ1)|drip(τ2)(| |)◦σ1(| |)◦σ2(| |) Hence, the (label kof the) mate reaction will be an immediate cause for both drip(τ1) and drip(τ2), and the global set of causes of these two drip actions will be {h1, h2, k}. 3.2 How does the causes distribute over the parallel components of a membrane process? When moving to consider the features of the causal relation peculiar of membrane calculi, a first question arises: if a process on a membrane performs an action, this action will be a cause only for its continuation (and eventually for the continuation of its synchronizing action), or for the whole process on the membrane? In other words, consider the system maten|drip(σ)(| |)◦mate⊥ n(| |) If the system performs the mate synchronization, then the drip action will be caused or not by the mate action? The assumption that the drip will be caused Towards a Causal Semantics for Brane Calculi 103 by the mate may have the following biological interpretation: when a membrane interaction operation is performed, all the membrane is involved, and at the end of the operation the structure of all the membrane has been affected. This assumption is considered in [14] in the definition of a causal semantics for Beta-binders [21, 22] , a bio-inspired process calculus roughly consisting of unnested compartments enclosing π-calculus processes. It is also used in [2] for the definition of a maximal parallelism semantics (i.e., step semantics with maximal progress: if an action can be performed in the current step, then it must be performed) for MBD. It is also the common approach used in the definition of the maximal parallelism semantics for Membrane Systems with evolving membranes (see, e.g., [19, 20]). In the present paper, we consider the opposite approach: in the above system, we consider the drip operation independent from the mate operation, as the drip operation can be executed regardless of the fact that the mate synchronization has been performed or not. The biological interpretation may be the following: the membrane proteins and the part of the lipid bilayer involved in the mate synchronization are different from the membrane proteins and the part of the bilayer that is performing the drip operation, and they lie in different parts of the membrane surface. Thus, we consider the following causal reactions: maten|drip(σ)(| |)◦mate⊥ n(| |)h;∅ −−→ h:: 0 |drip(σ)|h:: 0(| |)k;∅ −−→ h:: 0 |k:: 0 |h:: 0(| |) Note that the information on the causes of the empty process 0 is completely irrelevant, hence in the following we will replace H:: 0 with 0. 3.3 Causal dependencies generated by the mate operation Now we analyze the features peculiar of the MBD operations. According to the informal explanation above, a mate action turns out to be a cause for the continuations of the mate and the co-mate prefixes that synchronize to perform the operation. However, when considering the mate operation, a more subtle kind of causality, we call environment causality, is originated, e.g., between the mate action and the processes on the child membranes of the two membranes performing the mate and co-mate actions. This causality is due to the fact that the environment of such child membranes, i.e., the set of membranes with which they can interact, is increased by the execution of the mate action. Mate followed by mate Consider the following process: maten(|(matem|mateo)(| |)◦mate⊥ o(| |)|)◦ mate⊥ n(|mate⊥ m(| |)|) 104 N. Busi Now the mate synchronization on mcannot be performed, as the two membranes whose processes can synchronize on such an operation belong to different membranes. On the other hand, the mate synchronization on ocan take place, as both membranes whose processes can synchronize on such an operation belong to the same membrane. However, if the mate synchronization on ntakes place, the two external membranes are fused; this results in a change of the environment of the child membrane; now the mate on mcan take place, as the two child membranes now belong to the same father membrane and can get in contact. Hence, the mate on mcausally depends on the mate on n. To this aim, we decorate the processes of the child membranes of the external membrane performing a mate with label kin the following way: the child membranes on the left are decorated with the enriched label k+ i, whereas the child membrane on the right with the enriched complementary label k− i.2Note that we cannot simply decorate both groups of child membranes with label k, otherwise we are no longer able to distinguish between the synchronization on m, that is caused by k, and the synchronization on owhich has no causes. The enriched labels are used in the following way: when two processes preceded by enriched labels synchronize on a mate operation, the label kwill be a cause for such a synchronization if one process in decorated with an enriched label and the synchronizing process is decorated with the complementary label. We obtain the following causal reductions: maten(|(matem|mateo)(| |)◦mate⊥ o(| |)|)◦ mate⊥ n(|mate⊥ m(| |)|) h;∅ −−→ (0 |0)(|(h+ i:: matem|h+ i:: mateo)(| |)◦h+ i:: mate⊥ o(| |)◦ h− i:: mate⊥ m(| |)|) Now, if the mate on m is executed, then it will be caused by h, as the mate and comate processes are labeled with h+ iand h− i, respectively: (0 |0)(|(h+ i:: matem|h+ i:: mateo)(| |)◦h+ i:: mate⊥ o(| |)◦ h− i:: mate⊥ m(| |)|) k;h −−→ (0 |0)(|(0 |h+ i:: mateo)(| |)◦h+ i:: mate⊥ o(| |)◦ 0(| |)|) On the other hand, if the mate on ois executed, then it is not caused by hn, because the mate and comate processes are labeled with the same label h+ i. 2The iin the labels k+ iand k− istands for “internal”, and means that the action with label khas been performed by the father membrane. The need for such a label will be made clear in the following. Towards a Causal Semantics for Brane Calculi 105 Mate followed by bud A similar problem arises between the father and the child membrane when a bud operation is performed. Consider the following process: (maten|bud⊥ m(ρ1))(|budm(| |)◦budo(| |)|)◦ (mate⊥ n|bud⊥ o(ρ2))(| |) Now only the bud on mcan be performed, as the membrane performing the bud on ois not a child of the membrane performing the corresponding cobud. However, the bud on ocan be performed after the mate on nis performed, hence the bud causally depends on the mate. Thus, besides decorating the children of a membrane performing a mate (resp comate) with complementary labels k+ i(resp. k− i), we also decorate the subprocesses in parallel with the subprocess performing the mate (resp. the comate) with k+ e(resp. k− e)3. When a bud is performed, it is caused by kif the process performing the cobud on the father membrane is decorated, e.g., with k+ eand the process performing the bud on the child membrane is decorated with k− e. Note that, in case of a mate followed by a drip, the decorated causes will give rise to no causal dependency: the drip is caused by the mate only if the mate (or the comate) is a prefix of the drip. 3.4 Causal dependencies generated by the bud and the drip operations The bud (resp. drip) operation create a new membrane – whose membrane process is specified in the cobud (resp. drip) action – surrounding the child membrane that performs the synchronizing bud action (resp. with no children). As the new membrane does not exist before the bud (resp. drip) operation is performed, all the actions that such a membrane will perform are caused by the bud (resp. drip) operation. Consider the following system: bud⊥ n(drip(σ))(|budn(| |)|) This system can perform the following causal reactions: bud⊥ n(drip(σ))(|budn(| |)|)h;∅ −−→ 0(| |)◦h:: drip(σ)(|0(| |)|)k;h −−→ 0(| |)◦0(|0(| |)|)◦k:: σ(| |) We note that the bud operation generates no environmental cause. Regarding the child membranes, they are essentially divided into two sets, thus possibly preventing some mate (or bud) operation that was possible before to happen. On the other hand, the other processes in the father membrane are left unchanged. 3Here the emeans “external” 106 N. Busi 4 A causal semantics for MBD: the formal definition In this section we provide a formal definition of the notions introduced in the previous section. Definition 6. Let Kbe a denumerable set of cause names, disjoint from the set Names. Let Deco(K)be the set Deco(K) = K ∪ {ky x|k∈ K ∧ x∈ {i, e} ∧ y∈ {+,−}} The set of membrane processes with causes are defined by the following grammar: ˜σ, ˜τ::= 0 |˜σ|˜τ|!˜σ|K:: a.σ Variables a, b range over MBD actions specified in Definition 4, K⊆Deco(K), and a.σ is a sequential process as defined in Definition 1. The set of systems with causes is defined as in Definition 1, but using processes with causes instead of processes to decorate membranes. The set of causes preceding the process 0 is useless, hence it has been omitted. We omit the˜over processes if it is clear from the context that they are processes with causes. To define the causal semantics, we need an auxiliary operator on processes (and on systems) permitting to add a set of causes in front of each sequential subprocess of the process (resp. of the processes associated to the most external membranes of the system. Definition 7. Given K⊆Deco(K), the operator KZ⇒is inductively defined on processes with causes as follows: KZ⇒0=0 KZ⇒(σ|τ) = KZ⇒σ|KZ⇒τ KZ⇒!σ= !KZ⇒σ KZ⇒H:: a.σ =H∪K:: a.σ The operator KZ⇒is inductively defined on systems as follows: KZ⇒  = KZ⇒(P◦Q) = KZ⇒P◦KZ⇒Q KZ⇒(!P)=!KZ⇒P KZ⇒(σ(|P|)) = (KZ⇒σ)(|P|) If the set Kis a singleton, often we omit the surrounding parenthesis in the operator KZ⇒; thus we write, e.g., kZ⇒Pinstead of {k}Z⇒P. Now we are ready to define the causal semantics for MBD. We write Pk;H −−→ P0 to denote the fact that system Pperforms an action – to which we associate the cause name k– that is caused by the (previously occurred) actions whose action Towards a Causal Semantics for Brane Calculi 107 names form the set H. The cause name kis a fresh name: this means that it does not occur in Pand that it has not used yet in the current computation. The structural congruence relation is the that in Definition 2. The causal rules are obtained by decorating the rules in Definition 3 with the causal information. Definition 8. The causal reaction rules are the following: (par)Pk;H −−→ Q P◦Rk;H −−→ Q◦R (brane)Pk;H −−→ Q σ(|P|)k;H −−→ σ(|Q|) (strucong)P0≡P P k;H −−→ Q Q ≡Q0 P0k;H −−→ Q0 Now we are ready to define the causal reaction relation for MBD. Definition 9. The causal reaction relation for MBD is the least relation containing the following axioms, and satisfying the rules in Definition 8: (kmate) (H1:: maten.σ)|σ0(|P|)◦(H2:: mate⊥ n.τ)|τ0(|Q|)k;H1⊕mH2 −−−−−−−→ ((k∪H1mH2)Z⇒σ|k+ eZ⇒σ0| (k∪H2mH1)Z⇒τ|k− eZ⇒τ0) (|k+ iZ⇒(P)◦k− iZ⇒(Q)|) (kbud) (H1:: bud⊥ n(ρ).τ)|τ0(|(H2:: budn.σ)|σ0(|P|)◦Q|)k;H1⊕bH2 −−−−−−−→ (k∪H1bH2) :: ρ(|((k∪H2bH1)Z⇒σ)|σ0(|P|)|)◦ ((k∪H1mH2)Z⇒τ)|τ0(|Q|) (kdrip) (H:: drip(ρ).σ|σ0)(|P|)k;fd(H) −−−−−→ k∪f0 d(H)Z⇒ρ(| |)◦(k0∪f00 d(H)Z⇒σ)|σ0(|P|) The auxiliary functions are defined as follows: H1⊕mH2={k|k∈(H1∪H2)∩ K}∪ {k| {k+ i, k− i} ⊆ (H1∪H2)} H1mH2={ky x∈H1|k6∈ (H1⊕mH2)} H1⊕bH2={k|k∈(H1∪H2)∩ K}∪ {k|kx e∈H1∧ky e∈H2∧x6=y} H1bH2={ky i∈H1|k6∈ (H1⊕bH2)} H1bH2={ky x∈H1|k6∈ (H1⊕bH2)} fd(H) = {k|k∈H∩ K} f0 d(H) = {kx i|kx i∈H∧x∈ {+,−}} f00 d(H) = {kx y|kx y∈H∧x∈ {+,−} ∧ y∈ {i, e}} 108 N. Busi The auxiliary functions describe the way in which the (decorated) causes propagate when a reduction is performed. In the merge operation, the set of causes of the merge action, denoted by H1⊕mH2, contains both the causes of the mate and the comate operation, as well as those causes hsuch that h+ idecorates one of the merging membranes and h− idecorates the other (this means that the two membranes have become sibling membranes by the execution of a mate operation with label h). The external decorated causes are not taken into account because they are concerned with bud operations between a father and a child membrane, and not with sibling membranes. To avoid redundancy, the set of causes H1H2of the continuation of the mate action is obtained by removing the decorated causes whose name appears as a cause of the current mate synchronization (and analogously for comate, bud and cobud actions). In the bud operation, the set of causes of the bud actions, denoted by H1⊕bH2, contains both the causes of the bud and the cobud operation, as well as those causes hsuch that, e.g., h+ edecorates the father membrane and h− idecorates the child membrane. The set of causes of the newly created membrane is denoted by H1H2, and contains only internal causes; they are needed because in the system maten(|bud⊥ o(matem)(|budo(| |)|)|)◦mate⊥ n(|mate⊥ m|) the mate synchronization on mcan happen only if the mate synchronization on n has been performed. Regarding the drip operation, here there is no synchronization; hence, the set of causes labeling the reduction relation, represented by fd(H) is exactly the set of nondecorated causes. The newly created membrane is decorated with function f0 d(H) containing only internal causes; they are needed because in the system maten(|drip(matem)(| |)|)◦mate⊥ n(|mate⊥ m|) the mate synchronization on mcan happen only if the mate synchronization on n has been performed. The external causes are not needed because they are used for bud synchronization between father and child, and the newly created membrane has no child taken from the old membrane. 4.1 Properties of the causal semantics The only interesting property enjoyed by the causal semantics is the retrievability of the interleaving semantics. We start defining the function DropCause which removes the causes from processes and systems. Definition 10. The function DropCause is defined inductively on processes with causes in the following way: DropCause(0) = 0 DropCause(˜σ|˜τ) = DropCause(˜σ)|DropCause(˜τ) DropCause(!˜σ)=!DropCause(˜σ) DropCause(K:: a.σ) = a.σ Towards a Causal Semantics for Brane Calculi 109 The function DropCause is defined inductively on systems with causes in the following way: DropCause() =  DropCause(P◦Q) = DropCause(P)◦DropCause(Q) DropCause(!P)=!DropCause(P) DropCause(˜σ(|P|)) = DropCause(˜σ)(|DropCause(P)|) Theorem 1. Let Pbe a system with causes. The following properties hold: •if Pk;H −−→ P0then DropCause(P)→DropCause(P0); •if DropCause(P)→Qthen there exist a system with causes P0, a cause name kand a set of cause names Hsuch that Pk;H −−→ P0and Q=DropCause(P0). The so-called diamond property, stating that if two non-causally related actions can happen one after the other, then they can happen also in the other order, and at the end they reach the same system, does not hold. In our setting, the diamond property can be formally defined as follows: given a system P, if Ph;H −−→ P0k;K −−→ P00 and h6∈ K, then there exists a system qsuch that Pk;K −−→ Qh;H −−→ P00. Consider e.g. the following system: bud⊥ m(0)(|maten(| |)◦(budm|mate⊥ n)(| |)|) This system can perform the mate action, followed by the bud action. Moreover, the two actions are independent, i.e., causally unrelated. However, if we first perform the bud action, then the submembrane mate⊥ n)(| |) is isolated from the other submembrane, and the merge can no longer take place. However, there is no reason to consider the bud action as causally dependent on the mate action, as the bud action can actually independently occur at the beginning of the computation. Nevertheless, there is a form of asymmetric conflict between the two actions: the occurrence of the bud action prevents the mate action to happen, but the vice versa does not hold. A similar phenomenon takes place, e.g., in Petri nets with read and inhibitor arcs (see [4] for a discussion on this topic). A possible way to capture this kind of asymmetric conflict is based on the following idea: if a mate synchronization with causal label kis performed, we decorate the process of the father membrane of the two membrane that are fusing with a label, say kf(where the fstands for “father”). When the bud operation is performed, the cobud prefix is decorated with kf, whereas the bud prefix is decorate with k− e. As a but synchronization is performed in this situation, we get the information that – even if the bud does not causally depend from the mate – the bud synchronization cannot be swapped with the mate. Even if there is no asymmetric conflict, there are situations where the diamond property does not hold. Even if the two actions can be performed in either order, the final states that are reached are different. Take the system bud⊥ n(0).σ(|(budn.τ |drip(ρ))(| |)|) 110 N. Busi If the bud action is performed first, then the membrane with process ρwill be dripped inside the newly created membrane, labeled with process 0. On the other hand, if the drip is performed first then the membrane with process ρremains inside the older membrane (with process bud⊥ n(0).σ or with the continuation σ. 5 Conclusion In this paper we tackled the problem of defining a causal semantics for an instance of Brane Calculi, namely, the MBD calculus. As already pointed out in [14], we think that the study of the causal dependencies that arise between the actions performed by a process is of primary importance for biologically inspired calculi, because of its possible application to the analysis of complex biological pathways. This paper represents a first step in this direction, but a lot of work remains to be done. The next step is the study of the causal semantics for the PEP calculus, and its integration with the causal semantics for MBD. Then, we will move to the full Brane Calculus, that, besides the membrane-membrane interaction primitives of PEP and MBD, also contains objects representing free-floating molecules, and primitives for molecule-molecule and membrane-molecule interactions. When the definition of a causal semantics has been completed, we will start investigating the causal dependencies arising in biological pathways involving membranes, such as, e.g., the LDL Cholesterol Degradation Pathway [16], that has been modeled in the full Brane Calculus in [5]. We also plan to perform a thorough investigation of the properties that are enjoyed by the causal semantics, and possibly to refine the definition of the causal semantics in order to fulfill some of the properties. For example, a possible solution in order to obtain a causal semantics that partially enjoys the diamond property has been sketched in the previous section, and deserves further investigation. We also plan to extend our investigation to other calculi/systems whose membranes are organized in a dynamically evolving hierarchical structure, such as, e.g., the Projective Brane Calculus [13] or Membrane Systems with active, evolving membranes. References 1. M. Boreale, D. Sangiorgi: A fully abstract semantics for causality in the π-Cclculus. Acta Informatica, 35, 5 (1998), 353–400. An extended abstract appeared in Proc. STACS 1995, 243–254. 2. N. Busi: On the computational power of the Mate/Bud/Drip Brane Calculus: interleaving vs. maximal parallelism. In Proc 6th International Workshop on Membrane Computing (WMC6), LNCS 3850, Springer, 2006. 3. N. Busi, R. Gorrieri: A Petri net semantics for π-calculus. In Proc. Concur’95, LNCS 962, Springer, 1995, 145–159. Towards a Causal Semantics for Brane Calculi 111 4. N. Busi, G.M. Pinna: Comparing truly concurrent semantics for contextual place/transition nets with inhibitor and read arcs. Fundam. Inform., 44, 3 (2000), 209–244. 5. N. Busi, C. Zandron: Modeling and analysis of biological processes by mem(brane) calculi and systems. In Proceedings of the Winter Simulation Conference (WSC 2006), ACM, 2006. 6. L. Cardelli: Brane Calculi - Interactions of biological membranes. In Proc. Computational Methods in System Biology 2004 (CMSB 2004), LNCS 3082, Springer, 2005. 7. L. Cardelli: Abstract Machines for System Biology. Draft, 2005. 8. L. Cardelli, A.D. Gordon: Mobile ambients. Theoretical Computer Science, 240, 1 (2000), 177–213. 9. Ph. Darondeau, P. Degano: Causal trees. In Proc. ICALP’89, LNCS 372, Springer, 1989, 234–248. 10. P. Degano, R. De Nicola, U. Montanari: Partial ordering descriptions and observations of nondeterministic concurrent processes. In Proc. REX School/Workshop on Linear Time, Branching Time and Partial Order in Logic and Models of Concurrency, LNCS 354, Springer, 1989, 438–466. 11. P. Degano, C. Priami: Causality for mobile processes. In Proc. ICALP’95, LNCS 944, Springer, 1995, 660–671. 12. P. Degano, C. Priami: Non interleaving semantics for mobile processes. Theoretical Computer Science, 216, 1-2 (1999), 237–270. 13. V. Danos, S. Pradalier: Projective brane calculus. In Proc. Computational Methods in System Biology 2004 (CMSB 2004), LNCS 3082, Springer, 2005. 14. M.L. Guerriero, C. Priami: Causality and Concurrency in Beta-binders. TR-01-2006 The Microsoft Research - University of Trento Centre for Computational and Systems Biology, 2006. 15. A. Kiehn: Proof systems for cause based equivalences. In Proc. MFCS’93, LNCS 711, Springer, 1993. 16. H. Lodish, A. Berk, P. Matsudaira, C.A. Kaiser, M. Krieger, M.P. Scott, S.L. Zipursky, J. Darnell: Molecular Cell Biology. W.H. Freeman and Company, 4th edition, 1999. 17. R. Milner: Communication and Concurrency. Prentice-Hall, 1989. 18. R. Milner, J. Parrow, D. Walker: A calculus of mobile processes. Information and Computation, 100 (1992), 1–77. 19. G. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 20. G. P˘aun: Membrane Computing. An Introduction. Springer, 2002. 21. C. Priami, P. Quaglia: Beta binders for biological interactions. In Proc. of Computational Methods in Systems Biology, LNCS 3082, Springer, 2005, 20–33. 22. C. Priami, P. Quaglia: Operational patterns in beta-binders. T. Comp. Sys. Biology, 1 (2005), 50–65. 23. A. Regev, E. M. Panina, W. Silverman, L. Cardelli, E. Shapiro: BioAmbients: An abstraction for biological compartments. Theoretical Computer Science, 325, 1 (2004), 141–167. 118 D. D´ıaz-Pernil et al. Theorem 1. Subset Sum ∈PMCT D. Proof. Let A={a1, . . . , an}be a finite set, w:A→Na weight function, and k∈N. Let g:N×N→Nbe a function defined by g(n, k) = (n+k)(n+k+ 1) 2+n This function is primitive recursive and bijective between N×Nand Nand computable in polynomial time. Let us denote by u= (n, (w1, . . . , wn), k), where wi=w(ai), 1 ≤i≤n, the given instance of the problem. We define the polynomially computable function s(u) = g(n, k). We shall provide a family of tissue P systems where each P system solves all the instances of the Subset Sum problem with the same size. The weight function wof the concrete instance will be provided via an input multiset determined via the function cod(u) = {{vwi i: 1 ≤i≤n}} ∪ {{qk}}. Next, we shall provide a family Π={Π(g(n, k)) : n, k ∈N}of recognizing tissue P systems with cell division which solve the Subset Sum problem in a linear time. For each (n, k)∈N×Nwe shall consider the system Π(g(n, k)) = (Γ, Σ, ω1, ω2,R,E, iin, i0), where •Γ=Σ(n)∪ {Ai, Bi: 1 ≤i≤n} ∪ {zi: 1 ≤i≤n+dlog ne+dlog(k+ 1)e+ 11} ∪ {ci: 1 ≤i≤n+ 1} ∪ {di: 1 ≤i≤ dlog ne+dlog(k+ 1)e+ 4} ∪ {ei: 1 ≤i≤ dlog ne+ 1} ∪ {Bij : 1 ≤i≤n∧1≤j≤ dlog(k+ 1)e+ 1} ∪ {b, f1, g1, g2, p, D, T, S, N, yes,no} •Σ={q}∪{vi: 1 ≤i≤n} •ω1=z1b c1yes no •ω2=DA1· · · An • R is the following set of rules: 1. Division rules: r1,i ≡[Ai]2→[Bi]2[λ]2for i= 1, . . . , n 2. Communication rules: r2,i ≡(1, zi/zi+1,0) for i= 1, . . . , n +dlog ne+dlog(k+ 1)e+ 10 r3,i ≡(1, ci/c2 i+1,0) for i= 1, . . . , n r4≡(1, cn+1/D, 2) r5≡(2, cn+1/d1e1,0) r6,i ≡(2, ei/e2 i+1,0) for i= 1, . . . , dlog ne r7,i ≡(2, di/di+1,0) for i= 1, . . . , dlog ne+dlog(k+ 1)e+ 3 r8,i ≡(2, edlog ne+1Bi/Bi1,0) for i= 1, . . . , n r9,i,j ≡(2, Bij/B2 ij+1,0) for i= 1, . . . , n,j= 1, . . . , dlog(k+ 1)e r10,i ≡(2, Bidlog(k+1)e+1vi/p, 0) for i= 1, . . . , n r11 ≡(2, pq/λ, 0) r12 ≡(2, ddlog ne+dlog(k+1)e+4/g1f1,0) Subset Sum with Tissue P Systems with Cell Division 119 r13 ≡(2, f1p/λ, 0) r14 ≡(2, f1q/λ, 0) r15 ≡(2, g1/g2,0) r16 ≡(2, g2f1/T, 0) r17 ≡(2, T/λ, 1) r18 ≡(1, bT/S, 0) r19 ≡(1, Syes/λ, 0) r20 ≡(1, zn+dlog ne+dlog(k+1)e+11b/N, 0) r21 ≡(1, Nno/λ, 0) • E =Γ− {yes,no} •iin = 2, is the input cell •i0=env, is the output cell The design is structured in the following stages: •Generation Stage: The initial cell labelled by 2 is divided into two new cells; and the divisions are iterated ntimes until a cell has been produced for each possible candidate solution. Simultaneously to this process, two counters (ci and zi) evolve in the cell labelled by 1: the first one controls the step in which the communication between cells 2 and cell 1 starts and the second one will be useful in the output stage. •Pre–checking Stage: When this stage starts, we have 2ncells labelled by 2, each of them encoding a subset of the set A. In each such a cell, as many objects pas the weight of the corresponding subset will be produced. Recall that there are kcopies of the object qin every cell labelled by 2 (since they were introduced as part of the input multiset). •Checking Stage: In each cell labelled by 2, the number of copies of objects p and qare compared. The way to do that is removing from the cell in one step all possible pairs (p, q). After doing so, if some objects por qremain in the cell, then the cell was not encoding a solution of the problem; otherwise, the weight of the subset of Aencoded on the cell equals to kand hence it encodes a solution to the problem. •Output Stage: The system sends to the environment the right answer according to the results of the previous stage: –Answer yes: After the checking stage, there is a cell labelled by 2 without objects pnor q. In this case, such a cell sends an object Tto the cell 1. This object Tcauses the cell 1 to expel an object yes to the environment (see rules r17 –r19). –Answer no: Every cell labelled by 2 contains some objects por q. In this case, no object Tarrives to the cell labelled by 1 and an object no is sent to the environment. The proof will be concluded in Subsection 5.2. Before going on, let us informally present an overview of the computation. 120 D. D´ıaz-Pernil et al. 5.1 An overview of the computation First of all, we recall the polynomial encoding of the Subset Sum problem in the family Πconstructed above. Let u= (n, (w1, . . . , wn), k) be an instance of the problem, s(u) = g(n, k) and cod(u) = {{vwi i: 1 ≤i≤n}} ∪ {{qk}}. Next, we describe informally how the recognizing tissue P system with cell division Π(s(u)) with input cod(u) works. Let us start with the generation stage. Recall that if a division rule is triggered in a cell, then communication rules cannot be simultaneously applied to the contents of such cell. In this stage we have two parallel processes: •On the one hand, in the cell labelled by 1 we have two counters: zi, which will be used in the answer stage, and ci, which will be multiplied until getting 2n copies in exactly nsteps. •On the other hand, in the cells labelled by 2, the division rules are applied. For each object Ai(which codifies a member of the set A) we obtain two cells labelled by 2: one of them has an element Biand the other does not. When all divisions have been done, after nsteps, we shall have 2ncells with label 2 and each of them will contain the encoding of a subset of A. At this moment, the generation stage ends and the pre-checking stage begins. For each cell 2, an object Dis changed by a copy of the counter ci. In this way, 2ncopies of Dwill appear in the cell 1, and in each cell labelled by 2 there will be an object cn+1. The occurrence of such object cn+1 in the cells 2 will produce the apparition of two counters: (a) The counter dilets the checking stage start, since it produces the apparition of the objects g1and f1after dlog ne+dlog(k+ 1)e+ 4 steps. (b) The counter eiwill be multiplied until obtaining 2dlog necopies, ensuring that at least ncopies of edlog ne+1 will be available in the step n+dlog ne+ 2. Then, we trade objects edlog ne+1 and Biagainst Bi1for each element Aiin the subset associated with the cell. After that, for each 1 ≤i≤nwe get 2dlog(k+1)ecopies of Bidlog(k+1)e+1, ensuring that at least k+ 1 copies will be available. Then for each element Ai in the subset associated with the cell we get min{2dlog(k+1)e, w(ai)}copies of object p, in the step n+dlog ne+dlog(k+ 1)e+ 5. The checking takes place in the step n+dlog ne+dlog(k+1)e+6, when all pairs of objects pand qpresent in any cell labelled by 2 are sent to the environment. In this way, if the weight of the subset associated with a cell is equal to k, then no object por qremains in this cell in the next step. Otherwise, if the encoding is not exactly of weight k, then at least one object por qwill remain in the cell. In the next step the answer stage starts. Two cases must be considered for each cell: •If no object por qremain in the cell, the object f1does not evolve, g1evolves to g2, and in the step n+dlog ne+dlog(k+ 1)e+ 8 the objects f1and g2are traded against Tfrom the environment. In the next step Tis sent to the cell 1, Subset Sum with Tissue P Systems with Cell Division 121 and in the step n+dlog ne+dlog(k+ 1)e+ 10, the objects Tand bare sent to the environment traded by S. Finally, in the step n+dlog ne+dlog(k+1)e+11 the objects Sand yes are sent to the environment. •If any object por qremains in the cell, such object is sent to the environment together with the object f1. This causes that the object bstill remains in the cell 2 after the step n+dlog ne+dlog(k+ 1)e+ 10. In this way, the objects b and zn+dlog ne+dlog(k+1)e+11 are traded by the object Nwith the environment, and in the step n+dlog ne+dlog(k+ 1)e+ 12 the objects Nand no are sent to the environment. 5.2 Verification Next, we prove that the family of recognizing tissue P systems with cell division described above solves the Subset Sum problem in a linear time, according to Definition 1. Before going on, let us remark that the defined family is consistent, i.e., all systems of the family are recognizing tissue P systems with cell division. By construction (type of rules and working alphabet) we can check that it is a family of tissue P systems with cell division. Moreover, we shall prove next that all computations of all systems in the family always halt and in the last step of computations either an object yes or no is sent to the environment. Polynomial uniformity of the family Next, we show that the family Π={Π(g(n, k)) : n, k ∈N}defined in Theorem 1 is polynomially uniform by Turing machines. To this aim we are going to show that it is possible to build Π(g(n, k)) in polynomial time with respect to the size of u. It is easy to check that the rules of a system Π(g(n, k)), with n, k ∈Nof the family are defined recursively from the values nand k. Besides, the necessary resources to build an element of the family are of polynomial order with respect to the same: •Size of the alphabet: (n+ 2) · dlog(k+ 1)e+ 6n+ 3dlog ne+ 28 ∈O(n·log k) •Initial number of cells: 2 ∈θ(1). •Initial number of objects: n+ 6 ∈θ(n). •Number of rules: (n+ 2) · dlog(k+ 1)e+ 5n+ 3dlog ne+ 26 ∈O(n·log k) •Maximal length of a rule: 3 ∈θ(1). Therefore, a deterministic Turing machine can build Π(g(n, k)) in a polynomial time with respect to nand k. Notice that every instance u= (n, (w1, . . . , wn), k) is introduced in the initial configuration of its associated cellular system via an input multiset (i.e. an 1-ary representation) and hence, |u| ∈ O(n+k) holds. 122 D. D´ıaz-Pernil et al. We would like to recall that the functions cod and shave been defined above for an instance u= (n, (w1, . . . , wn), k) of the Subset Sum problem as follows: cod(u) = {{vwi i: 1 ≤i≤n}} ∪ {{qk}}, and s(u) = g(n, k), respectively. Both functions are computable in polynomial time and the pair (cod, s) is a polynomial encoding of ISubsetSum in Π, since for each instance uof the Subset Sum problem we have that cod(u) is an input multiset of the system Π(s(u)). In order to settle the formal verification of the family of tissue P systems we shall prove that all the systems of the family are polynomially bounded, and also that they are sound and complete with respect to (SubsetSum, cod, s). Polynomial boundness of the family In order to ensure that the system Π(s(u)) with input cod(u) is polynomially (indeed, linearly) bounded, it suffices to find the moment in which the computation halts, or at least, an upper bound for it. As we shall show, the number of steps of the computations of any system of the family can always be bounded by a linear function. Nonetheless, we would like to stress that the amount of pre-computed resources for each instance uis polynomial in the size of the instance, since cod(u) needs to be computed and Π(s(u)) needs to be built. Proposition 1. The family Π={Π(g(n, k)) : n, k ∈N}is polynomially bounded with respect to (SubsetSum, cod, s). Proof. (Sketch). We shall informally go through the stages of the computation in order to estimate a bound for the number of steps. The computation will be studied in more detail when addressing the soundness and completeness proof. Let u= (n, (w1, . . . , wn), k) be an instance of the Subset Sum problem. We shall study what happens during the computation of the system Π(s(u)) with input cod(u) which processes such instance in order to find the halting step, or at least, an upper bound for it. First, the generation stage lasts exactly nsteps, where all the divisions of the cells of the system are performed. After that, the pre-checking stage starts with the rule r4. In the following step the object d1arrives to all cells 2 and the counter distarts. At the step n+dlog ne+dlog(k+ 1)e+ 5, the last element of the counter diis reached and the checking stage ends. In this way, in the (n+dlog ne+dlog(k+ 1)e+ 6)-th step of the computation the checking takes place. Recall that only one step is needed for the checking, as rule r11 takes out in parallel all pairs (p, q) from all cells 2. The last one is the answer stage. The longest case is obtained when the answer is negative. In this case there is one step where only the counter ziis working since no element Thas reached the cell 1. In the next step an object Nis brought from the environment and, finally, in the (n+dlog ne+dlog(k+ 1)e+ 12)-th step, the object no is sent to the environment. Therefore, there exists a linear bound with respect to (n+log k) on the number of steps of the computation. Subset Sum with Tissue P Systems with Cell Division 123 Soundness and Completeness of the family In order to prove the soundness and completeness of the family Πwith respect to (SubsetSum, cod, s), we shall prove that given an instance uof the Subset Sum problem, the system Π(s(u)) with input cod(u) sends out an object yes if and only if the answer to the problem for the considered instance uis affirmative, and the object no is sent out otherwise. Proposition 2. The family Π={Π(g(n, k)) : n, k ∈N}is sound and complete with respect to (SubsetSum, cod, s). Proof. In order to complete the proof we shall proceed through a number of auxiliary results. Remark 1. Given a computation Cwe denote the configuration at the i-th step as Ci. Moreover, Ci(1) will denote the multiset associated to cell 1 in such configuration. We start with the generation stage (i.e., the nfirst steps of the computation). It consists of two parallel processes, each of them in one cell. Lemma 1. If Cis an arbitrary computation of the system, then for all jsuch that 0≤j≤n,Cj(1) = {{zj+1, c2j j+1, b, yes,no}} holds. Proof. We shall reason by induction on j. Base Case. We have C0(1) = {z1, c1, b, yes,no}, and thus the lemma holds for j= 0. Case j < n →j+ 1.Let jbe such that 1 ≤j < n and we have, by inductive hypothesis, Cj(1) = {{zj+1, c2j j+1, b, yes,no}}. In this configuration, only the rules r3,j+1 and r4,j+1 can be applied to cell 1, and therefore Cj+1(1) = {{zj+2, c2(j+1) j+2 , b, yes,no}}. Lemma 2. If Cis an arbitrary computation of the system, then: 1. For each subset V⊆ {1, . . . , n}there exists only one cell 2in Cnwhose multiset is cod(u)∪ {{D}} ∪ {{Bi:i∈V}} 2. There exist exactly 2ncells labelled by 2in configuration Cn Proof. It is clear that division rules cannot be applied in parallel over the same cell. At this point there is an intrinsic non-determinism of the system. We have to apply all the division rules, but the order is non-deterministically chosen. At time 0, there are ndivision rules that can be applied. When we apply one of them to the cell labelled by 2, for example, r1,i (1 ≤i≤n) we eliminate the object Aiand will obtain two new cells, in the first one an object Biwill appear, but not in the second one. The remaining contents of the original cell will be in the two new cells as well. In the following step, another division rule can be applied to the two cells labelled by 2. As described above, the object Ajthat triggers the rule disappears, 124 D. D´ıaz-Pernil et al. and a new object Bjappear in one of the new cells (note that the two cells may chose different objects Aj). This process is repeated in all cells 2 for each division rule. It is clear that by triggering a division rule r1,j we get two different cells. Only one of them containing Bj. On the other hand, each object Aiappears exactly once in their initial configuration. Therefore, after applying ndivision rules we obtain 2ncells labelled by 2. Moreover, let Vbe a subset of {1, . . . , n}, if for each division rule [Ai]2→ [Bi]2[λ]2we focus on the cell containing Bionly for i∈V(we select the other cell otherwise), then after ndivision steps we will have a cell labelled by 2 such that Bjbelongs to the cell if and only if j∈V, irrespectively of the order in which the division rules are applied. Lemma 3. If Cis an arbitrary computation of the system, then for all isuch that 1≤i≤ dlog ne+dlog(k+ 1)e+ 7,Cn+i(1) = {{zn+i+1, D2n, b, yes,no}} holds Proof. In order to prove the lemma it suffices to observe the following: • Cn(1) = {{zn+1, c2n n+1, b, yes,no}} holds from Lemma 1. •There exist exactly 2ncells labelled by 2 in configuration Cn, each of them containing an object D(this follows from Lemma 2). •In the next step of the computation, only rules r4and r2,n+1 are applicable on cell 1, yielding Cn+1(1) = {{zn+1+1, D2n, b, yes,no}} •During the rest of the checking stage, only rules of type r2,i are applicable on cell 1, and the result follows. Lemma 4. Let Cbe an arbitrary computation of the system. Then: •For each subset V⊆ {1, . . . , n}there exists only one cell 2in Cn+1 whose associated multiset is cod(u)∪ {{cn+1}} ∪ {{Bi:i∈V}} •There exist exactly 2ncells labelled by 2in configurations Cn+i, for 1≤i≤ dlog ne+dlog(k+ 1)e+ 12 Proof. Cn+1 is obtained from Cnby the application of the rules r4and r2,n+1 and hence, 2nobjects cn+1 in the cell 1 are traded against 2nobjects Dfrom the cells 2 (one from each cell). Then Cn+1(1) = {{zn+2, D2n, b, yes,no}} and for every V⊆ {1, . . . , n}there exists only one cell 2 whose associated multiset is cod(u)∪ {{cn+1}} ∪ {{Bi:i∈V}} Since no division rule has been applied in this step (actually, they will not be applied anymore along the computation), the number of cells 2 remains the same as in the previous configuration. Lemma 5. Let Cbe an arbitrary computation of the system. For each i(1 ≤i≤ dlog ne+ 1) and for each V⊆ {1, . . . , n}there exists only one cell 2in Cn+i+1 whose associated multiset is cod(u)∪ {{di, e2(i−1) i}} ∪ {{Bj:j∈V}} Subset Sum with Tissue P Systems with Cell Division 125 Proof. We shall reason by induction on i. Case i= 1. It suffices to note that r5is the only rule that can be applied on cells 2 in configuration Cn+1, and the result follows from the previous Lemma. Case 1≤i < dlog ne+ 1 →i+ 1. Let ibe such that 1 ≤i < dlog ne+1 and let us suppose that the result holds for i. Let Vbe an arbitrary subset of {1, . . . , n}, then let us consider its associated cell whose contents are indicated by inductive hypothesis. The only rules applicable to this cell are r6,i and r7,i, and therefore the multiset of such cell 2 in Cn+i+2 will be cod(u)∪ {{di+1, e2i i+1}} ∪ {{Bj:j∈V}}, as we wanted to prove. Lemma 6. Let Cbe an arbitrary computation of the system. For each l(1 ≤l≤ dlog(k+ 1)e+ 2) and for each V⊆ {1, . . . , n}there exists only one cell 2in Cn+dlog ne+l+2 whose associated multiset is cod(u)∪ {{ddlog ne+l+1, e(2dlog ne−|V|) dlog ne+1 }} ∪ {{B2(l−1) jl :j∈V}} Proof. We shall reason by induction on l. Case l= 1. Let Vbe an arbitrary subset of {1, . . . , n}, then from the previous Lemma it follows that there exists a cell whose associated multiset in Cn+dlog ne+2 is cod(u)∪ {{ddlog ne+1, e2dlog ne dlog ne+1}} ∪ {{Bj:j∈V}}. The next configuration for this cell is obtained by applying rules r7,dlog ne+1 and r8,j for every j∈V: •r7,dlog ne+1 allows the evolution of the counter dto ddlog ne+2 in each cell 2. •Each r8,j allows the replacement of the objects Bj(together with a copy of edlog ne+1) by Bj1. and thus the result holds for l= 1. Case 1≤l < dlog(k+ 1)e → l+ 1. Let lbe such that 1 ≤l < dlog ne+ 1 and let us suppose that the result holds for l. That is, there exists only one cell 2 in Cn+dlog ne+l+3 with the multiset cod(u)∪ {{ddlog ne+l+1, e2dlog ne−|V| dlog ne+1 }} ∪ {{B2(l−1) jl :j∈V}} In the next step, rules r7,n+dlog ne+l+3 and r9,j,l, for every j∈V, will be applied on this cell, and thus the multiset of such cell 2 in Cn+dlog ne+l+1+3 will be cod(u)∪ {{ddlog ne+l+2, e2dlog ne−|V| dlog ne+1 }} ∪ {{B2l j(l+1) :j∈V}} Lemma 7. Let Cbe an arbitrary computation of the system. For each V⊆ {1, . . . , n}there exists only one cell 2in Cn+dlog ne+dlog(k+1)e+5 whose associated multiset is {{pPj∈Vwj, qk}}∪{{ddlog ne+dlog(k+1)e+4, e2dlog ne−|V| dlog ne+1 }}∪{{B2dlog(k+1)e−wj j(dlog(k+1)e+1) :j∈V}} 126 D. D´ıaz-Pernil et al. Proof. Let Vbe an arbitrary subset of {1, . . . , n}. From the previous Lemma (taking l=dlog(k+1)e+2), it follows that in Cn+dlog ne+dlog(k+1)e+4 there is a cell 2 associated with this subset whose content is indicated above. In the next step, the following rules are applied: •r7,dlog ne+dlog(k+1)e+3 allows the evolution of the counter ddlog ne+dlog(k+1)e+4. •r10,j, for every j∈V, allow the replacement of all the existing objects vj (recall that there are w(aj) copies of vjin cod(u)), together with objects Bj(dlog(k+1)e+1) against Pj∈Vwjobjects p. Remark 2. From this moment on, for the sake of simplicity, given V⊆ {1, . . . , n} we shall note by wV=Pj∈Vwj, and we shall also note by trashVthe following multiset: {{e2dlog ne−|V| dlog ne+1 }} ∪ {{B2dlog(k+1)e−wj j(dlog(k+1)e+1) :j∈V}} Lemma 8. Let Cbe an arbitrary computation of the system and let V⊆ {1, . . . , n}. We have the following: •If k=wVthen there exists only one cell 2in Cn+dlog ne+dlog(k+1)e+6 whose associated multiset is {{f1, g1}} ∪ trashV •If k < wVthen there exists only one cell 2in Cn+dlog ne+dlog(k+1)e+6 whose associated multiset is {{pwV−k, f1, g1}} ∪ trashV •If k > wVthen there exists only one cell 2in Cn+dlog ne+dlog(k+1)e+6 whose associated multiset is {{qk−wV, f1, g1}} ∪ trashV Proof. Let Vbe an arbitrary subset of {1, . . . , n}. From the previous Lemma, it follows that in Cn+dlog ne+dlog(k+1)e+5 there is a cell 2 associated with this subset whose content is indicated above. In the next step, the following rules are applied: •r11 sends all existing pairs (p, q) to the environment. So, if k=wVthen all objects pand qwill disappear of the cell. However, if k < wVthen wV−k objects pwill remain in the cell, and conversely if k > wVthen k−wVobjects qwill remain in the cell. •r12 trades the object ddlog ne+dlog(k+1)e+4 against the objects f1, g1. Lemma 9. Let Cbe an arbitrary computation of the system, and let Vbe a subset of {1, . . . , n}. 1. For each Vsuch that wV=k, there exists one cell 2such that: a) its associated multiset in Cn+dlog ne+dlog(k+1)e+7 is {{f1, g2}} ∪ trashV b) its associated multiset in Cn+dlog ne+dlog(k+1)e+8 is {{T}} ∪ trashV Subset Sum with Tissue P Systems with Cell Division 127 c) For each i(1 ≤i≤4), its associated multiset in Cn+dlog ne+dlog(k+1)e+i+8 is trashV 2. For each Vsuch that wV6=k, there exists one cell 2such that for each i(1 ≤ i≤6) its associated multiset in Cn+dlog ne+dlog(k+1)e+i+6 is {{g2, pwV−k−1}} ∪ trashVor {{g2, qk−wV−1}} ∪ trashV Proof. 1. From the previous Lemma, if k=wVthen there exists only one cell 2 in Cn+dlog ne+dlog(k+1)e+6 whose associated multiset is {{f1, g1}} ∪ trashV Then, by applying the rule r15 (no other rule can be applied in this cell) we obtain in the next step {{f1, g2}} ∪ trashV. After that, by applying the rule r16 we obtain {{T}} ∪ trashV. Finally, by applying the rule r17 the element Tis sent to the cell labelled by 1. No more rules can be applied after this moment in the cells labelled by 2. Therefore, for 1 ≤i≤4, the contents of the cell in Cn+dlog ne+dlog(k+1)e+i+8 is the multiset trashV. 2. From the previous Lemma, if k < wVthen there exists only one cell 2 in Cn+dlog ne+dlog(k+1)e+6 whose associated multiset is {{pwV−k, f1, g1}} ∪ trashV Then, by applying the rule r13 an object pis sent to the environment together with object f1. In parallel, rule r15 trades g1against g2. No more rules can be applied in the cell after this moment. Therefore, for 1 ≤i≤5, the contents of the cell in Cn+dlog ne+dlog(k+1)e+i+7 is the multiset {{g2, pwV−k−1}} ∪ trashV). Analogously for the case when k > wV(applying the rule r14 instead of r13). Lemma 10. Let Cbe an arbitrary computation of the system. Let us suppose that there exists V⊆ {1, . . . , n}such that wV=k. Then (a) Cn+dlog ne+dlog(k+1)e+9(1) = {{zn+dlog ne+dlog(k+1)e+10, D2n, b, yes,no, T}} (b) Cn+dlog ne+dlog(k+1)e+10(1) = {{zn+dlog ne+dlog(k+1)e+11, D2n, S, yes,no}} (c) Cn+dlog ne+dlog(k+1)e+11(1) = {{zn+dlog ne+dlog(k+1)e+11, D2n,no}} Proof. The configuration of item (a) is obtained by the application of rules r17 and r2,n+dlog ne+dlog(k+1)e+9 to the previous configuration. Analogously, the configurations of items (b) and (c) are obtained by the application of rules r18 and r19 respectively. Lemma 11. Let Cbe an arbitrary computation of the system. Let us suppose that there does not exist any subset V⊆ {1, . . . , n}such that wV=k. Then (a) Cn+dlog ne+dlog(k+1)e+9(1) = {{zn+dlog ne+dlog(k+1)e+10, D2n, b, yes,no}} (b) Cn+dlog ne+dlog(k+1)e+10(1) = {{zn+dlog ne+dlog(k+1)e+11, D2n, b, yes,no}} (c) Cn+dlog ne+dlog(k+1)e+11(1) = {{D2n, N, yes,no}} (d) Cn+dlog ne+dlog(k+1)e+12(1) = {{D2n,yes}} 134 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez AP system with active membranes, of the initial degree n≥1, is a construct of the form Π= (O, H, µ, w1, . . . , wn, R, ho), where: 1. Ois the alphabet of objects; 2. His a finite set of labels for membranes; 3. µis a membrane structure, consisting of nmembranes having initially neutral polarizations, labeled (not necessarily in a one-to-one manner) with elements of H; 4. w1, . . . , wnare strings over O, describing the multisets of objects placed in the ninitial regions of µ; 5. Ris a finite set of developmental rules, of the following forms: (a) [ha→v]e h, for h∈H, e ∈ {+,−,0}, a ∈O, v ∈O∗ (object evolution rules, associated with membranes and depending on the label and the charge of the membranes, but not directly involving the membranes, in the sense that the membranes are neither taking part in the application of these rules nor are they modified by them); (b) a[h]e1 h→[hb]e2 h, for h∈H, e1, e2∈ {+,−,0}, a, b ∈O (in communication rules; a possibly modified object is introduced in a membrane; the polarization of the membrane can also be modified, but not its label); (c) [ha]e1 h→b[h]e2 h, for h∈H, e1, e2∈ {+,−,0}, a, b ∈O (out communication rules; a possibly modified object is sent out of the membrane; the polarization of the membrane can also be modified, but not its label); (d) [ha]e h→b, for h∈H, e ∈ {+,−,0}, a, b ∈O (dissolving rules; in reaction with an object, a membrane can be dissolved, while the object specified in the rule can be modified); (e) [ha]e1 h→[hb]e2 h[hc]e3 h, for h∈H, e1, e2, e3∈ {+,−,0}, a, b, c ∈O (division rules for elementary or non-elementary membranes; in reaction with an object, the membrane with label his divided into two membranes with the same label, possibly of different polarizations; the object specified in the rule is replaced in the two new membranes by possibly new objects; the remaining objects may evolve in the same step by rules of type (a) and the result of this evolution is duplicated in the two new membranes; if membrane hcontains other membranes, then they may evolve at the same time by rules of any type and the result of their evolution is duplicated in the two new membranes); Polarizationless P Systems with Active Membranes 135 6. ho∈Hor ho=env indicates the output region. In the maximally parallel mode, in each step (a global clock is assumed) we apply multisets of rules in such a way that no further rule can be applied to the remaining objects or membranes. In each step, each object and each membrane can be involved in only one rule. Because this way of using the rules is standard in membrane computing, we do not give further details, and we present only the minimally parallel mode, which here means the following: All the rules of any type involving a membrane hconstitute the set Rh(this means all the rules of type (a) of the form [ha→v]e h, all the rules of type (b) of the form a[h]e1 h→[ha]e2 h, and all the rules of types (c) – (e) of the form [ha]e h→z, with the same h, constitute the set Rh). Moreover, if a membrane happears several times in a given configuration of the system, then for each occurrence of the membrane we consider a different set Rh; this means that we identify the ith copy of membrane hwith the pair (h, i), and we consider the set of rules Rh,i =Rh. Then, in each step, we choose a multiset of rules taken from the sets Rh,i,h∈H, in such a way that after having assigned objects to all the rules in this multiset, no rule from any of the sets Rh,i from which no rule has been taken so far, could be used in addition. Whenever relevant, in order to make visible the sets of rules, we write explicitly the sets Rh,h∈H, instead of the global set R. Of course, as usual for P systems with active membranes, each membrane and each object can be involved in only one rule, and the choice of rules to be used and of objects and membranes to evolve is done in a non-deterministic way. We should note that for rules of type (a) the membrane is not considered to be involved: when applying [ha→v]h, the object acannot be used by other rules, but the membrane hcan be used by any number of rules of type (a) as well as by one rule of types (b) – (e). In each step, the use of rules is done in the bottom-up manner (first the inner objects and membranes evolve, and the result is duplicated if any surrounding membrane is divided). A halting computation provides a result given by the number of objects present in region hoat the end of the computation; this is a region of the system if ho∈H (and in this case, for a computation to be successful, exactly one membrane with label hoshould be present in the halting configuration), or it is the environment if ho=env. We shall also consider the following normal form for P systems with active membranes: A system Πis said to be in the one-normal form if the membranes have no polarization (it is the same as saying that always all membranes have the same polarization, say 0, which therefore is irrelevant and thus omitted) and the rules are of the forms [ha→b]h,a[h]h→[hb]h, [ha]h→b[h]h, [ha]h→b, and [ha]h→[hb]h[hc]h, for a, b, c ∈O, such that a6=b, a 6=c, b 6=c. Note that the labels of membranes are never changed. The set of numbers generated in the minimally parallel way by a system Π is denoted by Nmin(Π). The family of sets Nmin(Π), generated by systems with 136 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez rules of the non-restricted form, having initially at most n1membranes and using configurations with at most n2membranes during any computation is denoted by NminOPn1,n2((a),(b),(c),(d),(e)); when a type of rules is not used, it is not mentioned in the notation. If any of the parameters n1, n2is not bounded, then it is replaced by ∗. If the systems do not use polarizations for membranes, then we write (a0),(b0),(c0),(d0),(e0) instead of (a),(b),(c),(d),(e). When the system Π is in the one-normal form, then we write NminOPn1,n2((a1),(b1),(c1),(d1),(e1)). When considering families of numbers generated by P systems with active membrane working in the maximally parallel mode, the subscript min is replaced by max in the previous notations. For precise definitions, we refer to [11] and to the papers mentioned below. 4 Computational Completeness The following results are well known: Theorem 1. (i)NmaxOP3,3((a),(b),(c)) = NRE, [11]. (ii)NmaxOP∗,∗((a0),(b0),(c0),(d0),(e0)) = NRE, [1]. (iii)NminOP3,3((a),(b),(c)) = NRE, [5]. In turn, the following inclusions follow directly from the definitions: Lemma 1. NmodeOPn1,n2((a1),(b1),(c1),(d1),(e1)) ⊆ NmodeOPn1,n2((a0),(b0),(c0),(d0),(e0)) ⊆ NmodeOPn1,n2((a),(b),(c),(d),(e)), for all n1, n2≥1,mode ∈ {max, min}. We now improve the equalities from Theorem 1 in certain respects, starting with proving the computational completeness of P systems with active membranes in the one-normal form when working in the maximally parallel mode, and then we extend this result to the minimal parallelism. Theorem 2. NmaxOPn1,∗((a1),(b1),(c1),(d1),(e1)) = NRE, for all n1≥5. Proof. We only prove the inclusion NRE ⊆NmaxOP5,∗((a1),(b1),(c1),(d1),(e1)). Let us consider a register machine M= (3, B, l0, lh, I) generating an arbitrary set N(M)∈NRE. We then construct the P system Π= (O, H, µ, ws, wh, w1, w2, w3, R, env), of the initial degree 5, with Polarizationless P Systems with Active Membranes 137 O={di|0≤i≤5}∪{g, #,#0, p, p0, p00, c, c0, c00} ∪ B∪ {l0|l∈B} ∪ {liu |liis the label of an ADD instruction in I, 1≤u≤4} ∪ {liu0|liis the label of a SUB instruction in I, 1≤u≤4} ∪ {liu+|liis the label of a SUB instruction in I, 1≤u≤6}, H={s, h, 1,2,3}, µ= [s[1]1[2]2[3]3[h]h]s, ws=l0d0, wα=λ, for all α∈H− {s}, and with the rules constructed as described below. The value stored in a register r= 1,2,3 of M, in Πis represented by the number of copies of membranes with label rplus one (if the value of the register ris k, then we have k+ 1 membranes with label r). The membrane with label h is auxiliary, it is used for controlling the correct simulation of instructions of M by computations in Π. Each step of a computation in M, i.e., using an ADD or a SUB instruction, corresponds to six steps of a computation in Π. We start with all membranes being empty, except for the skin region, which contains the initial label l0of Mand the auxiliary object d0. If the computation in Mhalts, that is, the object lhappears in the skin region of Π, then we pass to producing one object cfor each membrane with label 1 present in the system, except one; in this way, the number of copies of csent to the environment represents the correct result of the computation in M. We first indicate the rules used in each of the six steps of simulating instructions ADD and SUB, and then we present the rules for producing the result of the computation; in each configuration, only the membranes and the objects relevant for the simulation of the respective instruction are specified. In particular, we ignore the “garbage” object g, because once introduced it remains idle for the whole computation. The simulation of an instruction li: (ADD(r), lj, lk) uses the rules from Table 1. Table 1. The simulation of an ADD instruction Step Main rules Auxiliary rules Configuration – – – [slid0[r]r... [h]h]s 1li[r]r→[rl0 i]r[sd0→d1]s[sd1[rl0 i]r... [h]h]s 2 [rl0 i]r→[rli1]r[rg]r[sd1→d2]s[sd2[rli1]r[rg]r... [h]h]s 3 [rli1]r→li2[r]rd2[h]h→[hd3]h[sli2[r]r[r]r... [hd3]h]s 4 [sli2→li3]s[hd3]h→d4[h]h[sli3d4[r]r[r]r... [h]h]s 5 [sli3→li4]s[sd4→d5]s[sli4d5[r]r[r]r... [h]h]s 6 [sli4→lt]s, t ∈ {j, k}[sd5→d0]s[sltd0[r]r[r]r... [h]h]s 138 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez The label object lienters into the correct membrane r(even if the register ris empty, there is at least one membrane with label r) and in the next step divides it. The object li2exits the newly produced membrane, but gremains inside; li2will evolve three further steps, just to synchronize with the evolution of the auxiliary objects du, u ≥0, and the auxiliary membrane h, so that in the sixth step we end with the label ljor lkof the next instruction to be simulated present in the skin membrane, together with d0; note that the number of copies of membrane rwas increased by one. ' & $ % d3 d3→# #→#0 #0→# d2 d1 d0d4d5d0 - - - - - - 123 4 5 6 h Fig. 1. The evolution of auxiliary objects The auxiliary objects du, u ≥0, and the auxiliary membrane hare used in the simulation of SUB instructions, as we will see immediately; in step 4, there also are other rules to be used in membrane h, introducing the trap-object #, but using such rules will make the computation never halt, hence, they will not produce an unwanted result. The evolution of objects du, u ≥0, is represented graphically in Figure 1; membrane his only used in step 3, to send an object inside, and in the next step, for sending an object out of it. On each arrow we indicate the step, according to Table 1; the steps made by using rules of types (b), (c) are pointed out by drawing the respective arrows crossing the membranes, thus suggesting the in/out actions. The way the “ADD module” works is suggested in Figure 2; the division operation from step 2 is indicated by a branching arrow. The simulation of an instruction li: (SUB(r), lj, lk) is done with the help of the auxiliary membrane h. The object lienters a membrane r(there is at least one copy of it) and divides it, and on this occasion makes a non-deterministic choice between trying to continue as having register rnon-empty or as having it empty. If the guess has been correct, then the correct action is done (decrementing the register in the first case, doing nothing in the second case) and the correct next label is introduced, i.e., ljor lk, respectively. If the guess has not been correct, then the trap object # is introduced. For all membranes xof the system we consider the rules [x#→#0]x, [x#0→#]x, hence, the appearance of # will make the computation last forever. Polarizationless P Systems with Active Membranes 139 li         r l0 i li1g li2 6 @ @I   6 -li3-li4 lj/lk ? rr 1 2 3 45 6 Fig. 2. The work of the ADD module In Table 2 we present the rules used in the case of guessing that the register ris not empty. Like in the case of simulating an ADD instruction, the auxiliary objects and membranes do not play any role in this case. Table 2. The simulation of a SUB instruction, guessing that register ris not empty Step Main rules Auxiliary rules Configuration – – – [slid0[r]r...[h]h]s 1li[r]r→[rl0 i]r[sd0→d1]s[sd1[rl0 i]r...[h]h]s 2 [rl0 i]r→[rli1+]r[rli2+]r[sd1→d2]s[sd2[rli1+]r[rli2+]r...[h]h]s 3 [rli1+]r→li3+ d2[h]h→[hd3]h [rli2+]r→li4+[r]r[sli3+li4+[r]r...[hd3]h]s 4li3+[r]r→[rg]r[hd3]h→d4[h]h li4+[r]r→[rli5+]r[sd4[rli5+]r[rg]r...[h]h]s or [sli3+ →#]s,[sli4+ →#]s[sd4#[r]r...[h]h]s 5 [rli5+]r→li6+ [sd4→d5]s[sd5li6+[r]r...[h]h]s 7 [sli6+ →lj]s[sd5→d0]s[sljd0[r]r...[h]h]s In step 2 we divide the membrane rcontaining the object l0 iand the objects li1+, li2+ are introduced in the two new membranes. One of them is immediately dissolved, thus the number of copies of membrane rremains unchanged; the objects li3+, li4+ are introduced in this step. In the next step (the fourth one of the simulation), objects li3+, li4+ look for membranes rin the skin region. If both of them find such membranes – and this is the correct/desired continuation – then both of them enter such membranes; li3+ becomes gand li4+ becomes li5+. If only 140 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez one of them finds a membrane r, then the other one has to evolve to object # in the skin membrane and the computation never halts. li         6 @ @I   li3+    g 6 li4+ li5+ li6+ lj 6    - ? ? r r r rr 1 2 33 δ 4 li3+ →# 4 li4+ →# 5δ 6 l0 i li1+ li2+ Fig. 3. The simulation of a SUB instruction when guessing that the register is non-empty If we had enough membranes rand li3+, li4+ went there, then in the next step li5+ exits and is changed to li6+. In the sixth step, li6+ becomes lj(simultaneously with introducing d0), and this completes the simulation. Thus, the computation continues without having # present in the system if and only if the guess made in step 2 has been correct, i.e., if register rhas been non-empty. Because in step 5 a membrane rwas dissolved, the number of these membranes was decreased by one, and this corresponds to subtracting one from register r. Figure 3 indicates the evolution of objects liu+in the six steps mentioned in Table 2; when a dissolving operation is used, this is indicated by writing δnear the respective arrow. However, in step 2, instead of the rule [rl0 i]r→[rli1+]r[rli2+]rwe can use the rule [rl0 i]r→[rli10]r[rli20]r, with the intention to simulate the subtract instruction in the case when the register ris empty – that is, only one membrane with label ris present in the system. The rules used in the six steps of the simulation are given in Table 3. In this case, the auxiliary objects du, u ≥0, and the auxiliary membrane h play an essential role. Polarizationless P Systems with Active Membranes 141 Table 3. The simulation of a SUB instruction, guessing that register ris empty Step Main rules Auxiliary rules Configuration – – – [slid0[r]r...[h]h]s 1li[r]r→[rl0 i]r[sd0→d1]s[sd1[rl0 i]r...[h]h]s 2 [rl0 i]r→[rli10]r[rli20]r[sd1→d2]s[sd2[rli10]r[rli20]r...[h]h]s 3 [rli10]r→li30 d2[h]h→[hd3]h [rli20]r→li40[r]r[sli30li40 [r]r...[hd3]h]s 4 [rli30]r→[rg]r,li40 waits [hd3]h→d4[h]h[sli40d4[rg]r...[h]h]s or li40[r]r→[r#]r[sd4[r#]r...[h]h]s or li40[h]h→[hl0 k]h[hd3→#]h[s[rg]r...[hl0 k#]h]s 5li40[h]h→[hl0 k]h[sd4→d5]s[sd5[r]r...[hl0 k]h]s 6 [hl0 k]h→lk[h]h[sd5→d0]s[slkd0[r]r...[h]h]s li         li30 li10 l0 i li20 li40 6 @ @I   66    g   # -      l0 klk -    d3 6 d4d5d0 d2 d1 d0- - - - - - 1234 5 6 h d3→# # 45h r 4 # 3 3 r4 2 r r δ r 1 Fig. 4. The simulation of a SUB instruction when guessing that the register is empty Until step 3 we proceed exactly as above, but now we introduce the objects li30, li40. The first one can enter the available membrane r, there evolving to g. If 142 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez there is a second membrane r, i.e., if the guess has been incorrect, then the rule li40[r]r→[r#]rshould be used simultaneously (step 4), and the computation never ends. If there is no second membrane r, then in step 4 li40, can also enter membrane h, but then the trap object is produced here by the rule [hd3→#]h. The only way not to introduce the object # is (i) not to have a second membrane r, (ii) to use the rule [hd3]h→d4[h]h, thus preventing the use of the rule li40[h]h→ [hl0 k]h, and (ii) not sending li40 to the unique membrane r. This means that during step 4 the object li40 should wait unchanged in the skin region.         p-   @ @R A A A A AK -c00 c0 p00 p0 δ 1 1 1 δc - out    l0 h lh- - 1 δ    L L L  LL L     h p0 δ Fig. 5. The end of computations In the next step, li40 can enter membrane h(or the unique membrane r, but it becomes # there). In the next step, lkis released from membrane h, at the same time with producing d0, hence, the simulation is completed correctly and the system can pass to simulating another instruction. The six steps of the computation are shown in Figure 4, this time with the evolution of the auxiliary objects being indicated, too. The arrows marked with # correspond to moves which are not desired. For both guesses, the simulation of the SUB instruction works correctly, and the process can be iterated. If the computation in Mhalts, i.e., if lhis reached, i.e., if the object lhis introduced in the skin region, we can start to use the following rules: lh[1]1→[1l0 h]1, [1l0 h]1→p, p[1]1→[1p0]1, [1p0]1→[1p00]1[1c0]1, Polarizationless P Systems with Active Membranes 143 [1p00]1→p, [1c0]1→c00, [sc00]s→c[s]s, p[h]h→[hp0]h, [hp0]h→p. The object lhdissolves one membrane with label 1 (thus, the remaining membranes with this label are now as many as the value of register 1 of M), and gets transformed into p. This object enters each membrane with label 1, divides it, reproduces itself (after passing through p0and p00) and also produces a copy of the object c00; this happens when dissolving the two membranes with label 1 obtained by division (rule [1p0]1→[1p00]1[1c0]1), hence, the number of copies of the membrane with label 1 has decreased by one. The object c00 immediately exits the system, thereby being changed into c. At any time, the object pcan also enter membrane hand then dissolves it. The computation can stop only after having dissolved all membranes with label 1 (i.e., a corresponding number of copies of chas been sent out) and after having dissolved the membrane h, hence, the evolution of objects du, u ≥0, also stops. The function of this final module is described in Figure 5. Consequently, N(M) = Nmax(Π), and this concludes the proof. ut Theorem 3 gives the same result as Theorem 3 from [1], with the additional constraint to have evolution rules with exactly one object on the right-hand side (neither producing more objects, nor erasing objects, as it is the case in [1]). The previous proof can easily be changed in order to obtain the computational completeness of P systems in the one-normal form also in the case of minimal parallelism. Specifically, we can introduce additional membranes in order to avoid having two or more evolution rules to be applied in the same region or one or more evolution rules and one rule of types (b) – (e) which involve the same membrane (these are the only situations where the minimal parallelism does not correspond to the maximal parallelism; note that all rules of types (b) – (e) are associated with membranes which are involved in the use of rules, hence, no two rules of these types can be applied for the same membrane). In the previous construction, situations as above which must be avoided are the following ones: – Rules [sli3+ →#]sand [sli4+ →#]s, in step 4 of the simulation of SUB for the guess of a non-empty register. However, no other rule is applicable in the skin region at that time. Applying at least one rule of this type means introducing the trap object, hence, applying one of these rules is the same for the fate of the computation as applying all possible rules of that kind. – Steps 5 and 6 of the auxiliary module (see again Figure 1) are performed in the skin region, in parallel with steps of modules from Figures 2 and 3. This can be avoided by introducing one further auxiliary membrane, h0, in the skin Some Mathematical Methods and Tools for an Analysis of Harmony-Seeking Computations Adam Obtu lowicz Institute of Mathematics, Polish Academy of Sciences ´ Sniadeckich 8, P.O.B. 21, 00-956 Warsaw, Poland [email protected] Summary. A general review of some topic concepts and methods of membrane computing [15], [19] which can be useful in an analysis of harmony-seeking computations [1] is presented. Then an application of a certain particular method of membrane computing in a discussion of mobility of some systems considered in city planning [2] is described in some details. A conclusion of the discussion states that systems of hierarchical organization in a form of a tree are mobile by means of massively parallel (local) moves of the parts of the systems, where the moves are related to the process capabilities of moves of ambients in [7]. 1 Introduction An idea of a harmony-seeking computation was introduced and discussed in [1] aiming, among others, to improve design and planning in architecture in order to achieve that internal coherence (harmony) between the designed and planned objects of various scales (from the rooms in buildings, through buildings themselves, the districts of cities, and to cities themselves) which natural living system possesses. Therefore the discussion of harmony-seeking computations in [1] expands far beyond the methods of design and planning in architecture and concerns also better understanding of the phenomena of life with a regard to a geometric adaptation. The paper [1] contains general postulates for mathematical modeling of harmony-seeking computations. The aim of the present paper is to propose and review some known mathematical methods and tools which may serve for modeling harmony-seeking computations according to those postulates. The methods focus on modeling those evolution processes of natural (living) systems which may realize massively parallel computations themselves or inspire a planning of devices realizing these computations, where an aspect of geometric 248 A. Obtu lowicz adaptation is respected (on topological level) by considering certain possible transformations of hierarchical organization of systems during their evolution processes. A hierarchical organization is meant here as determined by a nesting relation of the less complex parts of a system in the more complex parts of a system. The proposed and reviewed in the paper (Section 2) mathematical methods and tools are mainly those already applied in membrane computing, a branch of natural computing initiated by Gh. P˘aun and described in [19] (see also the P systems page [15]), where the underlying structure of a system (called a membrane system) with respect to nesting of subsystems or its parts is a tree and this underlying structure may be transformed during an evolution process. In Section 3 and Appendix we present in some details a concrete application of membrane computing methods for an analysis of mobility (with respect to massively parallel moves) of certain systems considered in city planning and discussed in [2]. Section 3 together with Appendix are self-contained. The author thanks Krzysztof Wodiczko for long discussions about architecture and mathematics. 2 Membrane Systems and Their Evolution Rules; A General Review In [1] a harmony-seeking computation is identified with its underlying process whose steps are wholeness-extending-transformations (briefly W-E-transforma- tions), where each W-E-transformation operates on one wholeness to produce another wholeness which is illustrated as follows: W1−W E1→W2−W E2→W3−W E3→W4−W E4→. . . . The character of W-E-transformations is established in [1] by five postulates A1–A5 about the structure of wholeness and three postulates B1–B3 about the definition of W-E-transformations themselves. In Postulate A5 each wholeness is identified (defined as) with a system of configurations, where according to Postulate A2 the subconfigurations may be spatially nested, or overlapping, or disjoint. One can see that membrane systems, the basic tools of membrane computing, meant as finite trees with nodes labeled by multisets are appropriate candidates to model (the structure of configurations identified with) a wholeness because the trees (and their Venn diagram presentation, cf. [19]) well describe the spatial nesting. Moreover, the description of evolution processes of membrane systems by using evolution rules in membrane computing also well suits to model the harmony-seeking computations. Namely, the evolution rules of membrane systems are similar to production rules generating languages and they can be simultaneously applied to membrane systems in a similar way like production rules for L-systems can be simultaneously applied to the processed expressions. We point out here Methods and Tools for an Analysis of Harmony-Seeking Computations 249 that a simulation of harmony-seeking process of tree growth by using a contextfree L-system is discussed in [1]. The known applications of membrane systems and their evolution rules for modeling processes in system biology presented among others in the recent papers contained in (Pre-)Proceedings of Workshops and Brainstorming Weeks on Membrane Computing (cf. [13], [14], [11], see the papers by D. Bezzossi, N. Busi and C. Zandron, L. Cardelli and Gh. P˘aun, V. Manca) show that it is worth to apply membrane computing methods and tools to model harmony-seeking computations. The most remarkable are those applications which concern fractals generation by P systems presented in [12], because fractals represent geometry of dynamic systems with a regard to similarities in various scales which is an important aspect of fractals applications in architecture, see [20]. 3 Semilattices of Subsets, Trees of Subsets, hereditarily finite sets, and Their Mobility The paper [2] contains a discussion of a thesis that a city structure of a form of a semilattice of subsets is better (topologically) adapted or more fit to live in than a structure of a form of a tree of subsets. In this section we introduce a representation of those semilattices and trees by certain hereditarily finite sets and then we show that this representation makes possible to transfer from [18] some results concerning mobile ambients and mobile membranes into the area of trees and semilattices of subsets and then into the realm of city planning. We quote from [2] the definitions of semilattices and trees of subsets. The semilattice axiom goes like this: A collection of sets forms a semilattice if and only if, when two overlapping sets belong to the collection, the set of elements common to both also belongs to the collection. The tree axiom states: A collection of sets forms a tree if and only if, for any two sets that belong to the collection, either one is wholly contained in the other, or else they are wholly disjoint. We use the following notion which is a generalization of the above defined concepts. We define a [finite]nesting structure to be an ordered pair N= (UN,NN) such that UNis a [finite] set, called the underlying set of N, and NNis a collection of nonempty subsets of UNwith UNbelonging to NN. The elements of NNare called the parts in N. For two parts n,n0in a nesting structure Nwe define that nis an immediate part of n0in N(and write n≺n0) if n(n0and for every part min Nif n⊆m⊆n0, then m=nor m=n0. We recall now the notion of a hereditarily finite set used in [18]. For a potentially infinite set Lof labels or names which are urelements, i.e., they are not (treated as) sets themselves, we define inductively a family of sets 250 A. Obtu lowicz HFifor natural numbers i≥0 such that HF0=∅, HFi+1 = the set of nonempty finite subsets of L∪HFi. The elements of the union HF = S{HFi|i≥0} ∪ {∅}are called hereditarily finite sets over Lor hereditarily finite sets with urelements in L, or simply hereditarily finite sets if there is no risk of confusion. For x∈HF we define its weak transitive closure WTC(x) and support supp(x) by WTC(x) = [WTC(y)|y∈xand y∈HF∪ {x} supp(x) = (x∩L)∪[{supp(y)|y∈xand y∈HF}, and the depth of xis defined to be the smallest natural number ifor which x∈HFi. The notion of a hereditarily finite set is applied in [10] to give a general characterization of physical computing devices. The characterization is improved in [4], [21], [22], and examples are given in [9]. Membrane computing applications of hereditarily finite sets are discussed in [16], [17], [18]. For a finite nesting structure N= (UN,NN) we define its hereditarily finite set hfs(N) by hfs(N) = UN−[{n∈ NN|n≺UN}∪ {hfs(N(n))|n∈ NNand n≺UN}, where for a part n∈ NNwe write N(n) to denote a nesting structure whose underlying set UN(n)is nitself and the set NN(n)of parts in N(n) is the set {n0∈ NN|n0⊆n}. For a hereditarily finite set xwe define its nesting structure Nxby UNx= supp(x),NNx={supp(y)|y∈WTC(x)}. A characterization of hereditarily finite sets of finite nesting structures is formulated in the following theorem which one can treat as a representation theorem of nesting structures by hereditarily finite sets. Theorem 1. For every finite nesting structure N, if xis the hereditarily finite set of N, i.e. x= hfs(N), then the following conditions hold: 0) Nx=N, 1) supp(y) = supp(y0)implies y=y0for all y, y0with {y, y0} ⊆ WTC(x), 2) y∈y0if and only if supp(y)≺supp(y0)for all y, y0with {y, y0} ⊆ WTC(x), 3) y∩S{supp(y0)|y0∈y}=∅for every y∈WTC(x). For every hereditarily finite set x, if it satisfies the conditions 1)–3), then hfs(Nx) = x. Methods and Tools for an Analysis of Harmony-Seeking Computations 251 Proof. One proves by induction on the number of elements of NNthat x= hfs(N) implies that the conditions 0)–3) hold for x. One proves by induction on the depth of xthat if the conditions 1)–3) hold for x, then hfs(Nx) = x. Corollary 1. For a finite nesting structure Nthe set WTC(hfs(N)) ordered by the membership relation ∈forms a structure which is isomorphic to that structure which is given by the set NNof parts in Nordered by ≺. Proof. The corollary is a consequence of Theorem 1. By 1) a mapping from WTC(hfs(N)) into NNgiven by y7→ supp(y) is a bijection which preserves the ordering by 2), where 1) and 2) are the conditions from Theorem 1 which hold for x= hfs(N). Example 1. The set xof the form (n1,2,{3}o,n2,{3},{3},{4}o, n{3},{4},5,{4}o,6,n{3},{4},5,{4}o) is a hereditarily finite set such that hfs(Nx) = x, where Nxis a semilattice illustrated in Fig. 0. • • ••• • • • • • • {3} {4} {2,3}{3,4}{4,5} {1,2,3}{2,3,4}{3,4,5} {1,2,3,4,5} {3,4,5,6} {1,2,3,4,5,6} Fig. 0. 252 A. Obtu lowicz The representation of finite nesting structures by hereditarily finite sets described in Theorem 1 and Corollary 1 provides that already defined constructions and proved properties of hereditarily finite sets xsatisfying hfs(Nx) = xcan be transferred or interpreted in the class of finite nesting structures. In particular, the basic concepts and constructions describing mobile systems1modeled by hereditarily finite sets, see [18] and Appendix in the present paper, can be transferred to the class of finite nesting structures via the representation. The following theorem is a starting point of this transfer. Theorem 2. Let xbe a hereditarily finite set such that hfs(Nx) = x. Then the following conditions hold: C1)if y∈xwith y∈HF, then for u1= (x− {y})∪ythe condition NNu1= NNx− {supp(y)}holds, C2)if {y, z} ⊆ x∩HF with y6=z, then for u2= (x− {y, z})∪ {z∪ {y}} the condition NNu2= (NNx− {supp(y)})∪ {supp(y)∪supp(z)}holds, C3)if z∈y∈xwith z∈HF, then for u3= (x− {y})∪ {y− {z}, z}the condition NNu3= (NNx− {supp(y)})∪ {supp(y− {z})}holds. Moreover, if Nxis such that NNxis a tree, then for every i∈ {1,2,3}the set NNuiis also a tree and hfs(Nui) = ui. Proof. We prove the theorem by induction on the depth of x. We interpret Theorem 2 in the following way. The conditions C1), C2), C3) correspond to the following process capabilities discussed in [7]: •condition C1) corresponds to the capability “can open an ambient”, •condition C2) corresponds to the capability “can enter an ambient”, •condition C3) corresponds to the capability “can exit out an ambient”. The above capabilities are capabilities of some “spatial” moves of parts of systems with respect to hierarchical organization of systems determined by nesting relation of parts. A mathematical description of the mentioned capabilities for systems modeled by hereditarily finite sets x(with WTC(x) meant as a collection of parts of x) is contained in conditions C1), C2), C3), where for every i∈ {1,2,3}the conditions written between “if” and “then” in Ci) are (pre)conditions which provide a realization of a move and the equation defining uiwritten after “then” in Ci) is a (post)condition describing the result uiof the move. For a hereditarily finite set xmodeling a system with parts represented by elements of WTC(x) the capabilities of moves can be applied (or referred) to the elements of WTC(x) and these applications are called local moves in x. The local moves are described in terms of Gh. P˘aun’s evolution rules and their applications in [18], see also Appendix of the present paper, where a local action is a mathematical description of a local move. 1Related to mobile ambient systems in [7]. Methods and Tools for an Analysis of Harmony-Seeking Computations 253 A collisionless set of simultaneous local moves in a given x(more than one local move in a unit of time) is described in [18] and Appendix as a proper set of local actions over x. An inductive formula for assembly of a whole system from the results of local moves belonging to a collisionless set of simultaneous local moves in a hereditarily finite set xis given in [18], see also the inductive definition of Ap(A, x) in Appendix, where Ap(A, x) is the result of assembly for a proper set Aof local actions over x. Theorem 3 in Appendix is the final and concluding step of the discussed transfer of the basic concepts and constructions describing mobile systems modeled by hereditarily finite sets into the area of nesting structures. Remark. For xgiven in Example, y=n1,2,{3}o,n2,{3},{3},{4}o,n{3},{4},5,{4}o, and z=n2,{3},{3},{4}o we have that z∈y∈xwhich means that preconditions in C3) hold for these x, y, z. Then for u3= (x− {y})∪ {y− {z}, z}we have that Nu3=Nx(because supp(y− {z}) = supp(y) in this case) which means that capability “can exit out an ambient” does not lead to any real move leaving Nxunchanged. Conclusion By virtue of Theorem 2 and Theorem 3 in Appendix every finite nesting structure Nwith NNbeing a tree is mobile with respect to simultaneous (massively parallel) local moves determined by process capabilities “can open an ambient”, “can enter an ambient”, and “can exit out an ambient”. The case discussed in Remark shows that mobility of some nesting structures Nwith NNbeing a semilattice is problematic. Appendix We consider those evolutive transformations of hereditarily finite sets into hereditarily finite sets which are determined by evolution rules written in P˘aun’s manner as the parenthesis expressions, cf. [19]: R1) [ ] →(dissolution rule), R2) [ ][ ] →[[ ]] (in-rule), R3) [[ ]] →[ ][ ] (out-rule), The single applications from the top of the above rules to hereditarily finite sets are described in the following way: 254 A. Obtu lowicz •if y∈x∩HF, then the dissolution rule [ ] →can be applied to xand the result of its application is a new hereditarily finite set of the form (x− {y})∪y, •if {y, z} ⊆ x∩HF, and z6=y, then the in-rule [ ][ ] →[[ ]] can be applied to x and the result of its application is a new hereditarily finite set of the form (x− {y, z})∪ {z∪ {y}}, •if z∈y∈x∈HF, z∈HF, and y− {z} 6=∅, then the out-rule [[ ]] →[ ][ ] can be applied to xand the result of its application is a new hereditarily finite set of the form (x− {y})∪({y− {z}, z} − {∅}). The above described single applications of evolution rules R1), R2), R3) from the top determine evolutive transformations of hereditarily finite sets into new hereditarily finite sets from the top. One sees that these rules are related to process capabilities “can open an ambient”, “can enter an ambient”, “can exit out an ambient”, introduced in [6]. The evolution rules may describe forces in patterns, cf. [3]. We describe by using ∪,−, and {?}a more complicated case of evolutive transformations of hereditarily finite sets, where these transformations are determined by simultaneous applications of different rules to many different elements of WTC(x) for a hereditarily finite set xto be transformed. The evolutive transformations of hereditarily finite sets considered above can be “transferred” to nesting structures by using the construction of Nx(see Theorem 1 and Corollary 1) to define evolutive transformations of nesting structures themselves. We restrict our considerations to tree-like hereditarily finite sets which are defined to be such that hfs(Nx) = xand Nxis a tree. Let xbe a tree-like hereditarily finite set. By a local action over xwe mean an ordered pair a= (Pa, Ra), where Pais a bijection from dom(a) into scope(a) with scope(a)⊂WTC(x) and Rais an evolution rule such that a1) if Rais a dissolution rule [ ] →, then dom(a) = {0,1}and Pa(1) ∈Pa(0), a2) if Rais an in-rule [ ][ ] →[[ ]], then dom(a) = {0,1,2}and {Pa(1), P a(2)} ⊂ Pa(0), a3) if Rais an out-rule [[ ]] →[ ][ ], then dom(a) = {0,1,2}and Pa(2) ∈Pa(1) ∈ Pa(0). For a local action aover xthe bijection Pais meant as a place of application of the rule Ra, where it will be seen later than one can interpret scope(a) as the scope of the local transformation of xaccording to the rule Ra. Let Abe a set of local actions over x. For a set y∈WTC(x) and a set z⊆ywe write A(y−z) to denote the set of local actions aover y−zsuch that a∈ A or Pa(0) = y−zwith a∗= (Pa∗, Ra)∈ A for Pa∗: dom(a)→ (scope(a)− {y−z})∪ {y}with Pa∗(i) = Pa(i) for all i∈dom(a)− {0}. If z=∅, Methods and Tools for an Analysis of Harmony-Seeking Computations 255 then A(y−z) = Ayis simply the set of those local actions over ywhich belong to A. If z=y, then A(y−z) = A∅=∅. For a set Aof local actions over xwe adopt the following notation Aα={a∈ A|Rais an α-rule}for α∈ {in,out}, Adiss ={a∈ A|Rais a dissolution rule}. We define now a property of sets Aof local actions over tree-like hereditarily finite sets xsuch that if Ahas this property, then one can construct the result of transformation of xwith respect to Ain a consistent (unambiguous) way, where xis transformed according to simultaneous application of the rules Rain places Pa, respectively for all a∈ A. A set Aof local actions over xis called a proper set of local actions over x if for all local actions a,a0in Aif a6=a0, then scope(a)∩scope(a0) = ∅or the disjunction of the following conditions holds: (C1)Pa(0) = Pa0(0) and (scope(a)− {Pa(0)})∩(scope(a0)− {Pa0(0)}) = ∅, (C2) if {a,a0} ⊆ Adiss, then Pa(0) = Pa0(1), (C3) if {a,a0} ⊆ Ain, then Pa(1) = Pa0(1) or Pa0(0) ∈ {Pa(1), Pa(2)}, (C4) if {a,a0} ⊆ Aout, then Pa(0) = Pa0(2) or {Pa(1), Pa(2)} ∩ {Pa0(0), P a0(1)}={Pa(1)}, (C5) if a∈ Adiss and a0∈ Ain, then Pa(1) = Pa0(0) or Pa(0) ∈ {Pa0(1), Pa0(2)}, (C6) if a∈ Adiss and a0∈ Aout, then Pa(1) = Pa0(0) or {Pa(0), Pa(1)} ∩ {Pa0(1), Pa0(2)}={Pa(0)}, (C7) if a∈ Ain and a0∈ Aout, then Pa(1) = Pa0(1) or Pa0(0) ∈ {Pa(1), P a(2)} or scope(a)∩ {Pa0(1), P a0(2)}={Pa(0)}. We adopt the following conventions to explain and illustrate the notion of a proper set of local actions. For a tree-like non-empty hereditarily finite set xwhose content is not specified (or is not important for considerations) we illustrate xby a drawing given by a triangle below whose bottom vertex is labeled by x. •x .. For a tree-like non-empty hereditarily finite set xwhose content is not specified we illustrate one-element set {x}by a drawing given by a triangle with an arrow glued to the bottom vertex of the triangle as below 262 A. Obtu lowicz 21. W. Sieg: Computability Theory. Seminar Lectures, University of Bologna, November 2004, http://www.phil.cmu.edu/summerschool/2006/Sieg/computability theory.pdf. 22. W. Sieg: Calculations by man and machine: conceptual analysis. Lecture Notes in Logic, 15 (2002), 390–409. Twenty Six Research Topics About Spiking Neural P Systems Gheorghe P˘aun Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucharest, Romania and Department of Computer Science and AI University of Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain [email protected], [email protected] 1 Foreword To continue the tradition of the previous brainstorming weeks on membrane computing, I am collecting here a series of open problems and research topics, not about membrane computing in general, but about one of the directions of research which were pretty much investigated in the last year: spiking neural P systems. In general, one mentions issues which look of a broader nature, but also some precise problems are formulated. As usual with such lists of problems, the selection is subjective, by no means exhaustive. Of course, choosing only problems related to spiking neural P systems does not mean that there are no longer enough problems waiting to be solved in the general framework of membrane computing – on contrarily (e.g., separate lists can refer to computational complexity issues, to dynamical systems approaches, etc.), but such problems tend to become rather specialized and technical at the present stage of the development of membrane computing. Instead, the membrane computing models with a neural inspiration are at the beginning of a systematic exploration, and, as claimed below, this area of research looks very promising. 2 Forecast It is obvious that the (human) brain structure and functioning, from neurons, astrocytes, and other components to complex networks and complex (chemical, electrical, informational) processes taking place in it, should be – and only partially is – a major source of inspiration for informatics (I choose this more general term rather that the restrictive, but usual, “computer science”, in order to stress 264 Gh. P˘aun that I have in mind both mathematics per se and practice, both the theory of computability and the use of computing machineries). If biology is such a rich source of inspiration for informatics as natural computing proves, then the brain should be the “golden mine” of this intellectual enterprise. Risking a forecast, I believe that if something really great is to appear in informatics in the near future, then this “something” will be suggested by the brain (and this will probably be placed at the level of “strategies” of computing, not at the “tactic” level – just in balance with the two computing devices already learned from the brain activity and which can be considered the most central notions in informatics, the Turing machine and the finite automaton). The previous statements do not intend to suggest that spiking neural P systems are the answer to this learning-from-brain challenge, but only to call (once again) the attention to this challenge. Becoming familiar with brain functioning, in whatever reductionistic framework (as spiking neural P systems investigation is), can however be useful. After all, “the road of one thousand miles starts with the first step”, Lao Tze said. . . Let us make from spiking neural P systems “the first step”. 3 Some (Neural) Generalities The neuron is a highly specialized cell, at the same time intricate and simple, robust and fragile, like any other cell, but having the particularity of being involved (in general) in huge networks by means of the synapses established with partner neurons. It is not at all the intention of these lines to give any biological information from this area, but only to point out some of the peculiarities related to neurons and the brain: the functioning of each neuron assumes chemical, electrical, and informational processing at the same time; the axon is not a simple transmitter of impulses, but an information processor; in the communication between neurons the spiking activity plays a central role (which means that the distance in time between consecutive spikes is used to carry information, that is, time is a support of information); the neurons are not cooperating only through synapses, but their relationships are also regulated through the calcium waves controlled by the astrocytes, “eavesdroppers” of axons playing an important role in the neural communication; the brain displays a general emergent behavior which, to my knowledge and to my understanding, cannot be explained only in terms of neuron interrelationships (something is still missing in this picture, maybe of a quantum nature – as Penrose suggests, maybe related to the organization of parts, maybe of a still subtler or even unknown nature). Some of these ideas (especially spiking) are supposed to lead to “neural computing of the third generation”, which suggests that already computer scientists are aware of the possibility of major progresses to be made (soon) on the basis of progresses in neuro-biology. The bibliography of this note contains several titles, both from the general biology of the cell [1], general neurology [41], and from neural computing based on Twenty Six Research Topics About Spiking Neural P Systems 265 spiking [3], [29], [16], [26], [27], [28], about the axon as an information processor [39], astrocytes and their role in the brain functioning [37], [40]. Of course, these titles are only meant to be initial “dendrites” to the huge bibliography related to (computer science approaches to) brain functioning. 4 Spiking Neural P Systems – Informal Presentation Spiking neural P systems (SN P systems, for short) were introduced in [23] in the precise (and modest: trying to learn a new “mathematical game” from neurology, not to provide models to it) aim of incorporating in membrane computing ideas specific to spiking neurons; the intuitive goal was to have (1) a tissue-like P system with (2) only one (type of) object(s) in the cells – the spike, with (3) specific rules for evolving populations of spikes, and (4) making use of the time as a support of information. In what follows, I briefly describe several classes of SN P systems investigated so far, as well as some of the main types of results obtained in this area. In short, an SN P system (of the basic form – later called a standard SN P system) consists of a set of neurons placed in the nodes of a directed graph and sending signals (spikes, denoted in what follows by the symbol a) along the arcs of the graph (they are called synapses). The objects evolve by means of spiking rules, which are of the form E/ac→a;d, where Eis a regular expression over {a}and c, d are natural numbers, c≥1, d ≥0. The meaning is that a neuron containing kspikes such that ak∈L(E), k ≥c, can consume cspikes and produce one spike, after a delay of dsteps. This spike is sent to all neurons to which a synapse exists outgoing from the neuron where the rule was applied. There also are forgetting rules, of the form as→λ, with the meaning that s≥1 spikes are removed, provided that the neuron contains exactly sspikes. An extension of theses type of rules was considered (with a mathematical motivation) in [30], [14]: rules of the form E/ac→ap;d, with the meaning that when using the rule, cspikes are consumed and pspikes are produced (one assumes that c≥p, not to produce more than consuming). Because pcan be 0 or greater than 0, we obtain a generalization of both spiking and forgetting rules, while forgetting rules also have a regular expression associated with them. An SN P system (with standard as well with extended rules) works in the following way. A global clock is assumed and in each time unit each neuron which can use a rule should do it (the system is synchronized), but the work of the system is sequential locally: only (at most) one rule is used in each neuron. One of the neurons is considered to be the output neuron, and its spikes are also sent to the environment. The moments of time when a spike is emitted by the output neuron are marked with 1, the other moments are marked with 0. This binary sequence is called the spike train of the system – it might be infinite if the computation does not stop. 266 Gh. P˘aun With a spike train we can associate various numbers, which can be considered as computed (we also say generated) by an SN P system. For instance, in [23] only the distance between the first two spikes of a spike train was considered, then in [33] several extensions were examined: the distance between the first k spikes of a spike train, or the distances between all consecutive spikes, taking into account all intervals or only intervals that alternate, all computations or only halting computations, etc. An SN P system can also work in the accepting mode: a neuron is designated as the input neuron and two spikes are introduced in it, at an interval of nsteps; the number nis accepted if the computation halts. Two main types of results were obtained: computational completeness in the case when no bound was imposed on the number of spikes present in the system, and a characterization of semilinear sets of numbers in the case when a bound was imposed. Another attractive possibility is to consider the spike trains themselves as the result of a computation, and then we obtain a device generating a (binary) language. We can also consider input neurons and then an SN P system can work as a transducer. Such possibilities were investigated in [34]. Languages – even on arbitrary (i.e., not only binary) alphabets – can be obtained also in other ways: following the path of a designated spike across neurons, as proposed in [12], or using rules of the extended form mentioned above. Specifically, with a step when the system sends out ispikes, we associate a symbol bi, and thus we get a language over an alphabet with as many symbols as the number of spikes simultaneously produced. This case was investigated in [14], where representations or characterizations of various families of languages were obtained. (An essential difference was found between the case when zero spikes sent out is interpreted as a symbol b0and the case when this is interpreted as inserting λ, the empty string, in the result.) Other extensions were proposed in [21] and [20], where several output neurons were considered, thus producing vectors of numbers, not only numbers. A detailed typology of systems (and of sets of vectors generated) is investigated in the two papers mentioned above, with classes of vectors found in between the semilinear and the recursively enumerable ones. The proofs of all computational completeness results known up to now in this area are based on simulating register machines. Starting the proofs from small universal register machines, as those produced in [25], one can find small universal SN P systems (working in the generating mode, as sketched above, or in the computing mode, i.e., having both an input and an output neuron and producing a number related to the input number). This idea was explored in [30] and the results are as follows: there are universal computing SN P systems with 84 neurons using standard rules and with only 49 neurons using extended rules. In the generative case, the best results are 79 and 50 neurons, respectively. In the initial definition of SN P systems several ingredients are used (delay, forgetting rules), some of them of a general form (unrestricted synapse graph, unrestricted regular expressions). As shown in [19], several normal forms can be Twenty Six Research Topics About Spiking Neural P Systems 267 found, in the sense that some ingredients can be removed or simplified without losing the computational completeness. For instance, the forgetting rules or the delay can be avoided, and the outdegree of the synapse graph can be bounded by 2, while the regular expressions from firing rules can be of very restricted forms. The dual problem, of the indegree bounding, was solved (affirmatively) in [35]. Besides using the rules of a neuron in the sequential mode introduced above, it is possible to also use the rules in a parallel way. A possibility was considered in [24]: when a rule is enabled, it is used as many times as possible, thus exhausting the spikes it can consume in that neuron. As proved in [24], SN P systems with the exhaustive use of rules are again universal, both in the accepting and the generative cases. In the proof of these results the synchronization plays a crucial role, but both from a mathematical point of view and from a neuro-biological point of view it is rather natural to consider non-synchronized systems, where the use of rules is not obligatory: even if a neuron has a rule enabled in a given time unit, this rule is not obligatorily used, the neuron may remain still, maybe receiving spikes from the neighboring neurons; if the unused rule may be used later, it is used later, without any restriction on the interval when it has remained unused; if the new spikes made the rule non-applicable, then the computation continues in the new circumstances (maybe other rules are enabled now). This way of using the rules applies also to the output neuron, hence now the distance in time between the spikes sent out by the system is no longer relevant. That is why, for non-synchronized SN P systems we take as a result of a computation the total number of spikes sent out; this, in turn, makes necessary considering only halting computations (the computations never halting are ignored, they provide no output). Non-synchronized SN P systems were introduced and investigated in [7], where it is proved that SN P systems with extended rules are still equivalent with Turing machines (as generators of sets of natural numbers). 5 Some (More) Formal Definitions To make clearer some of the subsequent formulations, I recall here the definition of central classes of SN P systems, but more details should be found in the papers mentioned in the bibliography. No general notions or notations from language or automata theory, computability, complexity, computer science in general, or membrane computing, are recalled. Aspiking neural P system (in short, an SN P system), of degree m≥1, is a construct of the form Π= (O, σ1, . . . , σm, syn, out), where: 1. O={a}is the singleton alphabet (ais called spike); 268 Gh. P˘aun 2. σ1, . . . , σmare neurons, of the form σi= (ni, Ri),1≤i≤m, where: a) ni≥0 is the initial number of spikes contained by the neuron; b) Riis a finite set of rules of the following general form: E/ac→ap;d, where Eis a regular expression with athe only symbol used, c≥1, and p, d ≥0, with c≥p; if p= 0, then d= 0, too. 3. syn ⊆ {1,2, . . . , m}×{1,2, . . . , m}with (i, i)/∈syn for 1 ≤i≤m(synapses); 4. out ∈ {1,2, . . . , m}indicates the output neuron. A rule E/ac→ap;dwith p≥1 is called a firing (we also say spiking)rule; a rule E/ac→ap;dwith p=d= 0 is written in the form E/ac→λand is called aforgetting rule. If L(E) = {ac}, then the rules are written in the simplified form ac→ap;dand ac→λ. A system having only rules of the forms E/ac→a;dand ac→λis said to be restricted (we also use to say that such a system is a standard one). The rules are applied as follows: if the neuron σicontains kspikes, ak∈L(E) and k≥c, then the rule E/ac→ap;d∈Ri(with p≥1) is enabled and it can be applied; applying it means that cspikes are consumed, only k−cremain in the neuron, the neuron is fired, and it produces pspikes after dtime units. If d= 0, then the spikes are emitted immediately, if d= 1, then the spikes are emitted in the next step, and so on. In the case d≥1, if the rule is used in step t, then in steps t, t + 1, t + 2, . . . , t +d−1 the neuron is closed, and it cannot receive new spikes (if a neuron has a synapse to a closed neuron and sends spikes along it, then the spikes are lost). In step t+d, the neuron spikes and becomes again open, hence can receive spikes (which can be used in step t+d+1). The pspikes emitted by a neuron σiare replicated and they go to all neurons σjsuch that (i, j)∈syn (each σjreceives pspikes). If the rule is a forgetting one, hence with p= 0, then no spike is emitted (and the neuron cannot be closed, because also d= 0). In the synchronized mode, considered up to now in all SN P systems investigations except [7], a global clock is assumed, marking the time for all neurons, and in each time unit, in each neuron which can use a rule, a rule must be used. Because two rules E1/ac1→ap1;d1and E2/ac2→ap2;d2can have L(E1)∩L(E2)6=∅, it is possible that two or more rules can be applied in a neuron, and then one of them is chosen non-deterministically. Note that the neurons work in parallel (synchronously), but each neuron processes sequentially its spikes, using only one rule in each time unit. The initial configuration of the system is described by the numbers n1, n2, . . . , nmof spikes present in each neuron. During the computation, a configuration is described by both the number of spikes present in each neuron and by the state of the neuron, more precisely, by the number of steps to count down until it becomes open (this number is zero if the neuron is already open). Thus, hr1/t1, . . . , rm/tmiis the configuration where neuron σi, i = 1,2, . . . , m contains ri≥0 spikes and it will be open after ti≥0 steps; with this notation, the initial configuration is C0=hn1/0, . . . , nm/0i(see an example in Figure 2). Twenty Six Research Topics About Spiking Neural P Systems 269 Using the rules as suggested above, we can define transitions among configurations. Any sequence of transitions starting in the initial configuration is called a computation. A computation halts if it reaches a configuration where all neurons are open and no rule can be used. With any computation, halting or not, we associate a spike train, a sequence of digits 0 and 1, with 1 appearing in positions which indicate the steps when the output neuron sends spikes out of the system (we also say that the system itself spikes at that time). With any spike train we can associate various numbers, which are considered as computed (generated) by the system; in the spirit of spiking neural computing, the distance between certain spikes are usually taken as the result of a computation (e.g., the distance between the first two spikes). Because of the non-determinism in using the rules, a given system computes in this way a set of numbers. An SN P system can be also used in the accepting mode: a number nis introduced in the system in the form of the distance between two spikes entering a specified neuron, and this number is accepted if the computation eventually halts. We denote by Ngen(Π) the set of numbers generated (in the synchronized way) by a system Πin the form of the number of steps elapsed between the first two spikes of a spike train. Then, by Spik2SPm(rulek, consp, forgq, deld) we denote the family of such sets of numbers generated by systems with at most mneurons, each of them containing at most krules, all of them of the standard form, and each rule consuming at most pspikes, forgetting at most qspikes, and having the delay at most d. When using extended SN P systems, we use Spik2EPm(rulek, consp, prodq, deld) to denote the family of sets Ngen(Π) generated by systems with at most mneurons, each of them containing at most krules (of the extended form), each spiking rule consuming at most pspikes, producing at most qspikes, and having the delay at most d. When any of the parameters m, k, p, q, d is not bounded, it is replaced by ∗. When using the rules in the exhausting or the non-synchronized mode, we write Nex gen(Π), Nnsyn gen (Π), respectively, and the superscripts ex and nsyn are also added to Spik in the families notation. The notations should be changed when dealing with other sets of numbers than the distance between the first two spikes, with accepting systems, when generating or accepting languages, but I do not enter here into details. Instead, I close this section by introducing two important tools in presenting SN P systems, namely, the graphical representation and the transition diagram. Figures 1, 2 are recalled from [9]. The graphical representation of an SN P system is rather intuitive: the neurons are represented by membranes, placed in the nodes of a directed graph whose arrows represent the synapses; an arrow also exits from the output neuron, pointing to the environment; in each neuron we specify the rules and the spikes present in the initial configuration. Figure 1 represents the initial configuration of a system Π. We have three neurons, labeled with 1, 2, 3, with neuron σ3being the output one. Each neuron contains two rules, with neurons σ1and σ2having the same rules (firing rules which can be chosen in a non-deterministic way, the difference between them being in the delay from firing to spiking), and neuron σ3having one firing and one forgetting 270 Gh. P˘aun ' & $ % ' & $ % ' & $ % -  @@@@R @ @ @ @I     - 12 3 a r11 :a→a; 0 r12 :a→a; 1 a r21 :a→a; 0 r22 :a→a; 1 a2 r31 :a→a; 0 r32 :a2→λ Fig. 1. The initial configuration of the SN P system Π rule. In the figure, the rules are labeled, and these labels are useful below, in relation with Figure 2. This figure can be used for analyzing the evolution of the system Π: because the system is finite, the number of configurations reachable from the initial configuration is finite, too, hence, we can place them in the nodes of a graph, and between two nodes/configurations we draw an arrow if and only if a direct transition is possible between them. In Figure 2 there are also indicated the rules used in each neuron, with the following conventions: for each rjk we have written only the subscript jk, with 31 being written in bold face, in order to indicate that a spike is sent out of the system at that step; when a neuron σj, j = 1,2,3 uses no rule, we have written j0, and when it spikes (after being closed for one step), we write js. The functioning of the system, both as a number generator and as a string generator, can easily be followed on this diagram. 6 Open Problems and Research Topics The following list of problems should be read with the standard precautions: it is not meant to be exhaustive, there is no ordering of the problems (according to their significance/interest), some problems are very general, others are much more particular, in many cases the formulation is preliminary/informal and addressing the problem should start with a precise/suitable formulation, in many cases related results exist in the literature, and so on. Most problems are stated in a short way, with reference to the discussion from Section 4 and the definitions from Section 5. A. Let us start with a general and natural idea: linking the study of SN P systems with neural computing. This can be a rich source of ideas, based on trans- Twenty Six Research Topics About Spiking Neural P Systems 271 h3/0,0/0,1/0i h4/0,0/0,0/0i h2/0,0/1,0/0i h2/0,1/0,2/0i + N q- 10,20,31 10 21 32 10 2s 30 10 22 32 h1/0,0/1,1/0ih1/0,1/0,1/0i ? } y 11 21 31 11,22,31 11 2s 31 h0/1,0/0,1/0ih0/1,0/1,0/0i h1/0,1/0,2/0i 7 z Y 12 2s 31 1s 20 31 12 21 31 12 22 31 ?q y1s2s30 12 22 32 12 21 32 h0/0,0/1,1/0i h2/0,0/0,1/0i h3/0,0/0,0/0i )  ? 11 22 32 10 2s 31 10 20 31 ' $ ? 11,21,32 Fig. 2. The transition diagram of system Πfrom Figure 1 ferring from an area to the other one research topics which make sense also in the destination framework. What means, for instance, training (in general, learning, adaptation, evolving) in terms of SN P systems? More elementary: what means solving a problem by using an SN P system, implicitly, what means to solve a problem in a better way? Maybe the starting point should not be (only) neural computing, which is already an abstract, specialized, reductionistic framework, but (also) from neurology, from learning in the general psycho-pedagogical sense. B. This problem is related to another general, natural, and important one: bringing more ingredients from neurology. Just a few quick ideas: considering an energy associated with firing/spiking; taking into considerations the antiport pro- 278 Gh. P˘aun considering computing models based on the axon functioning (Ranvier nodes amplification of impulses, and other processes) and a preliminary investigation was carried out in [13]. Many questions remain to be clarified in this area (see also the questions formulated in [13]), but a more general and probably more interesting problem appears, namely, of combining neurons and axons (as information processing units) in a global model; maybe also astrocytes can be added, thus obtaining a more complex model, closer to reality. Y. I will conclude with two general issues, where nothing was done up to now. First, SN P systems have a direct (pictural) similarity with Petri nets, where tokens (like spikes) are moved through the net according to specific rules. Bridging the two areas looks then rather natural – with “bridging” understood as a move of notions, tools, results in both directions, from Petri nets to SN P systems and the other way round. Z. Then, directly important for possible applications is the study of SN P systems as dynamical systems, hence not focusing on their output, but on their evolution, on the properties of the sequences of configurations reachable from each other. The whole panoply of questions from the (discrete) dynamical systems theory can be brought here, much similar to what happened in general membrane computing. As it was the case also other times, I have to stop because of reaching the end of the alphabet. . . – with the hope that the reader will shorten this list by providing answers to some problems. 7 Final Remarks Many other open problems and research topics can be found in the papers devoted to SN P systems – the interested reader can check the titles below in this respect (the bibliography contains all papers about SN P systems which I was aware of at the beginning of November 2006). On the other hand, because the research in this area is quite vivid, it is possible that some of these problems were solved at the same time or shortly after writing these notes, without being possible to mention the respective results here. That is why, the reader is advised to follow the developments in this area, for instance, through the information periodically updated at the Milano web page [43]. References 1. B. Alberts, A. Johnson, J. Lewis, M. Raff, K. Roberts, P. Walter: Molecular Biology of the Cell, 4th ed. Garland Science, New York, 2002. 2. A. Alhazov, R. Freund, M. Oswald, M. Slavkovik: Extended variants of spiking neural P systems generating strings and vectors of non-negative integers. In Pre-proc. WMC7, Leiden, July 2006, 88–101, and [18], 123–134. Twenty Six Research Topics About Spiking Neural P Systems 279 3. A. Carnell, D. Richardson: Parallel computation in spiking neural nets. Available at http://people.bath.ac.uk/masdr/. 4. M. Cavaliere, V. Deufemia: On time-free P systems. Intern. J. Found. Computer Sci., 17, 1 (2006), 69–90. 5. M. Cavaliere, R. Freund, A. Leitsch, Gh. P˘aun: Event-related outputs of computations in P systems. In Proc. Third Brainstorming Week on Membrane Computing, Sevilla, 2005, RGNC Report 01/2005, 107–122. 6. M. Cavaliere, D. Sburlan: Time-independent P systems. In Membrane Computing. International Workshop WMC5, Milano, Italy, 2004, LNCS 3365, Springer, 2005, 239–258. 7. M. Cavaliere, M. Ionescu, Gh. P˘aun: Asynchronous spiking neural P systems. Submitted, 2007. 8. M. Cavaliere, M. Ionescu: SN P systems with decaying spikes. Personal communication, 2006. 9. H. Chen, R. Freund, M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez: On string languages generated by spiking neural P systems. In [17], Vol. I, 169–194. 10. H. Chen, M. Ionescu, T.-O. Ishdorj: On the efficiency of spiking neural P systems. In [17], Vol. I, 195–206, and Proc. 8th Intern. Conf. on Electronics, Information, and Communication, Ulanbator, Mongolia, June 2006, 49–52. 11. H. Chen, M. Ionescu, T.-O. Ishdorj, A. P˘aun, Gh. P˘aun, M.J. P´erez-Jim´enez: Spiking neural P systems with extended rules: Universality and languages. Natural Computing, to appear. 12. H. Chen, M. Ionescu, A. P˘aun, Gh. P˘aun, B. Popa: On trace languages generated by spiking neural P systems. In [17], Vol. I, 207–224, and Proc. Eighth International Workshop on Descriptional Complexity of Formal Systems (DCFS 2006), June 21-23, 2006, Las Cruces, New Mexico, USA, 94–105. 13. H. Chen, T.-O. Ishdorj, Gh. P˘aun: Computing along the axon. In [17], Vol. I, 225–240, and Pre-proc. BIC-TA, Wuhan, 2006, 60–70. 14. H. Chen, T.-O. Ishdorj, Gh. P˘aun, M.J. P´erez-Jim´enez: Spiking neural P systems with extended rules. In [17], Vol. I, 241–265. 15. G. Ciobanu, L. Pan, Gh. P˘aun, M.J. P´erez-Jim´enez: P systems with minimal parallelism. Theoretical Computer Sci., to appear. 16. W. Gerstner, W Kistler: Spiking Neuron Models. Single Neurons, Populations, Plasticity. Cambridge Univ. Press, 2002. 17. M.A. Guti´errez-Naranjo et al., eds.: Proceedings of Fourth Brainstorming Week on Membrane Computing, Febr. 2006, Fenix Editora, Sevilla, 2006. 18. H.J. Hoogeboom, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: Membrane Computing, International Workshop, WMC7, Leiden, The Netherlands, 2006, Revised, Selected, and Invited Papers. LNCS 4361, Springer, Berlin, 2006. 19. O.H. Ibarra, A. P˘aun, Gh. P˘aun, A. Rodr´ıguez-Pat´on, P. Sosik, S. Woodworth: Normal forms for spiking neural P systems. In [17], Vol. II, 105–136, and Theoretical Computer Sci., 372, 2-3 (2007), 196–217. 20. O.H. Ibarra, S. Woodworth: Characterizations of some restricted spiking neural P systems. In Pre-proc. WMC7, Leiden July 2006, 387–396, and [18], 424–442. 21. O.H. Ibarra, S. Woodworth, F. Yu, A. P˘aun: On spiking neural P systems and partially blind counter machines. In Proc. UC2006, York, LNCS 4135, Springer, 2006, 113–129. 22. M. Ionescu, A. P˘aun, Gh. P˘aun, M.J. P´erez-Jim´enez: Computing with spiking neural P systems: Traces and small universal systems. In Proc. DNA12 (C. Mao, Y. 280 Gh. P˘aun Yokomori, B.-T. Zhang, eds.), Seoul, June 2006, 32–42. 23. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. 24. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems with exhaustive use of rules. Intern. J. Unconventional Computing, to appear. 25. I. Korec: Small universal register machines. Theoretical Computer Science, 168 (1996), 267–301. 26. W. Maass: Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK, 8, 1 (2002), 32–36. 27. W. Maass: Paradigms for computing with spiking neurons. In Models of Neural Networks. Early Vision and Attention (J.L. van Hemmen, J.D. Cowen, E. Domany, eds.), Springer, Berlin, 2002, 373–402. 28. W. Maass, C. Bishop, eds.: Pulsed Neural Networks, MIT Press, Cambridge, 1999. 29. C. O’Dwyer, D. Richardson: Spiking neural nets with symbolic internal state. Available at http://people.bath.ac.uk/masdr/. 30. A. P˘aun, Gh. P˘aun: Small universal spiking neural P systems. In [17], Vol. II, 213– 234, and BioSystems, in press. 31. Gh. P˘aun: Membrane Computing – An Introduction. Springer, Berlin, 2002. 32. Gh. P˘aun: Languages in membrane computing. Some details for spiking neural P systems. In Proc. of Developments in Language Theory Conference, DLT 2006, Santa Barbara, CA, June 2006, LNCS 4036, Springer, Berlin, 2006, 20–35. 33. Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Spike trains in spiking neural P systems. Intern. J. Found. Computer Sci., 17, 4 (2006), 975–1002. 34. Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Infinite spike trains in spiking neural P systems. Submitted, 2006. 35. Gh. P˘aun, M.J. Perez-Jimenez, A. Salomaa: Bounding the indegree of spiking neural P systems. TUCS Technical Report 773, 2006. 36. Gh. P˘aun, M.J. P´erez-Jim´enez, A. Salomaa: Spiking neural P systems. An early survey. Intern. J. Fund. Computer Sci., 2007. 37. G. Perea, A. Araque: Communication between astrocytes and neurons: a complex language. J. Physiol. – Paris, 96 (2002), 199–207. 38. D. Sburlan: Promoting and Inhibiting Contexts in Membrane Computing. PhD Thesis, Univ. Sevilla, Spania, 2006. 39. I. Segev, E. Schneidman, Axons as computing devices: basic insights gained from models. J. Physiol. (Paris), 93 (1999), 263–270. 40. X. Shen, P. De Wilde: Long-term neuronal behavior caused by two synaptic modification mechanisms. Neurocomputing, to appear. 41. G.M. Shepherd: Neurobiology. Oxford University Press, NY Oxford, 1994. 42. N.J.A. Sloane, S. Plouffe: The Encyclopedia of Integer Sequences. Academic Press, New York, 1995. 43. The P Systems Web Page: http://psystems.disco.unimib.it. Membrane Computing Schema Based on String Insertions Mario J. P´erez-Jim´enez1, Takashi Yokomori2 1Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] 2Department of Mathematics Faculty of Education and Integrated Arts and Sciences Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku Tokyo 169-8050, Japan [email protected] Summary. In this note we introduce the notion of a membrane computing schema for string objects. We propose a computing schema for a membrane network (i.e., tissue-like membrane system) where each membrane performs unique type of operations at a time and sends the result to others connected through the channel. The distinguished features of the computing models obtained from the schema are: 1. only context-free insertion operations are used for string generation, 2. some membranes assume filtering functions for structured objects(molecules), 3. the generating model and accepting model are obtained in the same schema, and both are computationally universal, 4. several known rewriting systems with universal computability can be reformulated in terms of membrane computing schema in a uniform manner. The first feature provides the model with a simple uniform structure which facilitates a biological implementation of the model, while the second feature suggests further feasibility of the model in terms of DNA complementarity. Through the third and fourth features, one may have a unified view of a variety of existing rewriting systems with Turing computability in the framework of membrane computing paradigm. 1 Introduction In the theory of bio-inspired computing models, membrane systems (or P systems) have been widely studied from various aspects of the computability such as the optimal system designs, the functional relations among many ingredients in different levels of computing components, the computational complexity and so forth. 282 M.J. P´erez-Jim´enez, T. Yokomori Up to the present, major concerns are focused on the computational capability of multisets of certain objects in a membrane structure represented by a rooted tree, and there are a relatively limited amount of works in the membrane structure of other types (like a network or graph) on string objects and their languages; those are, for example, in the context of P system on graph structure ([15]), of the tissue P systems ([10]) and of spiking neural P systems ([2, 6]). On the other hand, in DNA computing theory, a string generating device called insertion-deletion system has been proposed and investigated from the uniqueness of non-rewriting nature in generating string objects. Among others, string insertion operation with no context is of our particular interests, because of the relevance to biological feasibility in terms of DNA sequences. In this paper, we are concerned with tissue-like membrane systems with string insertion operations and investigate the computational capability of those systems. By using the framework of tissue-like membrane systems, however, our major focus is on studying the new aspects of the computational mechanisms used in a variety of existing models based on string rewriting. To this aim, we propose the notion of a membrane computing schema which provides a unified view and framework to investigate new aspects of the variety of computational mechanisms. That is, by a membrane computing schema Π, we represent a core structure of the computing model Mat issue. At the same time, we also consider an interpretation Ito Πwhich specifies the details of M. Then, we have Mthat is embodied as a tissue-like membrane system I(Π) with string insertion operation. The advantages of this schematic approach to computing are the following: (1) High transparency of the computing mechanism is obtained from separating the skeletal (core) part from other detailed specificity of the computation. (2) Structural modularity of the computing model facilitates our better understanding of the computing mechanism. With this framework we will present not only new results of the computing models with universal computability but also a unified view of those models from the framework of tissue-like membrane system with string insertion operations. 2 Preliminaries We assume the reader to be familiar with all formal language notions and notations in standard use. For unexplained details, consult, e.g., [14, 16]. For a string xover an alphabet V(i.e., xin V∗), lg(x) denotes the length of x. For the empty string, we denote it by λ. For an alphabet V,V={a|a∈V}. A binary relation ρover Vis called an involution if ρis injective and ρ2is an identity (i.e., for any a∈V, if we write ρ(a) = a, then it holds that ρ(a) = a). A Dyck language Dkover V∪Vis a language generated by a context-free grammar G= ({S}, V, P, S), where P={S→SS, S →λ} ∪ {S→aSa |a∈V}and kis the cardinality of V. Membrane Computing Schema Based on String Insertions 283 An insertion system ([9]) is a triple γ= (V, P, A), where Vis an alphabet, A is a finite set of strings over Vcalled axioms, and Pis a finite set of insertion rules. An insertion rule is of the form (u, x, v), where u, x, v ∈V∗. We define the relation 7→ on V∗by w7→ ziff w=w1uvw2and z=w1uxvw2for some insertion rule (u, x, v)∈P,w1, w2∈V∗. As usual 7→∗denotes the reflexive and transitive closure of 7→. The insertion language generated by γis defined as follows: L(γ) = {w∈V∗|s7→∗w, s ∈A}.An insertion rule of the form (λ, x, λ) is said to be context-free, and we denote it by λ→x. We denote by RE, CF, LIN and RG the families of recursively enumerable languages, of context-free languages, of linear languages, and of regular languages, respectively. Amatrix grammar with appearance checking is a construct G= (N, T, S, M, F), where N, T are disjoint alphabets, S∈N,Mis a finite set of sequences of the form (A1→x1,..., An→xn), n≥1, of context-free rules over N∪T(with Ai∈N, xi∈(N∪T)∗, in all cases), and Fis a set of occurrences of rules in M (we say that Nis the nonterminal alphabet, Tis the terminal alphabet, Sis the axiom, while the elements of Mare called matrices). For w, z ∈(N∪T)∗we write w=⇒zif there is a matrix (A1→x1, . . . , An→ xn) in Mand the strings wi∈(N∪T)∗,1≤i≤n+1, such that w=w1, z =wn+1, and, for all 1 ≤i≤n, either wi=w0 iAiw00 i, wi+1 =w0 ixiw00 i, for some w0 i, w00 i∈ (N∪T)∗, or wi=wi+1, Aidoes not appear in wi, and the rule Ai→xiappears in F. (The rules of a matrix are applied in order, possibly skipping the rules in F if they cannot be applied; we say that these rules are applied in the appearance checking mode.) If F=∅, then the grammar is said to be without appearance checking (and Fis no longer mentioned). We denote by =⇒∗the reflexive and transitive closure of the relation =⇒. The language generated by Gis defined by L(G) = {w∈T∗|S=⇒∗w}. The family of languages of this form is denoted by MATac. When we use only grammars without appearance checking, then the obtained family is denoted by MAT . It is known that MAT ⊂MATac =RE. A matrix grammar G= (N, T, S, M, F) is said to be in the binary normal form if N=N1∪N2∪ {S, #}, with these three sets mutually disjoint, and the matrices in Mare of one of the following forms: 1. (S→XA),with X∈N1, A ∈N2, 2. (X→Y, A →x),with X, Y ∈N1, A ∈N2, x ∈N2∪N2 2∪T∪ {λ}, 3. (X→Y, A →#),with X, Y ∈N1, A ∈N2, 4. (X→λ, A →x), with X∈N1, A ∈N2,and x∈T∪ {λ}. Moreover, there is only one matrix of type 1 and Fconsists exactly of all rules A→# appearing in matrices of type 3; # is a trap-symbol, once introduced, it is never removed. A matrix of type 4 is used only once, at the last step of a derivation. For each matrix grammar (with appearance checking) there effectively exists an equivalent matrix grammar (with appearance checking) in the binary normal 284 M.J. P´erez-Jim´enez, T. Yokomori form. (Note that the definition of the binary normal form presented here is a variant of the one in [4].) Arandom context grammar is a construct G= (N, T, S, P ), where N, T are disjoint alphabets, S∈N,Pis a finite set of rules of the form (A→x, Q, R), where A→xis a context-free rule (A∈N, x ∈(N∪T)∗), Qand Rare subsets of N. For α, β ∈(N∪T)∗we write α=⇒βiff α=uAv,β=uxv for some u, v ∈(N∪T)∗, (A→x, Q, R)∈P, all symbols of Qappear in uv, and no symbol of Rappears in uv. We denote by =⇒∗the reflexive and transitive closure of the relation =⇒. The language generated by Gis defined by L(G) = {w∈T∗|S=⇒∗w}.The family of languages of this form is denoted by RC. It is known that RC =RE ([4]). 3 Membrane Computing Schema, Interpretation and Languages We now introduce the notion of a membrane computing schema in a general form, then we will present a restricted version, from which a variety of specific computing models based on insertion operations and filtering can be obtained in the framework of a tissue-like membrane computing. That is, a membrane computing schema is given as a skeletal construct consisting of a number of membranes connected with synapses (or channels) whose structure may be taken as a kind of tissue P systems (e.g., [10]). 3.1 Membrane Computing Schema Amembrane computing schema of degree (k, p) is a construct Π= (V, T, Syn, Com, Ope, Fil, is, Out), where: (i) Vis a finite alphabet with an involution relation ρcalled the working alphabet. (ii) Tis a subset of Vcalled the terminal alphabet. (iii) Syn ⊆(Com×Ope)∪(Ope×Com)∪(Com×(SubFil∪{SF}))∪({FF}×Com) ∪(SubFil ×Ope)∪ {(SF, F F),(FF, Out)}, where Com ={Com1,···, Comp}called a set of communication cells, Ope ={Ope1,···, Opek}called a set of operation cells, Fil ={SF, F F} ∪ SubFil called a set of filtering cells, where SubFil ={FF1,···, FFt}called a set of subfilter cells. Syn determines the tissue membrane structure of Π. (See Figure 1. In the figure, the thick arrow indicates multiple arrows of one-way or two-way directions.) Membrane Computing Schema Based on String Insertions 285 (iv) Each cell Comiserves as a communication channel. That is, any string xin the cell Comiis sent out to all the cells indicated by Syn(Comi). (v) Each cell Opejconsists of a finite number of rules {σj1,···, σjs}, where each σji is a string insertion operation of the form : λ→u, where u∈V∗. (vi) SF and FF, called structured filter and final filter, are associated with two languages LSF and LF F over V, respectively. Further, each cell FFi, called subfilter, is also associated with a language LF Fi. (vii) is(= Com1) is the distinguished cell (to designate some specific role). (viii) Out is the output cell (for obtaining the outputs). 3.2 Interpretation of Π In order to embody a membrane computing schema Π, we need to give more information about Πwhich specifies each operation in Ope, and materializes SF and FF. Let us consider such an interpretation Ito the schema Πwhich enables us to have a computing model I(Π) that is feasible in a practical sense. [Notation] For any xin Com ∪SubFil ∪ {FF}, let Syn(x) = {j|(x, yj)∈ Syn}and for any yin Ope ∪SupF il ∪{SF }, let Syn−1(y) = {i|(xi, y)∈Syn}. (Note that both Syn(x) and Syn−1(y) refer to sets of indices.) Formally, an interpretation I to Πis a construct I= ({R1,···, Rk}, LSF , LF F ,{LF Fi|1≤i≤t}), where (i) Rispecifies a set of insertion operations used in Opei(for i= 1,···, k) (ii) LSF (LF F ) materializes a concrete specification about the function of SF (FF, respectively). In practical operational phases (described below), we assume the following: •In the cell SF, each string is assumed to form a certain structure (e.g., structured molecule based on hybridization in terms of H-bonds via minimal energy principle). SF takes as input a string uover Vand allows it to filter through if it is in LSF (otherwise, the string uis lost). Then, after building up a structured form s(u) of u,SF removes all parts of structures from s(u) and produces as output the concatenation of all remaining strings. The output vis sent out to the cell FF. •FF receives as input a string vover V(from SF). A string vfilters through if it is in LF F and is sent out to Out. Otherwise, it is sent out to all cells indicated by Syn(FF). •Each F Fireceives as input a string uover V. Then, a string vfilters through if it is in LF Fiand is sent out to all cells indicated by Syn(FFi). Otherwise, it is lost. •Filtering applies simultaneously to all strings in the filtering cell. Note that in the case SubFil is empty in a given Π, an interpretation to Πis simply written as I= ({R1,···, Rk}, LSF , LF F ). 286 M.J. P´erez-Jim´enez, T. Yokomori Fig. 1. Modular Structure of Membrane Network in Π 3.3 Transitions and Languages Given a schema Πand its interpretation I, we now have a membrane system I(Π) based on string insertions. In what follows, we define a transition sequence of I(Π) and the language associated with I(Π). The (p+ 1)-tuple of languages over Vrepresented by (L1,...,Lp, Lout) constitutes a configuration of the system, where each Lirepresents the set of all strings in the cell Comi(for all i= 1,···, p), and Lout is the set of strings presented in the output cell at some time instance. Let C1= (L1,...,Lp, Lout) and C2= (L0 1,...,L0 p, L0 out) be two configurations of the system. We define one transition from C1to C2in the following steps: (0) Pre-checking Step: For each `= 1,···, t, let Syn−1(F F`) = {`1,···, `q} and consider L[`] = ∪q i=1L`i. Then, each cell FF`filters out all strings of L[`] that are not in LF F`, and all strings that have passed through are sent to all the cells indicated by Syn(F F`). (In the case of t= 0, this step is skipped.) (1) Evolution Step: For each j= 1,···, k, let σj1,···, σjs be all the operations given in Opej. Suppose that we apply operations σji :λ→uji (1 ≤i≤s) to a string v which means that each σji is applied to vsimultaneously. Further, when we apply Membrane Computing Schema Based on String Insertions 287 σji to v, the location in vto insert uji is nondeterministically chosen and the result σji(v) is considered as the set of all possible strings obtained from vby σji. (Note that if two or more rules share the same location to insert, then all possible permutations of those rules are considered to apply to the location.) The result of such an application of all operations in Opejto vis denoted by Opej(v). Let L(j) = ∪t m=1Ljm, where Syn−1(Opej) = {j1,···, jt}. Then, the total result performed by Opejto L(j) is defined as Opej(L(j)) = ∪v∈L(j)Opej(v). This result is then sent out to all cells indicated by Syn(Opej) simultaneously. (2) Filtering Step: For each i= 1,···, p, let ˜ Li=∪r n=1Opein(L(in)), where Syn(Comi) = {i1,···, ir}. Further, let Le=∪g n=1 ˜ Lin, where Syn−1(SF ) = {i1,···, ig}. SF takes as input the set Leand produces as output a set of strings Lf. (Recall that in the cell SF , each string uis assumed to form a certain structure, and the output of SF is the reduced string by removing structural parts from uin LSF .) Then, SF sends out Lfto FF. (Any element of Lethat was filtered off by SF is assumed to be lost.) Finally, the cell FF filters out strings of Lfdepending upon whether they are in LF F or not. All strings in Lfthat passed through F F are sent out to Out, while others are simultaneously sent to Comifor all i∈Syn(F F) or they are all lost if Syn(FF) = ∅. Let Lff be the set of all strings that were filtered off by FF. Then, we define C2= (L0 1,...,L0 p, L0 out) by setting for each i= 1,···, p L0 i=Lff ,if i∈Syn(FF), ˜ Li,otherwise. Further, let L0 out =Lout ∪Lf(Out), where Lf(Out) = Lf−Lff (the set of all stings that have passed through F F and been sent to Out). Remarks. (1) Each cell in Com not only provides a buffer for storing intermediate results in the computation process but also transmits them to the cells specified by Syn. (2) The system has a global clock and counts time in such a way that every cell (including communication cells) takes one unit time to perform its task irrespective of the existence of strings in it, while a pre-checking step by a subfilter cell FFiis assumed to be executed within the unit time for its corresponding operation cells in Syn(F Fi). Let Ibe an interpretation of Π. When we have a transition from C1to C2of I(Π), we write C1=⇒C2. A configuration C0= ({w},∅,···,∅), where w∈V∗, is called the initial configuration. A sequence of transitions between configurations of the system I(Π), starting from the initial configuration, is called a computation of I(Π). 294 M.J. P´erez-Jim´enez, T. Yokomori From this simpler schema Π2, we can induce a family of computing devices I(Π2) (with an appropriate interpretation I) that can characterize RE. (Note that Π2 is nothing but a schema Π1,0.) Fig. 4. Membrane Computing Schema: Π2 Theorem 5.3 There exists I0 Gsuch that RE =LMSg(Π2,I0 G). Proof sketch. Let Lbe any language in RE that is generated by a Chomsky type- 0 grammar G= (V, T, S, P ). Then, consider the following interpretation I0 G= ({RG}, LSF , LF F ), where (i) For each r:u→vin P, construct Rr={λ→vr, λ →uRr}, and let RG=∪r∈PRr. (ii) LSF adopts the Dyck language Dn, where n=|N∪T∪ {r|r∈P}|. (iii) LF F is given as T∗, so that only strings in T∗can pass through F F and are sent out to Out. Consider a transition sequence C0= ({S},∅) =⇒nCn= (L1,n, L(n) out). Then, for any α∈(N∪T)∗and n≥0, it holds that α∈L1,n iff S=⇒nαin G. Thus, we have that L(G) = Lg(I0 G(Π2)). (The proof is based on the fact that each recursively enumerable language Lcan be represented in the form L=h(L0∩Dk)), where L0 is an insertion language, his a projection and Dkis a Dyck language. (Theorem 3.1 in [13]). In order to understand the idea of the proof, it would be helpful to Membrane Computing Schema Based on String Insertions 295 note that RGin Com1generates the insertion language L0, while a pair of SF and FF plays the same role as a pair of Dkand h.) 2 6 Concluding Remarks In this paper we have introduced the notion of a membrane computing schema and showed that several known computing models with the universal computability can be reformulated in a uniform manner in terms of the framework of the schema together with its interpretation. A similar idea in the context of grammar schema has been proposed and discussed in [1, 5] to prove the computational completeness of new type of P systems based on the framework of the random context grammars for both string and multiset languages. (Note that the definition of random context in those papers is not on a string to be rewritten but on the applicability of rules to rewrite, different from the standard notion.) As for the communication by sending objects and the use of filtering function, there are several papers that have been devoted to studying the computational powers of communicating distributed H systems (e.g., [3, 11]), and of the hybrid networks of evolutionary processors (e.g., [7, 8]). Table 1 summarizes the results we have obtained. From the table, one can have a unified view of a variety of computing models based on string rewriting. For example, it is seen that there exists a trade-off between the complexity of network structure in the schema and the complexity of the filtering SF. More specifically, for new terminologies, Lis a star language iff L=F∗for some finite set F. Further, Lis an occurrence checking language iff L=V∗F V ∗ for some finite set F. Then, it should be noted that (i) LGis a finite union of occurrence checking languages, (ii) Lsand Lmare star languages, (iii) Lriis a finite intersection of occurrence checking languages and their complements, (iv) Lmiis the complement of an occurrence checking language. Since Π0(or Π1) is more complex than Π2, one may see a trade-off between the complexity of the schema and that of SF , telling that LGfor single (or Lmat for multiple) hairpin checking is simpler than Dkfor nested hairpin checking. This kind of trade-off can also be seen in complexity between a series of schemas (Π1, Π1.5, Π2) and the corresponding SFs (Lm, Lmat, Dk). It should be remarked that if we start with a programmed context-free grammar Gpr ([4]), then we have the result that RE =LMSg(Π1,IGpr ), where an interpretation IGpr consists of Lm(for SF), T∗(for FF) and Lmi(for F Fi), which suggests that programmed context-free grammars can be regarded as hybrid systems between matrix grammars with appearance checking and random context grammars. 296 M.J. P´erez-Jim´enez, T. Yokomori Table 1 Schema SF FF SubFil Chomsky type-0 Π0LG(∈RG)T∗(N.A.) Grammar or Lmir (∈LIN ) Turing Π0LM(∈RG)V∗F V ∗(N.A.) Machine or Lmir (∈LIN ) Random Context Π1Lm(∈RG)T∗Lri(∈RG) Grammar Matrixac Π1.5Lmat =LsLm(∈RG)T∗Lmi(∈RG) Grammar Chomsky type-0 Π2Dk(∈CF )T∗(N.A.) Grammar In this paper we have just made the first step in the new direction towards understanding and characterizing the nature of the Turing computability from the novel viewpoint of modularity in the membrane computing schema. There remain many questions for the future works: •It would be the most interesting to study the relation between the complexity of the language classes and that of SF within a given schema. For instance, we can show that within the schema Π2,CF can be characterized by star (regular) languages for SF. •Instead of insertion operations we adopted in this paper, what kind of operations can be considered for the unique operation in the cells Ope? What kind of different landscape of the computing mechanisms can be seen from the new schema? References 1. M. Cavaliere, R. Freund, M. Oswald, D. Sburlan: Multiset random context grammars, checkers, and transducers. In Fourth Brainstorming Week on Membrane Computing (M.A. Guti´errez-Naranjo, Gh. P˘aun, A. Riscos-N´u˜nez, F.J. Romero-Campero, eds.), Fenix Editora, Sevilla, 2006, Vol. 1, 113–131. 2. H. Chen, R. Freund, M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez: On string languages generated by spiking neural P systems. In Fourth Brainstorming Week on Membrane Computing (M.A. Guti´errez-Naranjo, Gh. P˘aun, A. Riscos-N´u˜nez, F.J. Romero-Campero, eds.), Fenix Editora, Sevilla, 2006, Vol. 1, 169–193. 3. E. Csuhaj-Varju, L. Kari, Gh.P˘aun: Test tube distributed systems based on splicing. Computers and AI, 15, 2-3 (1996), 211–232. 4. J. Dassow, Gh. P˘aun: Regulated Rewriting in Formal Language Theory. Springer- Verlag, Berlin, 1989. 5. R. Freund, M. Oswald: Modeling grammar systems by tissue P systems working in the sequential mode. In Proc. of Grammar Systems Workshop, Budapest, 2004. 6. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. Membrane Computing Schema Based on String Insertions 297 7. M. Margenstern, V. Mitrana, M.J. P´erez-Jim´enez: Accepting hybrid networks of evolutionary processors. Lecture Notes in Computer Science, 3384, Springer-Verlag, Berlin, 2005, 235–246. 8. C. Martin-Vide, V. Mitrana, M.J. P´erez-Jim´enez, F. Sancho-Caparrini: Hybrid networks of evolutionary processors. In Proc. of GECCO, Lecture Notes in Computer Science, 2723, Springer-Verlag, Berlin, 2003, 401–412. 9. C. Martin-Vide, Gh. P˘aun, A. Salomaa: Characterizations of recursively enumerable languages by means of insertion grammars. Theoretical Computer Science, 205 (1998), 195–205. 10. C. Martin-Vide, Gh. P˘aun, J. Pazos, A. Rodriguez-Paton: Tissue P systems, Theoretical Computer Science, 296 (2003), 295–326. 11. Gh. P˘aun: Distributed architectures in DNA Computing based on splicing: Limiting the size of components. In Proc. Conf. Unconventional Models of Computation (C.S. Calude, J. Casti, M.J. Dinneen, eds.), Springer-Verlag, Berlin, 1998, 323–335. 12. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002. 13. Gh. P˘aun, M.J. P´erez-Jim´enez, T. Yokomori: Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems. Submitted. 2007. 14. Gh. P˘aun, G. Rozenberg, A. Salomaa: DNA Computing. New Computing Paradigms. Springer-Verlag, Berlin, 1998. 15. Gh. P˘aun, Y. Sakakibara, T. Yokomori: P systems on graph of restricted forms. Publicationes Mathematicae Debrecen, 60 (2002), 635–660. 16. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. Springer-Verlag, Berlin, 1997. A Software Tool for Dealing with Spiking Neural P Systems Daniel Ram´ırez-Mart´ınez, Miguel A. Guti´errez-Naranjo Research Group on Natural Computing University of Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain [email protected], [email protected] Summary. Software simulators for P system are nowadays the main tool to carry out experiments in the field of Membrane Computing. Although the simulation of a P system is a quite complex task, current simulators have been successfully used for pedagogical purposes and also as assistant tools for researchers. In this paper we present a first software tool for dealing with Spiking Neural P Systems. This tool outputs the transition diagram of a given system in a step-by-step mode. The code is modular and flexible enough to be adapted for further research tasks. 1 Introduction Membrane Computing was introduced by Gh. P˘aun in [11], starting from the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations1. Since then, a large number of variants and subvariants have been considered, concerning both the syntax and the semantics of the model. The devices of this model are called generically P systems. Roughly speaking, a P system consists of a membrane structure, in the compartments of which one places multisets of objects which evolve according to given rules. The evolution of the rules is usually performed in a synchronous non-deterministic maximally parallel manner, but this can vary depending on the model. Let us recall here three of the main variants of P systems: Cell-like P systems, Tissue-like P Systems, and Spiking Neural P Systems. In the cell-like model of P systems, membranes are hierarchically arranged in a tree-like structure (see [11]). The biological inspiration is the morphology of cell, where small vesicles are surrounded by larger ones. This biological structure can be abstracted into a tree-like graph, where the root of the graph represents the 1The foundations of Membrane Computing can be found at [12] and updated bibliography at [16]. 300 D. Ram´ırez-Mart´ınez, M.A. Guti´errez-Naranjo skin of the cell (the outermost membrane), the leaves represent membranes that do not contain other ones (elementary membranes) and two nodes in the graph are connected if they represent two membranes such that one of them contains the other one. In the tissue P systems ([9, 10]) we consider a general graph instead of a treelike membrane structure, where the nodes can be considered as processors and the edges as connections among them in order to share information. This model has two biological inspirations (see [10]): intercellular communication and cooperation between neurons. The common mathematical model of these two mechanisms is a net of processors dealing with symbols and communicating these symbols along channels specified in advance. The communication among cells is based on symport/antiport rules: Symport rules move objects across a membrane together in one direction, whereas antiport rules move objects across a membrane in opposite direction. Spiking neural P systems (SN P systems, for short) were introduced in [6]. The aim of this new model was to incorporate in membrane computing ideas specific to spiking neurons; the intuitive goal was to have (1) a tissue-like P system with (2) only one (type of) object(s) in the cells, the spike, with (3) specific rules for evolving populations of spikes, and (4) making use of the time as a support of information2. Irrespectively of the selected approach, it is usually a complex task to predict or to guess how a P system will behave. Moreover, as there do not exist, up to now, implementations in laboratories (neither in vitro nor in vivo nor in any electronic media), it seems natural to look for software tools that can be used as assistants that are able to simulate computations of P systems. The first software simulator for P systems appeared in 2000. It was written by Mihaela Malit¸a [8] in LPA-Prolog and, since then, more than ten software simulators have been presented (see [7] and references therein). Their common purpose is the better understanding of the computational process of P systems, for pedagogical purposes as well as assistant for researchers. Among these simulators, we can find simulators for transition P system (as Malit¸a’s one) or simulators able to deal with P Systems with active membranes (as Ciobanu and Paraschiv’s simulator [3]). Some of them explore new architectures looking for increasing the speed of the computation like Ciobanu and Wenyuan’s simulator [5] based on parallel architecture. Others put the stress on a simulation closer to biological laws, as the simulator by the Group for Models of Natural Computing [17] in Verona, based on the implementation of the metabolic algorithm introduced in [1]. In this paper we present a new tool which is born with the hope of becoming a tool for the creativity in Membrane Computing. It deals with SN P systems, and to the best of our knowledge, so far no other software tool has been presented for dealing with such systems. Our simulator shares the common purpose of the 2In the next section we will give a brief introduction of some concepts related to SN P Systems, a detailed description can be found at [13] and the references therein. A Software Tool for Dealing with Spiking Neural P Systems 301 others simulators: the understanding of the computational process of P systems and becoming an assistant for researchers. It receives the description of an SN P System and outputs its transition diagram with an user friendly interface. The paper is organized as follows. First we recall some definitions related to SN P systems. Then, the simulator is presented and some features of its implementation are given. Section 4 provides an example of how the simulator works and finally, in the last section some remarks and future work lines are presented. 2 The Model An SN P system consists of a set of neurons placed in the nodes of a directed graph and sending signals (called spikes) along the arcs of the graph (called synapses). The objects evolve according to a set of rules (called spiking rules). The idea is that a neuron containing a certain amount of spikes can consume some of them and produce other ones. The produced spikes are sent (maybe with a delay of some steps) to all neurons to which a synapse exists outgoing from the neuron where the rule was applied. There also are forgetting rules. By the application of these rules no spikes are sent, simply some spikes are removed from the neuron where the rule was applied. A global clock is assumed and in each time unit each neuron which can use a rule should do it, but only (at most) one rule is used in each neuron. One of the neurons is considered to be the output neuron, and its spikes are also sent to the environment. Formally, an SN P system of degree m≥1, is a construct of the form Pi = (O, σ1,...,σm, syn, out), where: •O={a}is the alphabet (the object ais called spike); •σ1,...,σmare neurons, of the form σi= (ni, Ri) with i∈ {1, . . . , m}where: –ni≥0 is the initial number of spikes contained by the neuron; –Riis a finite set of rules of the form: E/ac→ap;d where Eis a regular expression with athe only symbol used, c≥1 and p, d ≥0, with c≥p; if p= 0, then d= 0 too. •syn ⊆ {1,2,...,m} × {1,2, ..., m}with (i, i)6∈ syn for i∈ {1, . . . , m} (synapses); •out ∈ {1,2,...,m}is the output neuron. Notice that only one neuron can send spikes to the environment. For the sake of simplicity, if p=d= 0, the rule is written as E/ac→λinstead of E/ac→a0; 0. This type of rules is called forgetting rules. If L(E) = {ac}then the rules are written in the simplified form ac→ap;dand ac→λ. 302 D. Ram´ırez-Mart´ınez, M.A. Guti´errez-Naranjo ' & $ % ' & $ % ' & $ % -  @@@@ @R @ @ @ @ @I      - 12 3 a r11 :a→a; 0 r12 :a→a; 1 a r21 :a→a; 0 r22 :a→a; 1 a2 r31 :a→a; 0 r32 :a2→λ Fig. 1. An example of SN P system With respect to the application of the rules, if the neuron σicontains kspikes, ak∈L(E) and k≥c, then the rule E/ac→ap;d∈Ri(with p≥1) can be applied; applying it means that cspikes are consumed, only k−cremain in the neuron and it produces pspikes after dtime units. If d= 0, then the spikes are emitted immediately, otherwise the spikes are emitted after dsteps. In the case d≥1, if the rule is used in step t, then in steps t, t + 1, t + 2, . . . , t +d−1 the neuron is closed, and it cannot receive new spikes (if a neuron has a synapse to a closed neuron and sends spikes along it, then the spikes are lost). In step t+d, the neuron spikes and becomes again open, hence can receive spikes. The pspikes emitted by a neuron σiare replicated and they go to all neurons σjsuch that (i, j)∈syn (each σjreceives pspikes). If the rule is a forgetting one, then no spike is emitted and the neuron cannot be closed. In each time unit, in each neuron which can use a rule, a rule must be used non-deterministically chosen if several rules are applicable. Note that each neuron processes sequentially its spikes, using only one rule in each time unit. During the computation, a configuration is described by both the number of spikes present in each neuron and by the number of steps to count down until it becomes open (this number is zero if the neuron is open, for example, in the initial configuration). Any sequence of transitions starting in the initial configuration is called a computation. A computation halts if it reaches a configuration where all neurons are open and no rule can be used. The graphical representation of an SN P system is rather intuitive: the neurons are represented by membranes, placed in the nodes of a directed graph whose arrows represent the synapses. Figure 1 shows an example of the graphical representation of an SN P System taken from [2]. In the graphical representation of our software tool, the environment is also represented by a membrane and an arrow exits from the output neuron, pointing A Software Tool for Dealing with Spiking Neural P Systems 303 Fig. 2. Screen capture of the designer interface to this membrane; in each neuron we specify the rules and the spikes present in the initial configuration. Figure 2 shows a screen capture of the designer module of our software by showing our graphical representation of the example. The transition diagram of an SN P System is also a graph where the nodes are configurations and an arrow is drawn between two nodes/configurations. We draw an arrow if a direct transition is possible between them. Our software also provides labels to the arcs with information about the rules used in the transition. 3 The Simulator The software tool3for simulating the evolution of an SN P system is composed by the integration of three modules: •A Graphical User Interface (GUI) which allows an easy interface to users, decoupling experimentation and simulation from programming. This module is written in XBase++ [15], which is an object oriented language to program database oriented graphic applications. 3The simulator is available at [16]. 310 D. Ram´ırez-Mart´ınez, M.A. Guti´errez-Naranjo h3/0,0/0,1/0i h4/0,0/0,0/0i h2/0,0/1,0/0i h2/0,1/0,2/0i + N q - 10,20,31 10 21 32 10 2s 30 10 22 32 h1/0,0/1,1/0ih1/0,1/0,1/0i ? } y 11 21 31 11,22,31 11 2s 31 h0/1,0/0,1/0ih0/1,0/1,0/0i h1/0,1/0,2/0i 7 z Y 12 2s 31 1s 20 31 12 21 31 12 22 31 ?q y1s 2s30 12 22 32 12 21 32 h0/0,0/1,1/0i h2/0,0/0,1/0i h3/0,0/0,0/0i )  ? 11 22 32 10 2s 31 10 20 31 '$ ? 11,21,32 Fig. 6. The transition diagram from [13] The current version of the simulator follows the same line: we keep a high degree of expressivity, looking for a friendly interface with the user, but some technical details can be improved. As pointed out above, one of them is the possibility of fixing a bound of the number of steps performed from the initial configuration in order to avoid that the software collapses. Anther point is to extend the definition of the applicability of rules, since in the current version only a restricted definition is used. [Document text truncated for crawler view.]