Eighteenth Brainstorming Week on Membrane Computing Sevilla, February 4 - 7, 2020 : RGNC REPORT 1/2020

Eighteenth Brainstorming Week on Membrane Computing Sevilla, February 4 – 7, 2020 David Orellana-Mart´ın Gheorghe P˘aun Agust´ın Riscos-N´u˜nez Ignacio P´erez-Hurtado Editors Eighteenth Brainstorming Week on Membrane Computing Sevilla, February 4 – 7, 2020 David Orellana-Mart´ın Gheorghe P˘aun Agust´ın Riscos-N´u˜nez Ignacio P´erez-Hurtado Editors RGNC REPORT 1/2020 Research Group on Natural Computing Universidad de Sevilla Sevilla, 2020 c Autores (All rights remain with the authors) ISBN: XXX-XX-XXXXX-X Printed by: Artes Gr´aficas Moreno, S.L. http://www.agmoreno.net/ Preface The Eighteenth Brainstorming Week on Membrane Computing (BWMC) was held in Sevilla, from February 4 to 7, 2020, hosted by the Research Group on Natural Computing (RGNC) from the Department of Computer Science and Artificial Intelligence of Universidad de Sevilla. The first edition of BWMC was organized at the beginning of February 2003 in Rovira i Virgili University, Tarragona, and all the next editions have been taking place in Sevilla since then, always at the beginning of February. In the style of previous meetings in this series, was conceived as a period of active interaction among the participants, with the emphasis on exchanging ideas and cooperation. Several “provocative” talks were delivered, mainly devoted to open problems, research topics, announcements, conjectures waiting for proofs, or ongoing research works in general (involving both theory and applications). Joint work sessions were scheduled on the afternoons to allow for collaboration among the about 25 participants – see the list in the end of this preface. The papers included in this volume, arranged in the alphabetic order of the authors, were collected in the form available at a short time after the brainstorming; several of them are still under elaboration. The idea is that the proceedings are a working instrument, part of the interaction started during the stay of authors in Sevilla, meant to make possible a further cooperation, this time having a written support. A selection of papers from this volume will be considered for publication in the new Journal of Membrane Computing, published by Springer-Verlag (www.springer.com/41965). Other papers elaborated during the 2020 edition of BWMC will be submitted to other journals or to suitable conferences. The reader interested in the final version of these papers is advised to check the current bibliography of membrane computing available in the domain website http://ppage.psystems.eu. *** vi Preface The list of participants as well as their email addresses are given below, with the aim of facilitating the further communication and interaction: 1. Artiom Alhazov, Institute of Mathematics and Computer Science of Academy of Sciences of Moldova, Moldova [email protected] 2. Jos´e A. Andreu-Guzm´an, Universidad de Sevilla, Spain [email protected] 3. Daniel Cagigas-Mu˜niz, Universidad de Sevilla, Spain [email protected] 4. Daniel Cascado-Caballero, Universidad de Sevilla, Spain [email protected] 5. Rodica Ceterchi, University of Bucharest, Romania rceterc[email protected] 6. L´udek Cienciala, Silesian University in Opava, Czech Republic [email protected] 7. Lucie Ciencialov´a, Silesian University in Opava, Czech Republic lucie.ciencialov[email protected] 8. Rudolf Freund, Technological University of Vienna, Austria [email protected] 9. Carmen Graciani, Universidad de Sevilla, Spain [email protected] 10. Ricardo Graciani-D´ıaz, Universitat de Barcelona, Spain [email protected] 11. Sergiu Ivanov, IBISC, Universit´e ´ Evry, Universit´e Paris-Saclay, France [email protected] 12. Pramod Kumar Sethy, E¨otv¨os Lor´and University, Hungary pkseth[email protected]u 13. Albert J. Li˜n´an-Maho, ERIC LifeWatch, Universidad de Sevilla, Spain [email protected] 14. Miguel A. Mart´ınez-del-Amor, Universidad de Sevilla, Spain [email protected] 15. David Orellana-Mart´ın, Universidad de Sevilla, Spain [email protected] 16. Gheorghe P˘aun, Romanian Academy, Romania [email protected] 17. Ignacio P´erez-Hurtado, Universidad de Sevilla, Spain p[email protected] 18. Mario de J. P´erez-Jim´enez, Universidad de Sevilla, Spain marp[email protected] 19. Agust´ın Riscos-N´u˜nez, Universidad de Sevilla, Spain [email protected] 20. Jos´e L. Rodr´ıguez-Andreu, ERIC LifeWatch, Universidad de Sevilla, Spain jlro[email protected] Preface vii 21. ´ Alvaro Romero-Jim´enez, Universidad de Sevilla, Spain romero.alv[email protected] 22. Luis Valencia-Cabrera, Universidad de Sevilla, Spain lv[email protected] 23. Daniel Valenta, University of Opava, Czech Republic [email protected] 24. Gy¨orgy Vaszil, University of Debrecen, Hungary vaszil.gy[email protected]u 25. Claudio Zandron, University of Milano-Bicocca, Italy [email protected] As mentioned above, the meeting was organized by the Research Group on Natural Computing from Universidad de Sevilla (http://www.gcn.us.es)– and all the members of this group were enthusiastically involved in this (not always easy) work. The meeting was partially supported from various sources: (i) Research Project TIN2017-89842-P cofinanced by Ministerio de Econom´ıa, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigaci´on (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union, (ii) VI Plan Propio, Vicerrectorado de Investigaci´on de la Universidad de Sevilla, and (iii) Department of Computer Science and Artificial Intelligence from Universidad de Sevilla. The Editors (Sep 2020) Contents Some open problems A. Alhazov .............................................................. 1 Alternative Space Definitions for P Systems with Active Membranes A. Alhazov, A. Leporati, L. Manzoni, G. Mauri, C. Zandron ............ 9 Catalytic P Systems with Weak Priority of Catalytic Over Non-catalytic Rules A. Alhazov, R. Freund, S. Ivanov ...................................... 21 P Systems with Limited Capacity A. Alhazov, R. Freund, S. Ivanov ...................................... 33 Contour Approximation with P Systems R. Ceterchi, D. Orellana-Mart´ın, G. Zhang ............................ 49 P Colonies and Reaction Systems L. Ciencialov´a, L. Cienciala, E. Csuhaj-Varj´u .......................... 63 Extracting Parallelism in Simulation Algorithms for PDP systems M. ´ A. Mart´ınez-del-Amor, A. Doncel-Ram´ırez, D. Orellana-Mart´ın, I. P´erez-Hurtado ....................................................... 79 An optimal solution to the SAT problem with tissue P systems D. Orellana-Mart´ın, L. Valencia-Cabrera, M.J. P´erez-Jim´enez ......... 91 Seven Research Suggestions Gh. P˘aun ............................................................. 101 Some open problems for application of spiking neural P systems H. Peng .............................................................. 107 Modelling of Grey Wolf Optimization Algorithm Using 2D P Colonies D. Valenta, L. Ciencialov´a, L. Cienciala .............................. 109 Author Index ......................................................... 123 6 Artiom Alhazov 3 Some questions from variety 1. Anti-membranes. Reminder: rules of types []h→[]j[]k, []h[]h0→λ; could also be with objects. A. Alhazov, R. Freund, S. Ivanov: (Tissue) P Systems with Anti-Membranes. In Seventeenth Brainstorming Week on Membrane Computing (OrellanaMart´ın, D.; P˘aun, Gh.; Riscos-N´u˜nez, A.; Andreu-Guzm´an, J. A., Eds.), Sevilla. RGNC report 1/2019, University of Seville, Artes Gr´aficas Moreno, S.L., 2019, 29–30. http://www.gcn.us.es/files/17bwmc/029_AntiMembranes. pdf and A. Alhazov, R. Freund, S. Ivanov: P Systems with Anti-Membranes. In Proceedings of the 20th International Conference on Membrane Computing, CMC20, Curtea de Arges ,(P˘aun, Gh., Ed.). Bibliostar, Rˆamnicu Vˆalcea, 2019, 249–256. http://membranecomputing.net/cmc20/pdf/procCMC20.pdf#page= 250 1) Can we still do anything non-trivial if changing membrane labels is forbidden? 2) Is it possible, e.g., to simulate boolean circuits? 3) What if we forbid changing labels but allow a limited (3?) number of polarizations? let’s say annihilation needs some form of polarization agreement 4) Descriptional complexity of a small universal NFPAMS 5) Which ingredients are needed to solve SAT with anti-membranes? 6) How we can exploit deeper membrane structures? For instance, annihilation of nested membranes outside-in performs an ordered sequence of membrane dissolutions. 7) antiMembranes for efficiency? In any way that is not a trivial translation of the previous research from objects to membranes. 2. Channels. For symport/antiport P systems, in tissue case, it is usually assumed that channels do not admit any parallelism. There has been a few exceptions. 1) Some Rudi’s talk with PPT slides many years ago, where cells were represented by huge colored circles, I do not remember the title. 2) A. Alhazov, R. Freund, M. Oswald: Tissue P Systems with Antiport Rules and Small Numbers of Symbols and Cells. In: De Felice C., Restivo A. (eds) Developments in Language Theory. DLT 2005. Lecture Notes in Computer Science 3572. Springer, Berlin, Heidelberg, 2005, 100-111. https: //doi.org/10.1007/11505877_9 , where in Ot0P, primed letter tindicated that it was allowed to have distinct channels (i, j) and (j, i). 3) A more recent paper H. Adorna, A. Alhazov, L. Pan, B. Song: Simulating Evolutional Symport/Antiport by Evolution-Communication and vice versa in Tissue P Systems with Parallel Communication. In: Gheorghe M., Rozenberg Some open problems 7 G., Salomaa A., Zandron C. (eds) Membrane Computing. CMC 2017. Lecture Notes in Computer Science 10725. Springer, Cham, 2018, 1-14. https: //doi.org/10.1007/978-3-319-73359-3_1 relating evolutional symport/antiport with evolution-communication – in order to make it possible having direct simulation with a slowdown by a factor of a constant, communication needed to be massively parallel. 4) Older research on neural P systems, probably by [Krishna,Rama], long time before spiking. . . anyway, that last one was quite a different model. - Parallel VS sequential channels in tP systems. Improve results with mcre from NP∪co−NP to PSPACE. 3. Global rules. considered by A. P˘aun and once briefly by myself. This relates to problem (Q6) in Gheorghe’s open problem list http://www.gcn.us.es/?q=18bwmc_ openproblems. If membrane structure is static and we do not care about descriptional complexity, making all rules global does not seem to restrict us at all: objects can always be renamed when moved, so they know where they are. However, the total number of rules in this reduction may increase, and this technique becomes more complicated, or even impossible, with dissolution. BTW, this may open an interesting discussion at solving hard problems in polytime. Besides, not all membranes are created equal: by definition, elementary membrane division is not applicable to membranes that are (currently) non-elementary, and the skin cannot be dissolved or divided (and sometimes it is forbidden for any object to enter it) - this trick might help distinguishing membranes when needed, however, requiring non-determinism or complicated simulation. On the other hand, with sufficient ingredients one working region is already enough, so we should stay in a restricted enough settings. A. P˘aun: On P Systems with Global Rules. In: Jonoska N., Seeman N.C. (eds) DNA Computing. DNA 2001. Lecture Notes in Computer Science, vol 2340. Springer, Berlin, Heidelberg, 2002, 329-339. https://doi.org/10. 1007/3-540-48017-X_31 A. Alhazov, R. Freund: On the Efficiency of P Systems with Active Membranes and Two Polarizations. In: Mauri G., P˘aun Gh., P´erezJim´enez M.J., Rozenberg G., Salomaa A. (eds) Membrane Computing. WMC 2004. Lecture Notes in Computer Science, vol 3365. Springer, Berlin, Heidelberg, 2005, https://doi.org/10.1007/978-3-540-31837-8_8 A. Alhazov, R. Freund, S. Ivanov: Length P Systems. Fundamenta Informaticae 134(1-2), 2014, 17-37. https://doi.org/10.3233/FI-2014-1088 4. Maximal consistency modes. Reminder: here applicability does not only depend on lhs. I have heard about a practical use of this mode in a BWMC2019 discussion from Agustin (though I forgot which application it was for, so I would not know what reference to cite). Usually in membrane computing rule applicability only depends on the left side of the rule (whether all reactants are present in the current configuration, 8 Artiom Alhazov and, possibly, whether some additional conditions are satisfied, e.g., promoters, inhibitors, etc.). Consider rules changing membrane polarization. Allow to apply multiple rules (maximal parallelism), as long as the polarization in their rhs is the same. Let me call it “polarization agreement”. Need to be precise, probably need to choose the polarization corresponding to at least one applied rule, if possible. Other examples of maximal consistency: - Parallel string rewriting without conflicts [D. Besozzi], many years ago, reference needed. - Rudi’s target agreement/label agreement, original reference needed. - Any other shared resource to agree upon? Overall, I believe this feature deserves more attention. 5. cP systems. = P systems with complex objects, see [Nicolescu]. Reminder: prolog-like rules using power of term rewriting and unification. Very powerful model, e.g., a solution of the Travelling Salesman Problem has been reported with five rules only [CooperNicolescu ACMC2017]. Some longer time ago the colleagues in my institute wanted to attack with P systems the problem of finding Gr¨obner basis. Unfortunately, the data structures that can be represented and efficiently processed by usual P systems are limited, and hence they are not suited well to work, e.g., with dynamic ordered lists of strings (a solution via Turing machine is not elegant). It turns out that cP systems are much more flexible in representing and efficiently processing complicated data structures. Some problems that have been addressed besides universality/computational completeness and NP-hard problems, by usual P systems: - sorting https://doi.org/10.1007/3-540-29937-8_8, - dictionary search and update http://univagora.ro/jour/index.php/ijccc/issue/download/44/pdf_ 165, - inflections http://www.math.md/publications/csjm/issues/v17-n2/10082/, - annotating affixes https://doi.org/10.1007/978-3-642-54239-8_7, - firing squad synchronization problem https://doi.org/10.1007/978-3-540-95885-7_9 (more problems and solutions can be found in Applications of Membrane Computing, 2005 and Membrane Computing Handbook). Need: more problems that are practical, well defined and sufficiently simple (simpler than Gr¨obner basis), to be attacked by cP systems, but not completely trivial (needing, say, more than two rules). Need: more problems that are practical, well defined and sufficiently simple (simpler than Gr¨obner basis), to be attacked by cP systems, but not completely trivial (needing, say, more than two rules). Alternative Space Definitions for P Systems with Active Membranes Artiom Alhazov1, Alberto Leporati2, Luca Manzoni3, Giancarlo Mauri2, and Claudio Zandron2 1Vladimir Andrunachievici Institute of Mathematics and Computer Science Academiei 5, Chis ,inău, MD-2028, Moldova [email protected] 2Dipartimento di Informatica, Sistemistica e Comunicazione (DISCo) Università degli Studi di Milano-Bicocca Viale Sarca 336, 20126 Milan, Italy. {alberto.leporati,giancarlo.mauri,claudio.zandron}@unimib.it 3Dipartimento di Matematica e Geoscienze Università degli Studi di Trieste [email protected] Summary. The first definition of space complexity for P systems was based on an hypothetical real implementation by means of biochemical materials, and thus it assumes that every single object or membrane requires some constant physical space. This is equivalent to using a unary encoding to represent multiplicities for each object and membrane. A different approach can also be considered, having in mind an implementation of P systems in silico; in this case, the multiplicity of each object in each membrane can be stored using binary numbers, thus reducing the amount of needed space. In this paper, we give a formal definition for this alternative space complexity measure, we define the corresponding complexity classes and we compare such classes both with standard space complexity classes and with complexity classes defined in the framework of P systems considering the original definition of space. Key words: Membrane Systems, Computational Complexity, Space Complexity 1 Introduction P systems with active membranes have been introduced in [6], considering the idea of generating new membranes through division of existing ones. The exponential amount of resources that can be obtained in this way, in a polynomial number of computation steps, naturally leads to the definition of new complexity classes to be compared with the standard ones. 10 A. Alhazov, A. Leporati, L. Manzoni, G. Mauri, C. Zandron Initially, the research activity focused on the investigation of time complexity, for the various classes of P systems that can be obtained by introducing different features. The first definition of space complexity for P systems has been introduced in [8], and it was based on an hypothetical real implementation by means of biochemical materials such as cellular membranes and chemical molecules. Under this assumption, it was assumed that every single object or membrane requires some constant physical space, and this is equivalent to using a unary encoding to represent multiplicities. A different approach can also be considered, focusing the definition on the simulative point of view. By considering an implementation of P systems in silico, it is not strictly necessary to store information concerning every single object: the multiplicity of each object in each membrane can be stored using binary numbers, thus reducing the amount of needed space. In this paper, we give a formal definition for this alternative space complexity measure, we define the corresponding complexity classes and we compare such classes both with standard space complexity classes and with complexity classes defined in the framework of P systems considering the original definition of space [8]. In particular, we will give partial results concerning the use of constant, polynomial or exponential amount of space, respectively. The paper is organized as follows. In Section 2 we recall some definitions concerning P systems with active membranes and space requirements in P systems computations. In Section 3, we introduce a different definition for measuring space (which we call binary space to underline that information concerning objects is stored in binary) and we give some results following immediately from this definition. In Section 4 we compare the new binary space complexity classes with standard complexity classes and with space complexity classes for P systems based on the standard definition of space. Finally section 5 draws some conclusions and presents some future research topics on this subject. 2 Basic definitions In this section, we shortly recall some definitions that will be useful while reading the rest of the paper. For a complete introduction to P systems, we refer the reader to The Oxford Handbook of Membrane Computing [7]. Definition 1. AP system with active membranes having initial degree d≥1is a tuple Π= (Γ, Λ, µ, wh1, . . . , whd, R), where: •Γis an alphabet, i.e., a finite non-empty set of symbols, usually called objects; in the following, we assume Γ={O1, O2, . . . , On} •Λis a finite set of labels for the membranes; •µis a membrane structure (i.e., a rooted unordered tree, usually represented by nested brackets) consisting of dmembranes, labelled by elements of Λin a one- Alternative Space Definitions for P Systems with Active Membranes 11 to-one way, defining regions (the space between a membrane and all membranes immediately inside it, if any); •wh1, . . . , whd, with h1, . . . , hd∈Λ, are strings over Γdescribing the initial multisets of objects placed in the dregions of µ; •Ris a finite set of rules over Γ. Membranes are polarized, that is, they have an attribute called electrical charge, which can be neutral (0), positive (+) or negative (−). A P system can made a computation step by applying its rules to modify the membrane structure and/or the membrane content.The following types of rules can be used during the computation: •Object evolution rules, of the form [a→w]α h They can be applied inside a membrane labelled by h, having charge αand containing at least an occurrence of the object a; the object ais rewritten into the multiset w(i.e., ais removed from the multiset in hand replaced by the objects in w). •Send-in communication rules, of the form a[ ]α h→[b]β h They can be applied to a membrane labelled by h, having charge αand such that the external region contains at least an occurrence of the object a; the object ais sent into hbecoming band, simultaneously, the charge of his changed to β. •Send-out communication rules, of the form [a]α h→[ ]β hb They can be applied to a membrane labelled by h, having charge αand containing at least an occurrence of the object a; the object ais sent out from hto the outside region becoming band, simultaneously, the charge of his changed to β. •Dissolution rules, of the form [a]α h→b They can be applied to a membrane labelled by h, having charge αand containing at least an occurrence of the object a; the membrane his dissolved and its contents are left in the surrounding region unaltered, except that an occurrence of abecomes b. •Elementary division rules, of the form [a]α h→[b]β h[c]γ h They can be applied to a membrane labelled by h, having charge α, containing at least an occurrence of the object abut having no other membrane inside (in this case the membrane is said to be elementary); the membrane is divided into two membranes having both label hand charges βand γ, respectively; the object ais replaced, respectively, by band cin the two new membranes, while the other objects in the initial multiset are copied to both membranes. •(Weak) Non-elementary division rules, of the form [a]α h→[b]β h[c]γ h These rules operate just like division for elementary membranes, but they can be applied to non–elementary membranes, containing membrane substructures and having a label h. Like the objects, the substructures inside the dividing membrane are replicated in the two new copies of it. 12 A. Alhazov, A. Leporati, L. Manzoni, G. Mauri, C. Zandron A configuration of a P system with active membranes is described by the current membrane structure (including the electrical charge of each membrane) and the multisets located in the corresponding regions. A computation step changes the current configuration according to the following set of principles: •Each object and membrane can be subject to at most one rule per step, except for object evolution rules (inside each membrane several evolution rules can be applied simultaneously). •The application of rules is maximally parallel: each object appearing on the left-hand side of evolution, communication, dissolution or division rules must be subject to exactly one of them (unless the current charge of the membrane prohibits it). The same principle applies to each membrane that can be involved in communication, dissolution, or division rules. In other words, the only objects and membranes that do not evolve are those associated with no rule, or only to rules that are not applicable due to the electrical charges. •When several conflicting rules can be applied at the same time, a nondeterministic choice is performed; this implies that, in general, multiple possible configurations can be reached as the result of a computation step. •In each computation step, all the chosen rules are applied simultaneously (in an atomic way). However, in order to clarify the operational semantics, each computation step is conventionally described as a sequence of micro-steps as follows. First, all evolution rules are applied inside the elementary membranes, followed by all communication, dissolution and division rules involving the membranes themselves; this process is then repeated to the membranes containing them, and so on towards the root (outermost membrane). In other words, the membranes evolve only after their internal configuration has been updated. For instance, before a membrane division occurs, all chosen object evolution rules must be applied inside it; in this way, the objects that are duplicated during the division are already the final ones. •The outermost membrane cannot be divided or dissolved, and any object sent out from it cannot re-enter the system again. Ahalting computation of the P system Πis a finite sequence of configurations C= (C0,...,Ck), where C0is the initial configuration, every Ci+1 is reachable from Civia a single computation step, and no rules of Πare applicable in Ck. A non-halting computation C= (Ci:i∈N)consists of infinitely many configurations, again starting from the initial one and generated by successive computation steps, where the applicable rules are never exhausted. P systems can be used as language recognizers by employing two distinguished objects yes and no; exactly one of these must be sent out from the outermost membrane, and only in the last step of each computation, in order to signal acceptance or rejection, respectively; we also assume that all computations are halting. In order to solve decision problems (i.e., decide languages over an alphabet Σ), we use families of recognizer P systems Π={Πx:x∈Σ?}. Each input xis associated with a P system Πxthat decides the membership of xin the language Alternative Space Definitions for P Systems with Active Membranes 13 L⊆Σ?by accepting or rejecting. The mapping x7→ Πxmust be efficiently computable for each input length [4]. These families of recognizer P systems can be used to solve decision problems as follows. Definition 2. Let Πbe a P system whose alphabet contains two distinct objects yes and no, such that every computation of Πis halting and during each computation exactly one of the objects yes,no is sent out from the skin to signal acceptance or rejection. If all the computations of Πagree on the result, then Πis said to be confluent; if this is not necessarily the case, then it is said to be non-confluent and the global result is acceptance if and only if there exists an accepting computation. Definition 3. Let L⊆Σ?be a language, Da class of P systems (i.e. a set of P systems using a specific subset of features) and let Π={Πx|x∈Σ?} ⊆ D be a family of P systems, either confluent or non-confluent. We say that Πdecides L when, for each x∈Σ?,x∈Lif and only if Πxaccepts. Complexity classes for P systems are defined by imposing a uniformity condition on Πand restricting the amount of time or space available for deciding a language. Definition 4. Consider a language L⊆Σ?, a class of recognizer P systems D, and let f:N→Nbe a proper complexity function (i.e. a "reasonable" one, see [5, Definition 7.1]). We say that Lbelongs to the complexity class MC∗ D(f)if and only if there exists a family of confluent P systems Π={Πx|x∈Σ?} ⊆ D deciding Lsuch that: •Πis semi-uniform, i.e. there exists a deterministic Turing machine which, for each input x∈Σ?, constructs the P system Πxin polynomial time with respect to |x|; •Πoperates in time f, i.e. for each x∈Σ?, every computation of Πxhalts within f(|x|)steps. In particular, a language L⊆Σ?belongs to the complexity class PMC∗ Dif and only if there exists a semi-uniform family of confluent P systems Π={Πx|x∈ Σ?}⊆Ddeciding Lin polynomial time. The analogous complexity classes for non-confluent P systems are denoted by NMC∗ D(f)and NPMC∗ D. Another set of complexity classes is defined in terms of uniform families of recognizer P systems: Definition 5. Consider a language L⊆Σ?, a class of recognizer P systems D, and let f:N→Nbe a proper complexity function. We say that Lbelongs to the complexity class MCD(f)if and only if there exists a family of confluent P systems Π={Πx|x∈Σ?}⊆Ddeciding Lsuch that: 14 A. Alhazov, A. Leporati, L. Manzoni, G. Mauri, C. Zandron •Πis uniform, i.e. for each x∈Σ?deciding whether x∈Lis performed as follows: first, a polynomial-time deterministic Turing machine, given the length n=|x|as a unary integer, constructs a P system Πnwith a distinguished input membrane; then, another polynomial-time deterministic Turing machine computes an encoding of the string xas a multiset wx, which is finally added to the input membrane of Πn, thus obtaining a P system Πxthat accepts if and only if x∈L. •Πoperates in time f, i.e. for each x∈Σ?, every computation of Πxhalts within f(|x|)steps. In particular, a language L⊆Σ?belongs to the complexity class PMCDif and only if there exists a uniform family of confluent P systems Π={Πx|x∈Σ?} ⊆ Ddeciding Lin polynomial time. The analogous complexity classes for non-confluent P systems are denoted by NMCD(f)and NPMCD. As stated in the Introduction, the first definition of space complexity for P systems introduced in [8] considered a possible real implementation with biochemical materials, thus assuming that every single object and membrane requires some constant physical space. Such a definition (in the improved version from [3], taking into account also the space required by the labels for membranes and the alphabet of symbols) is the following: Definition 6. Considering a configuration Cof a P system Π, its size |C| is the number of membranes in the current membrane structure multiplied by log |Λ|, plus the total number of objects from Γthey contain multiplied by log |Γ|. If C= (C0,...,Ck)is a computation of Π, then the space required by Cis defined as |C|= max{|C0|,...,|Ck|}. The space required by Πitself is then obtained by computing the space required by all computations of Πand taking the supremum: |Π|= sup{|C|:Cis a computation of Π}. Finally, let Π={Πx:x∈Σ?}be a family of recognizer P systems, and let s:N→ N. We say that Πoperates within space bound sif and only if |Πx| ≤ s(|x|)for each x∈Σ?. Analogously to what has been done for time complexity classes, we can define space complexity classes. By MCSPACED(f(n)) (resp. MCSPACE∗ D(f(n))) we denote the class of languages which can be decided by uniform (resp. semi-uniform) families of confluent P systems of type D(for example, when we refer to P systems with active membranes, we denote this by setting D=AM), where each Πx∈Π operates within space bound f(|x|). In particular, the class of problems solvable in polynomial space by uniform (resp. semi-uniform) confluent systems is denoted by PMCSPACED(resp. Alternative Space Definitions for P Systems with Active Membranes 15 PMCSPACE∗ D), and the class of problems solvable in exponential space by uniform (resp. semi-uniform) confluent systems is denoted by EXPMCSPACED (resp. EXPMCSPACE∗ D). The corresponding classes for non-confluent systems are NPMCSPACED (resp. NPMCSPACE∗ D) and NEXPMCSPACED(resp. NEXPMCSPACED). 3 An Alternative Definition of Space Complexity for P Systems In this section, we first give a different definition of space complexity for P systems with active membranes. This definition considers the information stored in the objects of the systems, and not the single objects themselves. In other words, we store, using binary numbers, the multiplicity of each object in each membrane, thus reducing the amount of needed space with respect to the definition of space given in the previous section. We will refer to this definition of space by binary space, and we will add a symbol Bwhere appropriate, to distinguish between the definitions referring to this new measure and the definitions recalled in the previous section. Definition 7. Consider a configuration Cof a P system Π. Let us denote by h1, h2, ..., hzthe membranes of the current membrane structure (we stress the fact that zcan be smaller, equal, or greater than the initial number of membranes d, due to dissolution and duplication of membranes), and by |Oi,j |the multiplicity of object iwithin region j. The binary size |C|Bof a configuration Cis defined as: |C|B=z·log |Λ|+z X j=1 n X i=1 dlog(|Oi,j |)e·log |Γ| that is the number of membranes in the current membrane structure multiplied by log |Λ|, plus the number of bits required to store the amount of each object in each membrane multiplied by log |Γ|. If C= (C0,...,Ck)is a computation of Π, then the binary space required by C is defined as |C|B= max{|C0|B,...,|Ck|B}. The binary space required by Πitself is then obtained by computing the binary space required by all computations of Πand taking the supremum: |Π|B= sup{|C|B:Cis a computation of Π}. Finally, let Π={Πx:x∈Σ?}be a family of recognizer P systems, and let s:N→ N. We say that Πoperates within binary space bound sif and only if |Πx|B≤ s(|x|)for each x∈Σ?. 22 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov basic variant never evolve themselves, i.e., a catalytic rule is of the form ca →cv, where cis a catalyst, ais a single object and vis a multiset of objects. In contrast, non-catalytic rules in catalytic P systems are non-cooperative rules of the form a→v. From the beginning, the question how many catalysts are needed for obtaining computational completeness has been one of the most intriguing challenges regarding (catalytic) P systems. In [3] it has already been shown that two catalysts are enough for generating any recursively enumerable set of multisets, without any additional ingredients like a priority relation on the rules as used in the original definition. As already known from the beginning, without catalysts only regular (semi-linear) sets can be generated when using the standard halting mode, i.e., a result is extracted when the system halts with no rule being applicable any more. As shown, for example, in [5], using various additional ingredients, i.e., additional control mechanisms, one catalyst can be sufficient: in P systems with label selection, only rules from one set of a finite number of sets of rules in each computation step are used; in time-varying P systems, the available sets of rules change periodically with time. On the other hand, for catalytic P systems with only one catalyst a lower bound has been established in [6]: P systems with one catalyst can simulate partially blind register machines, i.e., they can generate more than just semi-linear sets. In this paper we now return to the idea of using a priority relation on the rules, but take only a very weak form of such a priority relation: we only require that overall in the system catalytic rules have weak priority over non-catalytic rules. This means that the catalyst cmust not stay idle if the current configuration contains an object awith which it may cooperate in a rule ca →cv; all remaining objects evolve in the maximally parallel way with non-cooperative rules. On the other hand, if the current configuration does not contain an object awith which the catalyst cmay cooperate in a rule ca →cv,cmay stay idle and all objects evolve in the maximally parallel way with non-cooperative rules. Even without using more than this weak priority of catalytic rules over the non-catalytic (noncooperative) rules, computational completeness can be established for catalytic P systems with only one catalyst, which is the main result of our paper. 2 Definitions For an alphabet V, by V∗we denote the free monoid generated by Vunder the operation of concatenation, i.e., containing all possible strings over V. The empty string is denoted by λ. Amultiset Mwith underlying 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}. A multiset is empty (respectively finite) if its support is the empty set (respectively a finite set). If M= (A, f) is a finite multiset over Aand supp(M) = {a1, . . . , ak}, then it can also be represented by the string af(a1) 1. . . af(ak) kover the alphabet {a1, . . . , ak}, and, moreover, all permutations of Catalytic P Systems with Weak Priority of Catalytic Rules 23 this string precisely identify the same multiset M. For further notions and results in formal language theory we refer to textbooks like [2] and [11]. 2.1 Register Machines Register machines are well-known universal devices for computing (or generating or accepting) sets of vectors of natural numbers. Definition 1. Aregister machine is a construct M= (m, B, l0, lh, P) where •mis the number of registers, •Pis the set of instructions bijectively labeled by elements of B, •l0∈Bis the initial label, and •lh∈Bis the final label. The instructions of Mcan be of the following forms: •p: (ADD (r), q, s), with p∈B\ {lh},q, s ∈B,1≤r≤m. Increase the value of register rby one, and non-deterministically jump to instruction qor s. •p: (SUB (r), q, s), with p∈B\ {lh},q, s ∈B,1≤r≤m. If the value of register ris not zero then decrease the value of register rby one (decrement case) and jump to instruction q, otherwise jump to instruction s (zero-test case). •lh:HALT . Stop the execution of the register machine. Aconfiguration of a register machine is described by the contents of each register and by the value of the current label, which indicates the next instruction to be executed. In the accepting case, a computation starts with the input of an l-vector of natural numbers in its first lregisters and by executing the first instruction of P(labeled with l0); it terminates with reaching the HALT -instruction. Without loss of generality, we may assume all registers to be empty at the end of the computation. In the generating case, a computation starts with all registers being empty and by executing the first instruction of P(labeled with l0); it terminates with reaching the HALT -instruction and the output of a k-vector of natural numbers in its last kregisters. Without loss of generality, we may assume all registers except the last koutput registers to be empty at the end of the computation. In the computing case, a computation starts with the input of a l-vector of natural numbers in its first lregisters and by executing the first instruction of 24 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov P(labeled with l0); it terminates with reaching the HALT -instruction and the output of a k-vector of natural numbers in its last kregisters. Without loss of generality, we may assume all registers except the last koutput registers to be empty at the end of the computation. Aconfiguration of a register machine is described by the contents of each register and by the value of the current label, which indicates the next instruction to be executed. Mis called deterministic if the ADD-instructions all are of the form p: (ADD (r), q). For useful results on the computational power of register machines, we refer to [7]; for example, to prove our main theorem, we need the following formulation of results for register machines generating or accepting recursively enumerable sets of vectors of natural numbers with kcomponents or computing partial recursive relations on vectors of natural numbers: Proposition 1. Deterministic register machines can accept any recursively enumerable set of vectors of natural numbers with lcomponents using precisely l+ 2 registers. Without loss of generality, we may assume that at the end of an accepting computation all registers are empty. Proposition 2. Register machines can generate any recursively enumerable set of vectors of natural numbers with kcomponents using precisely k+2 registers. Without loss of generality, we may assume that at the end of an accepting computation the first two registers are empty, and, moreover, on the output registers, i.e., the last kregisters, no SUB-instruction is ever used. Proposition 3. Register machines can compute any partial recursive relation on vectors of natural numbers with lcomponents as input and vectors of natural numbers with kcomponents as output using precisely l+ 2 + kregisters, where without loss of generality, we may assume that at the end of a successful computation the first l+ 2 registers are empty, and, moreover, on the output registers, i.e., the last kregisters, no SUB-instruction is ever used. In all cases it is essential that the output registers never need to be decremented. 2.2 Partially Blind Register Machines We now consider one-way nondeterministic machines which have registers allowed to hold positive or negative integers and which accept by final state with all registers being zero. Such machines are called blind if their actions depend on state and input alone and not on the register configuration. They are called partially blind if they block when any register is negative (i.e., only non-negative register contents is allowed) but do not know whether or not any of the registers contains zero. Catalytic P Systems with Weak Priority of Catalytic Rules 25 Definition 2. Apartially blind register machine is a construct M= (m, B, l0, lh, P) where •mis the number of registers, •Pis the set of instructions bijectively labeled by elements of B, •l0∈Bis the initial label, and •lh∈Bis the final label. The instructions of Mcan be of the following forms: •p: (ADD (r), q, s), with p∈B\ {lh},q, s ∈B,1≤r≤m. Increase the value of register rby one, and non-deterministically jump to instruction qor s. •p: (SUB (r), q), with p∈B\ {lh},q∈B,1≤r≤m. If the value of register ris not zero then decrease the value of register rby one and jump to instruction l2, otherwise abort the computation. •lh:HALT . Stop the execution of the register machine. Again, a configuration of a partially blind register machine is described by the contents of each register and by the value of the current label, which indicates the next instruction to be executed. A computation works as for a register machine, yet with the restriction that a computation is aborted if one tries to decrement a register which is zero. Moreover, computing, accepting or generating now also requires all registers (except output registers) to be empty at the end of the computation. Example 1. In [6] it was shown that the vector set S={(n, m)|0≤n, n ≤m≤2n} (which is not semi-linear) can be generated by a P system with only one catalyst and 19 rules. 2.3 Catalytic P Systems As in [6], the following definition cites Definition 4.1 in Chapter 4 of [10]. Definition 3. An extended catalytic P system of degree m≥1is a construct Π= (O, C, µ, w1, . . . , wm, R1, . . . , Rm, i0) where •Ois the alphabet of objects; 26 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov •C⊆Ois the alphabet of catalysts; •µis a membrane structure of degree mwith membranes labeled in a one-to-one manner with the natural numbers 1, . . . , m; •w1, . . . , wm∈O∗are the multisets of objects initially present in the mregions of µ; •Ri,1≤i≤m, are finite sets of evolution rules over Oassociated with the regions 1,2, . . . , m of µ; these evolution rules are of the forms ca →cv or a→v, where cis a catalyst, ais an object from O\C, and vis a string from ((O\C)× {here, out, in})∗; •i0∈ {0,1, . . . , m}indicates the output region of Π. The membrane structure and the multisets in Πconstitute a configuration of the P system; the initial configuration is given by the initial multisets w1, . . . , wm. A transition between configurations is governed by the application of the evolution rules, which is done in the maximally parallel way, i.e., only applicable multisets of rules which cannot be extended by further rules are to be applied to the objects in all membrane regions. The application of a rule u→vin a region containing a multiset Mresults in subtracting from Mthe multiset identified by u, and then in adding the multiset identified by v. The objects can eventually be transported through membranes due to the targets in and out. We refer to [10] for further details and examples. The P system continues with applying multisets of rules in the maximally parallel way until there remain no applicable rules in any region of Π. Then the system halts. We consider the number of objects from O\Ccontained in the output region i0at the moment when the system halts as the result of the underlying computation of Π. The system is called extended since the catalytic objects in C are not counted to the result of a computation. Yet as often done in the literature, in the following we will omit the term extended and just speak of catalytic P systems, especially as we will restrict ourselves to P systems with only one catalyst. The set of results of all computations possible in Πis called the set of natural numbers generated by Πand it is denoted by N(Π) if we only count the total number of objects in the output membrane; if we distinguish between the multiplicities of different objects, we obtain a set of vectors of natural numbers denoted by P s(Π). Remark 1. As in this paper we only consider catalytic P systems with only one catalyst, without loss of generality, we can restrict ourselves to one-membrane catalytic P systems with the single catalyst in the skin membrane, by taking into account the well-known flattening process, e.g., see [4]. Remark 2. Finally, we make the convention that a one-membrane catalytic P system with the single catalyst in the skin membrane and with internal output in the skin membrane, not taking into account the single catalyst cfor the results, throughout the rest of the paper will be described without specifying the trivial membrane structure or the output region (assumed to be the skin membrane), i.e., we will just write Catalytic P Systems with Weak Priority of Catalytic Rules 27 Π= (O, {c}, w, R) where Ois the set of objects, cis the single catalyst, wis the initial input specifying the initial configuration, and Ris the set of rules. As already mentioned earlier, the following result was shown in [6], establishing a lower bound for the computational power of catalytic P systems with only one catalyst: Proposition 4. Catalytic P systems with only one catalyst have at least the computational power of partially blind register machines. 3 Weak Priority of Catalytic Rules In this paper we now study catalytic P systems with only one catalyst in which the catalytic rules have weak priority over the non-catalytic rules. Example 2. To illustrate this weak priority of catalytic rules over the non-catalytic rules, consider the rules ca →cb and a→d. If the current configuration contains k > 0 copies of a, then the catalytic rule ca →cb must be applied to one of the copies, while the rest of objects amay be taken up by the non-catalytic rule a→d. In particular, if k= 1, only ca →cb may be applied. We would like to highlight the fact that weak priority of catalytic rules is much weaker than the general weak priority, as the priority relation is only constrained by the types of rules. Remark 3. The reverse weak priority, i.e., non-catalytic rules having priority over catalytic rules, is useless, since it is equivalent to removing all catalytic rules for which there are non-catalytic rules with the same symbol on the left-hand side of the rule. In that way we just end up with an even restricted variant of P systems with only one catalyst. 3.1 Computational Completeness with Weak Priority In this section, we show that catalytic P systems with one catalyst only and with weak priority of catalytic rules are computationally complete. Theorem 1. Catalytic P systems with only one catalyst and with weak priority of catalytic rules over the non-cooperative rules are computationally complete. Proof. Given an arbitrary register machine M= (m, B, l0, lh, P ) we will construct a corresponding catalytic P system with one membrane and one catalyst Π= (O, {c}, w, R) simulating M. Without loss of generality, we may assume that, depending on its use as an accepting or generating or computing device, the register machine M, as stated in Proposition 1, Proposition 2, and Proposition 3, fulfills 28 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov the condition that on the output registers we never apply any SUB-instruction. The following proof is given for the most general case of a register machine computing any partial recursive relation on vectors of natural numbers with lcomponents as input and vectors of natural numbers with kcomponents as output using precisely l+2+kregisters, where without loss of generality, we may assume that at the end of a successful computation the first l+ 2 registers are empty, and, moreover, on the output registers, i.e., the last kregisters, no SUB-instruction is ever used. In fact, the proof works for any number nof decrementable registers, no matter how many of them are the linput registers and the working registers, respectively. The main idea behind our construction is that all the symbols except the catalyst cand the output symbols (representing the contents of the output registers) go through a cycle of length 2nwhere nis the number of decrementable registers of the simulated register machine. When the symbols are traversing the r-th section of the nsections of length 2, they “know” that they are to probably simulate a SUB-instruction on register rof the register machine M. The alphabet Oof symbols includes register symbols (ar,2i−1),(ar,2i) for every decrementable register rof the register machine and only the register symbol arfor each of the koutput registers r,m−k+ 1 ≤r≤m, the state symbols (p, 2i−1),(p, 2i), 1 ≤i≤n, for every ADD-instruction of the register machine as well as, for p∈BSUB(r)the state symbols (p, 2i−1),(p, 2i) for 1 ≤i≤r as well as (p, 2j−1)−and (p, 2j)0for r+ 1 ≤j≤nfor every SUB-instruction p: (SUB(r), q, s) of the register machine, i.e., p∈BSUB(r), where BSUB(r)denotes the set of labels of all SUB-instruction p: (SUB(r), q, s) of decrementable registers r. Moreover, we use decrement witness symbols λrfor every decrementable register r, as well as the catalyst cand the trap symbol #. Observing that n=m−k, in total we get the following set of objects: O={ar|n+ 1 ≤r≤m} ∪ {(ar, i)|1≤r≤n, 1≤i≤2n} ∪ {λr|1≤r≤n} ∪ {(p, i)|p∈BADD,1≤i≤2n} ∪ {(p, i)|p∈BSUB(r),1≤i≤2r} ∪ {(p, i)−,(p, i)0|p∈BSUB(r),2r+ 1 ≤i≤2n} ∪ {c, #}. BADD denotes the set of labels of ADD-instructions. The starting configuration of Πis w=c(l0,1)α0, where l0is the starting label of the machine and α0is the multiset encoding the initial values of the registers. Catalytic P Systems with Weak Priority of Catalytic Rules 29 All register symbols ar, 1 ≤r≤n, representing the contents of decrementable registers, are equipped with the rules evolving them throughout the whole cycle: (ar, i)→(ar, i + 1),1≤r≤2n−1; (ar,2n)→(ar,1).(1) The construction also includes the trap rule # →#: once the trap symbol # is introduced, it will always keep the system busy and prevent it from halting and thus from producing a result. For simulating ADD-instructions we also need the following rules: Increment p: (ADD(r), q, s): The (variants of the) symbol pcycles together with all the other symbols, always involving the catalyst: c(p, i)→c(p, i + 1),1≤i≤2n−1.(2) At the end of the cycle, the register is incremented and the non-deterministic jump to qor soccurs: for rbeing a decrementable register, we take c(p, 2n)→c(q, 1)(ar,1), c(p, 2n)→c(s, 1)(ar,1),(3) whereas for rbeing a register never to be decremented, we take c(p, 2n)→c(q, 1)ar, c(p, 2n)→c(s, 1)ar(4) The output symbols need not undergo the cycle, in fact, they must not do that because otherwise the computation would never stop. When the computation of the register machine halts, only output symbols will be present, as we have assumed that at the end of a computation all decrementable registers will be empty, i.e., no cycling symbols will be present any more in the P system. Finally, we have to mention that if qor sis the final label lh, then we take λinstead, which means that also the P system will halt, because, as already explained above, the only symbols left in the configuration will be output symbols, for which no rules exist. The state symbol is not allowed to evolve without the catalyst: (p, i)→#,1≤i≤2n. (5) Hence, in that way it is guaranteed that the catalyst cannot be used in another way, i.e., affecting a symbol (ar, i) as explained below during the simulation of a SUB-instruction on register r. Decrement and zero-test p: (SUB(r), q, s): The simulation of a SUB instruction is carried out in two steps of the cycle, i.e., in steps 2r−1 and 2r. Before reaching simulation phase r, i.e., step 2r−1, the state symbol goes through the cycle, necessarily involving the catalyst: 30 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov c(p, i)→c(p, i + 1) >(p, i)→#,1≤i < 2r−1.(6) Although by the definition of the P systems with priority of catalytic rules, the catalytic rule has priority over the non-catalytic rule for (p, i), we indicate the general priority relation by the sign <(or >for the reverse relation) in order to make the situation even clearer. In the first step of the simulation phase r, i.e., in step 2r−1, the state symbol releases the catalyst to try to perform the decrement and to produce a witness symbol if register ris not empty: (p, 2r−1) →(p, 2r), c(ar,2r−1) →cλr.(7) Note that due to the counters identifying the position of the register symbols in the cycle, it is guaranteed that the catalytic rule transforming (ar,2r−1) picks the correct register symbol. Furthermore, due to the priority of the catalytic rules, one of the the register symbols (ar,2r−1) must be transformed by the catalytic rule if present, instead of continuing along its cycle. In the second step of simulation phase r, i.e., in step 2r, the detection of the possible decrement happens. The outcome is stored in the state symbol: cλr→c > λr→#, (p, 2r)→(p, 2r+ 1)−< c(p, 2r)→c(p, 2r+ 1)0.(8) If in the first step of the simulation phase the catalyst did manage to decrement the register, it produced λr. Thus, in the second step, the catalyst must erase λr, because otherwise this symbol will trap the computation (and because catalytic rules have priority). This means that the catalyst is not available to produce (p, 2r+1)0, and the rule (p, 2r)→(p, 2r+1)−must be applied due to the maximally parallel mode. If, on the other hand, the decrement did not succeed in the previous step, both rules (p, 2r)→(p, 2r+ 1)−and c(p, 2r)→c(p, 2r+ 1)0can be applied, but due to the priority of the catalytic rules, the second rule must be preferred, thus producing (p, 2r+1)0. Therefore, the superscript of the state symbol correctly reflects the outcome of the decrement: it is −if the decrement succeeded, and 0 if it did not. After the simulation of the decrement, the state symbols evolve to the end of the cycle and produce the corresponding next state symbols: (p, i)−→(p, i + 1)−, r + 2 ≤i≤n, (p, n + 1)−→(q, 1), (p, i)0→(p, i + 1)0, r + 2 ≤i≤n, (p, n + 1)0→(s, 1). (9) If the register ris the last decrementable one, i.e., r=n, then equations 8 and 9 together read as follows: cλn→c > λn→#, (p, n + 1) →(q, 1) < c(p, n + 1) →c(s, 1).(10) Catalytic P Systems with Weak Priority of Catalytic Rules 31 Finally, we again mention that if qor sis the final label lh, then we take λinstead, which means that not only the register machine but also the P system halts, because, as already explained above, the only symbols left in the configuration will be output symbols, for which no rules exist. ut We would also like to emphasize that the simulation is what may be called toxic/trap-deterministic: the only non-deterministic choice happens between a rule producing a trap symbol # and another one which does not introduce #. This means that the appearance of the trap symbol may immediately abort the computation, which is the concept used for toxic P systems as introduced in [1]. Using the trap symbol # as such a toxic object, the only successful computations are simulating register machines in a quasi-deterministic way with a look-ahead of one, i.e., considering all possible configurations computable from a given one, there is at most one successful continuation of the computation. For future research it remains a challenging question whether the length of the cycle now being 2ncan still be reduced. 4 Conclusion In this paper we revisited a classic problem of computational complexity in membrane computing: can catalytic P systems with only one catalyst already generate all recursively enumerable sets of multisets? This problem has been standing tall for many years, and nobody has yet managed to give it a positive or a negative answer. In this paper, we come closer to showing computational completeness: we give a construction that simulates an arbitrary register machine with a very weak ingredient—the weak priority of catalytic rules over non-catalytic rules. On the other hand, we still conjecture that P systems with one catalyst and no additional control mechanisms cannot reach computational completeness. Finding an answer to the question of characterizing the computational power of P systems with one catalyst therefore still remains one of the biggest challenges in the theory of P systems, although the result established in our paper has made the gap between the computational power of P systems with one catalyst and computational completeness smaller again. The result obtained in this paper can also be extended to P systems dealing with strings, following the definitions and notions used in [6], thus showing computational completeness for computing with strings. Acknowledgements The ideas, concepts, and results described in this paper have mainly been developed in the inspiring atmosphere of the 18th Brainstorming Week on Membrane Computing during the first week of February 2020 in Sevilla. Sergiu Ivanov is partially supported by the Paris region via the project DIM RFSI n◦2018-03 “Mod`eles informatiques pour la reprogrammation cellulaire”. 38 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov of rules which cannot be extended by further rules are to be applied to the objects in all membrane regions. The application of a rule u→vin a region containing a multiset Mresults in subtracting from Mthe multiset identified by u, and then in adding the multiset identified by v. The objects can eventually be transported through membranes due to the targets in and out. The P system continues with applying multisets of rules in the maximally parallel way until there remain no applicable rules in any region of Π. Then the system halts. We consider the number of objects from Ocontained in the output region i0at the moment when the system halts as the result of the underlying computation of Π. The set of results of all computations possible in Πis called the set of natural numbers generated by Πand it is denoted by N(Π) if we only count the total number of objects in the output membrane; if we distinguish between the multiplicities of different objects, we obtain a set of vectors of natural numbers denoted by P s(Π). We refer to [11] for further details and examples. A special variant of P systems uses so-called catalysts, which are objects which allow other objects to evolve, but never evolve themselves. Definition 4. Acatalytic P system of degree m≥1is a construct Π= (O, C, µ, w1, . . . , wm, R1, . . . , Rm, i0) where C⊆Ois the alphabet of catalysts; the evolution rules are of the forms ca →cv or a→v, where cis a catalyst, ais an object from O\C, and vis a string from ((O\C)× {here, out, in})∗; the other ingredients are defined as for hierarchical P systems in Definition 3. A catalytic P system is called purely catalytic if all rules are catalytic ones. Since the beginning, the question how many catalysts are needed in catalytic and purely catalytic P systems for obtaining computational completeness has been a challenging theoretical question. The following result was shown in [7], establishing a lower bound for the computational power of catalytic P systems with only one catalyst: Proposition 4. Catalytic P systems with only one catalyst have at least the computational power of partially blind register machines. Example 1. In [7] it was shown that the vector set S={(n, m)|0≤n, n ≤m≤2n} (which is not semi-linear) can be generated by some (even extended version of a) PBRM and therefore by a P system with only one catalyst and 19 rules. As already shown in [6], register machines with n≥2 decrementable registers can be simulated by catalytic P systems with ncatalysts and by purely catalytic P systems with n+ 1 catalysts. P Systems with Limited Capacity 39 3 Limited Capacity In most of the variants of P systems considered in the literature the number of objects in a membrane region is not limited. In this paper, we propose a variant in which the number of objects a membrane may contain is bounded, with the bound already being given in the definition of the system. In this paper we consider two variants of limiting the capacity – limiting the total capacity of objects in a cell and only limiting the capacity of specific objects in a cell, respectively. Definition 5. A P system with per-membrane limited capacity is the following construct: Π= (O, µ, w1, . . . , wn, k1, . . . , kn, R1,...Rn, i0), where ki∈N∪ {∞} is the total capacity of membrane i,1≤i≤n, meaning that, for |vi|denoting the contents of memrane iin the current configuration, the condition |vi| ≤ kimust always be enforced, unless ki=∞. The other components of the tuple are as in Subsection 2.3. Definition 6. A P system with per-symbol limited capacity is the following construct: Π= (O, µ, w1, . . . , wn, K1, . . . , Kn, R1,...Rn, i0), where Ki:O→N∪ {∞} are functions defining the per-symbol capacity of membrane i. The condition wa≤K(a)must therefore be enforced at all times, for any a∈O, unless K(a) = ∞. In this paper, we will focus on P systems with per-symbol limited capacity. Remark 1. We immediately remark that the flattening technique which is folklore in the membrane computing community can be applied in the case of P systems with per-symbol limited capacity. Without loss of generality, we therefore in Section 4 will only consider 1-membrane systems, which can be written in a simplified version as follows with omitting the trivial membrane structure and taking the skin membrane 1 as the output membrane: Π= (O, w, K, R) and Π= (O, C, w, K, R) for catalytic P systems. 3.1 Semantics of Limited Capacity What should happen if a membrane is about to exceed its capacity (total or persymbol)? Multiple kinds of behaviors may be considered, for example the following variants: 40 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov 1. Blocking behavior: Prohibit the application of (multisets of) rules which would produce more objects. Attempting to apply such rules blocks the system, and yields no result. 2. Destructive behavior: Completely remove the offending membrane from the system, together with its contents. 3. Dissolutive behavior: Dissolve the offending membrane, dumping its contents into its parent membrane; in this case, (one of) the parent membrane(s) must allow for more objects, as otherwise the whole system would be dissolved. 4. Separation behavior: Divide the offending membrane separating its contents across the child membranes. Since every child membrane only receives a part of the contents of the parent, the capacity constraints may be satisfied. The separation behavior may be useful for P systems with active membranes, whereas the first three behaviors may also be applied for hierarchical P systems. In this paper, we focus on the blocking behavior, see 1. Yet there are still at least two possible semantics for the blocking behavior itself under the maximally parallel derivation mode: Semantics 1: Take all the applicable multisets of rules in the maximally parallel derivation mode, but discard all those multisets which would violate the constraints. Semantics 2: Take all the applicable multisets of rules in the asynchronous derivation mode, discard the multisets which would violate the constraints, and then pick the non-extendable, i.e., maximal multisets out of these applicable multisets of rules. To illustrate the difference between these two semantics, consider the following 1-membrane system with limited capacity: a→c b→c ab It can formally be written as Πab = ({a, b}, ab, Kab,{a→c, b →c}) where Kab(c) = 1 and Kab(a) = Kab(b) = ∞. In the case of Semantics 1, no multisets of rules not violating the constraint of limiting the capacity of symbols cin the resulting configuration would be applicable, and the P system will block/abort this computation. P Systems with Limited Capacity 41 On the other hand, under Semantics 2, Πab would be allowed to apply either a→cor b→c, but not both. 4 Computational Power In this section we investigate the computational power of P systems with limited per-symbol capacity: when operating with Semantics 1, they at least can simulate partially blind register machines in real time; when operating with Semantics 2, they can simulate any register machines and therefore are computationally complete. 4.1 Semantics 1 Allows for Simulating a PBRM in Real Time In this subsection, we will show that P systems with limited per-symbol capacity operating under Semantics 1 can simulate partially blind register machines (PBRM) in real time: an instruction of the register machine is simulated in one step of the P system. An additional cleanup procedure at the end of the computation takes 3 more steps. In comparison with the result stated in [7] showing that P systems with one catalyst can simulate partially blind register machines (without any further ingredients), we here obtain a real-time simulation, whereas the result there needs a cycle of n+ 3 for each step of the register machine, with nbeing the number of decrementable registers. Theorem 1. Catalytic P systems with one catalyst and per-symbol limited capacity operating with Semantics 1 can simulate partially blind register machines (PBRM) in real time, plus three additional cleanup steps at the end of the computation. Proof. Consider an arbitrary partially blind register machine M= (m, B, l0, lh, P). The following proof is given for the most general case of a partially blind register machine computing a partial recursive function on vectors of natural numbers with lcomponents as input and vectors of natural numbers with kcomponents as output using nof decrementable registers, no matter how many of them are the first l input registers and the working registers, respectively. Moreover, we may assume that on the output registers, i.e., the last kregisters, no SUB-instruction is ever used. On the other hand, the computation of the PBRM yields a result if and only if at the end of the computation all registers except the output registers are empty. We now construct the P system Π= (O, {c}, w0, K, R) with per-symbol limited capacity operating under Semantics 1 and simulating the PBRM M. 42 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov The set of objects of the construction includes register symbols arfor representing the contents of register r, the catalyst c, and the state symbols p∈B. Moreover, we use decrement witness symbols λrfor every decrementable register r, 1 ≤r≤n, as well as the catalyst cand the trap symbol # and, finally, the additional symbols a0, λ0, lh0. As we will see later, a0can be interpreted as a register symbol for an additional decrementable register 0, which during the whole computation has the value 1, i.e., in every configuration we have exactly one copy of a0, and it is only eliminated in the final cleanup procedure. Now let BSUB(r)denote the set of labels of SUB-instruction p: (SUB(r), q) of decrementable registers r,BSUB =S1≤r≤nBSUB(r), and BADD denote the set of labels of ADD-instructions, i.e., B=BADD ∪BSUB. Observing that n=m−k, in total we get the following set of objects: O={ar|0≤r≤m} ∪ B∪ {lh0} ∪ D∪ {c, #}, D={λr|0≤r≤n}. The capacity of the symbols in Dis limited to 1, while all other symbols may appear in an unlimited number of copies: K(λr)=1,0≤r≤n, K(x) = ∞, x ∈O\D. Moreover, let D∅denote the multiset containing exactly one copy of each object in Dand Drthe multiset containing exactly one copy of each object in Dexcept λr. Then the starting configuration of the P system is defined as w0=c l0D∅a0α0, where α0is the multiset encoding the initial values of the registers. The set of rules now is going to be described in several parts below. First, we want all symbols in Dto disappear after one step: λr→λ∈Rfor all 0 ≤r≤n. We also include the traditional trap rule # →#∈R. Increment p: (ADD(r), q, s): To simulate the ADD instruction p: (ADD(r), q, s) without letting the catalyst block the system or do unwanted decrements, the catalyst is forced to process the state symbol: cp →cqarD∅cp →csarD∅p→#. P Systems with Limited Capacity 43 When the label of an ADD instruction is present in the configuration, the catalyst cannot act on any of the register symbols ar,0≤r≤m, because this would leave the state symbol pto be transformed to # due to the maximally parallel derivation mode. This evolution will not violate the capacity constraints, but introducing the trap symbol will prevent the system from ever halting. Therefore, the catalyst must be used in one of the two rules simulating the increment. Incidentally, these rules also replenish the supply of the symbols from D. Decrement p: (SUB(r), q)(no zero test): Consider the configuration c p D∅a0α, where αis a string of register symbols describing the current contents of the registers. The following rules have to be applied in this configuration: p→qDrcar→cλr. All the symbols from D∅from the current configuration will disappear in the next configuration. The rule p→qDrwill reintroduce almost all of the symbols, except for the particular λrcorresponding to the register to be decremented. This allows car→cλrto be applied in the current step, because in the next configuration there is still room for λr. All catalytic rules involving a wrong λr0(and therefore a wrong ar0) cannot be applied, because they would introduce a second instance of λr0, thus blocking the system. Therefore, the only possible evolution from the configuration c p D∅a0αis to the configuration c q D∅a0βwhere β=α−ar. Note that if the expected register symbol aris not present in α, then there will be no non-extendable multiset of rules including the correct car→cλp, because then at least the rule ca0→cλ0described below would become applicable, thus blocking (aborting) the computation without producing any result. This behavior corresponds to a crash in the PBRM when it tries to decrement a register which is already empty. Final zero test, cleanup, and halting: The simulation of the decrement instruction on register ronly works correctly when there are still some register symbols arleft. Indeed, as already mentioned above, in order to force the computation in the P system to abort if a decrement on an empty register would be tried, we at least would have the rule ca0→cλ0, but as long as the decrement symbol λ0is re-introduced by applying a rule p→qDr simulating a decrement on register r, the computation in the P system will be forced to crash as two symbols λ0are not allowed in a configuration. On the other hand, if finally, the PBRM has reached a configuration with all decrementable registers r, 1 ≤r≤nbeing empty, we have to allow for a final zero test: in this case the rule ca0→cλ0is welcome to be applied if we have reached the final (halting) label lh: lh→lh0Dλ0ca0→cλ0 44 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov The additional label lh0is used to check whether all decrementable registers are empty as required for a computation of the PBRM to be successful: lh0→Dλ0car→c#λ0,1≤r≤n In this step, the catalyst is free to use one of the rules car→c#λ0for any non-empty register rwithout violating the limiting condition for λ0, hence, the trap symbol # is introduced if and only if any of the decrementable registers is not empty. If all decrementable registers have been empty, in the final step, the system will just erase the symbols of Dλ0, which will disappear and the system will halt with only symbols arfor the output registers n+ 1 ≤r≤m. This final cleanup phase takes one step to erase a0, one more step to test the presence of register symbols ar, 1 ≤r≤n, and one final step to erase the last symbols of Dλ0. Hence, in a successful computation this final phase takes three steps. In the case of the simulation of a non-successful computation of the PBRM, there may be many more steps applying rules car→c#λ0, possibly already in the second step, but with the trap rule # →#∈Rcausing an infinite computation we need not take care about this situation in detail. ut Remark 2 (Trapping by limited capacity). Instead of having the rule # →# to implement the trap symbol as a guarantee for an infinite computation and thus for any computation introducing it to not be successful, we can limit its capacity to 1 and use rules of the form u→v## instead of u→v#. Alternatively, we could limit the capacity of # to 0, meaning that even having to pick the rule u→v# will already block the evolution. This means that, if all non-extendable multisets of rules contain a rule of the form u→v#, then we must discard all multisets, thereby blocking the evolution without producing any result. This blocking of computations reflects the concept of using toxic objects as introduced in [2]. 4.2 Semantics 2 Allows for Computational Completeness In this subsection, we show that (purely catalytic) P systems with limited persymbol capacity are computationally complete when operating with Semantics 2 without any additional ingredients. Remark 3 (Simulating catalytic rules). We first observe that when operating with Semantics 2 we can limit the parallelism of a non-cooperative rule by producing a marker symbol whose capacity is limited to one. For example, consider the rule p:a→uλptogether with the rule λp→λand the limiting condition K(λp) = 1, i.e., the symbol λpmay not appear in more than one copy. Then, in any multiset of rules allowed to be applied λpmay appear in at most one copy. This effectively prohibits applying pmore than once in any step. P Systems with Limited Capacity 45 Moreover, we can ensure that the rules compete for the marker symbol just as catalytic rules would compete for a catalyst. For example, consider two catalytic rules ca →cu and cb →cv. These two rules cannot be applied at the same time, even if both aand bare present, because the catalyst is only present in a single copy. We can ensure the same mutual exclusion by having the symbol λcwith the capacity limited to 1 (K(λc) = 1), and the rules a→uλcand b→vλc. Remark 4 (No catalysts needed). As elaborated in Remark 3, catalytic rules can be replaced by non-cooperative rules, i.e., P systems with per-symbol limited capacity operating with Semantics 2 do not need catalysts for simulating purely catalytic P systems. All together, these observations imply the following results: Theorem 2. P systems with per-symbol limited capacity operating with Semantics 2 without catalysts can simulate purely catalytic P systems. Since purely catalytic P systems are computationally complete, for example see [6], we immediately derive the following corollary. Corollary 1. P systems with per-symbol limited capacity operating with Semantics 2 are computationally complete, even without using catalysts. Remark 5 (Trapping by limited capacity). When following the proofs as given in [6] for simulating register machines by [purely] catalytic P systems, often rules introducing the trap symbol # as well as the rule # →# are used to guarantee an infinite computation and thus any computation introducing it to not be successful. As already explained in Remark 2, we can avoid these rules by limiting the capacity of the trap symbol to 1 and use rules of the form u→v## instead of u→v#, or alternatively, limit the capacity of # to 0, meaning that even having to pick the rule u→v# will already block the computation. 5 Conclusion In this paper, we have introduced the idea of bounding the number of symbols that may appear in the membranes of a P systems. This is a quite natural restriction to consider, given that actual biological membranes are of limited capacity, too. We defined limited total and per-symbol capacities, and defined two possible semantics for handling the overflow. We then showed that Semantics 1 allows noncooperative P systems to simulate partially blind register machines in real time, with 3 additional cleanup steps at the end of the computation. We also showed that non-cooperative P systems operating under Semantics 2 of limited capacity directly simulate purely catalytic P systems (in real time), yet without needing catalysts, and therefore are computationally complete. 46 Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov This paper only scratches the surface of the study of P systems with limited capacity. One immediate open problem is that of computational completeness of (catalytic, purely catalytic) P systems with limited capacity operating with Semantics 1 or else characterizing the computational power of these systems. Furthermore, Section 3 gives three more different behaviors which P systems may adopt when their membranes overflow. In particular, the separation and the dissolutive behaviors may even better represent the phenomena one would expect to observe in overfull membranes in biological cells. Acknowledgements The ideas, concepts, and results described in this paper have mainly been developed in the inspiring atmosphere of the 18th Brainstorming Week on Membrane Computing during the first week of February 2020 in Sevilla. Sergiu Ivanov is partially supported by the Paris region via the project DIM RFSI n◦2018-03 “Mod`eles informatiques pour la reprogrammation cellulaire”. References 1. Artiom Alhazov. P systems without multiplicities of symbol-objects. Inf. Process. Lett., 100(3):124–129, 2006. 2. Artiom Alhazov and Rudolf Freund. P systems with toxic objects. In Marian Gheorghe, Grzegorz Rozenberg, Arto Salomaa, Petr Sos´ık, and Claudio Zandron, editors, Membrane Computing – 15th International Conference, CMC 2014, Prague, Czech Republic, August 20–22, 2014, Revised Selected Papers, volume 8961 of Lecture Notes in Computer Science, pages 99–125. Springer, 2014. 3. Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov. Length P systems. Fundam. Inform., 134(1-2):17–37, 2014. 4. Artiom Alhazov, Rudolf Freund, and Agustin Riscos-N´u˜nez. Membrane division, restricted membrane creation and object complexity in P systems. Int. J. Comput. Math., 83(7):529–547, 2006. 5. J¨urgen Dassow and Gheorghe P˘aun. Regulated Rewriting in Formal Language Theory. Springer, 1989. 6. Rudolf Freund, Lila Kari, Marion Oswald, and Petr Sos´ık. Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science, 330(2):251–266, 2005. 7. Rudolf Freund and Petr Sos´ık. On the power of catalytic P systems with one catalyst. In Grzegorz Rozenberg, Arto Salomaa, Jos´e M. Sempere, and Claudio Zandron, editors, Membrane Computing – 16th International Conference, CMC 2015, Valencia, Spain, August 17–21, 2015, Revised Selected Papers, volume 9504 of Lecture Notes in Computer Science, pages 137–152. Springer, 2015. 8. Marvin L. Minsky. Computation. Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967. 9. Gheorghe P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61(1):108–143, 2000. 10. Gheorghe P˘aun. Membrane Computing: An Introduction. Springer, 2002. P Systems with Limited Capacity 47 11. Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa, editors. The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. 12. Grzegorz Rozenberg and Arto Salomaa, editors. Handbook of Formal Languages. Springer, 1997. 13. The P Systems Website. http://ppage.psystems.eu/. 54 Rodica Ceterchi, David Orellana-Mart´ın, and Gexiang Zhang 4.1 In string format We have from [2] the linearization procedure which allows to pass from the 2D array representation to the linear one. [U]→[Ru]sw[Ur]nw[Ud]ne[L∗]se [R]→[Ur]sw[Ru]se[Rl]ne[D]nw [L]→[Dl]ne[Ld]nw[Lr]sw[U]se [D]→[Ld]ne[Dl]se[Du]sw[R]nw 4.2 In 2D array format Each nonterminal array is in a membrane which has the possibility of dividing itself into 4 membranes organized in a tissue manner. The array rewriting rules become division rules for membranes, resulting in tissue P systems: [U1∗]→[Ur] [Ud] [Ru] [L∗]with ∗=d, r (15) [R1∗]→[D∗] [Rl] [Ur] [Ru]with ∗=u, l (16) [L1∗]→[Ld] [Dl] [Lr] [U∗]with ∗=d, r (17) [D1∗]→[R∗] [Ld] [Du] [Dl]with ∗=u, l (18) An example of 3 succesive subdivisions, which will finally lead to the picture: [U1∗]→[Ur] [Ud] [Ru] [L∗] [U1r] [U1d] [R1u] [L1∗]→ [Ur] [Ud] [Ur] [Ud] [Ru] [Lr] [Ru] [Ld] [Du] [Rl] [Ld] [Dl] [Ur] [Ru] [Lr] [U∗] [U1r] [U1d] [U1r] [U0d] [R1u] [L0r] [R1u] [L0d] [D1u] [R1l] [L1d] [D1l] [U0r] [R1u] [L1r] [U1∗] → → [Ur] [Ud] [Ur] [Ud] [Ur] [Ud] [#0] [#0] [Ru] [Lr] [Ru] [Ld] [Ru] [Lr] [#0] [#0] [Du] [Rl] [#0] [#0] [Du] [Rl] [#0] [#0] [Ur] [Ru] [#0] [#0] [Ur] [Ru] [#0] [#0] [Ru] [Ld] [Dl] [Rl] [Ld] [Dl] [Rl] [Ld] [Du] [Dl] [Ur] [Ru] [Lr] [Ud] [Du] [Dl] [#0] [#0] [Du] [Rl] [Ld] [Dl] [Ur] [Ud] [#0] [#0] [Ur] [Ru] [Lr] [Ur] [Ru] [L∗] [Ur] [Ud] [Ur] [Ud] [U0r] [U0d] [#0] [#0] [Ru] [L0r]R0u Ld Ru L0r#0#0 [Du] [R0l] [#0] [#0] [Du] [R0l] [#0] [#0] [Ur] [R0u] [#0] [#0] [Ur] [R0u] [#0] [#0] [Ru] [Ld] [D0l] [R0l] [Ld] [Dl] [Rl] [L0d] [D0u] [Dl] [Ur] [R0u] [L0r] [U0d] [Du] [D0l] [#0] [#0] [Du] [Rl] [L0d] [D0l] [Ur] [U0d] [#0] [#0] [U0r] [Ru] [Lr] [Ur] [Ru] [L0∗] → · · · With labels on membranes: [U]→[Ru]sw[Ur]nw[Ud]ne[L∗]se [R]→[Ur]sw[Ru]se[Rl]ne[D]nw Contour Approximation with P Systems 55 [L]→[Dl]ne[Ld]nw[Lr]sw[U]se [D]→[Ld]ne[Dl]se[Du]sw[R]nw [U1∗]→[Ur]nw [Ud]ne [Ru]sw [L∗]se with ∗=d, r (19) [R1∗]→[D∗]nw [Rl]ne [Ur]sw [Ru]se with ∗=u, l (20) [L1∗]→[Ld]nw [Dl]ne [Lr]sw [U∗]se with ∗=d, r (21) [D1∗]→[R∗]nw [Ld]ne [Du]sw [Dl]se with ∗=u, l (22) 4.3 Labels for membranes, and memory In the above we have used labels {sw, nw, ne, se}standing for the obvious notation for corners of a square: southwest, northwest, etc. Of course, binary labels could be used instead, with interesting properties. For instance: sw = 00, nw = 01, ne = 11, se = 10. This has the property that any 2 adjacent squares have labels differing in only 1 bit (Gray code on 2 bits). Many binary codes can be associated to SFCs. We will concatenate (properly!) labels at every derivation step, such that each membrane: on one hand inherits the label of its ’parent’, and gets a label stating what ’son’ it is. In this way, membranes have memory. Division rules (with labels) will be of the form: [ ]α→[ ]α00 [ ]α01 [ ]α11 [ ]α10 5 Tissue P systems with evolutional communication rules, extended division rules and external inputs Definition 1. Let Π= (Γ, H, M1,...,Mq,R,I)be a tissue P system with evolutional communication rules, extended division and rexternal inputs rules of degree q, where: 1. Γis a finite alphabet; 2. His the set of labels {1, . . . , q}; 3. M1,...,Mqare multisets over Γ; 4. Ris the set of rules of the following forms: a) [u]h1[v]h2→[v0]h1[u0]h2, h1, h2∈H, u, v, u0, v0∈Mf(Γ),|u|+|v|> 0,|u|= 0 → |u0|= 0,|v|= 0 → |v0|= 0 (evolutional communication rules); 56 Rodica Ceterchi, David Orellana-Mart´ın, and Gexiang Zhang b) [a]h→[a1]h1. . . [as]hs, h, h1, . . . , hs∈H, a, a1, . . . , as∈Γ(extended division rules); 5. Ibe a set of elements (Γi, Hi,Ri),1≤i≤rsuch that: a) Γi⊆Γ; b) Hi∩H=∅ ∧ Hi∩Hj=∅, i 6=j. c) Riis the set of rules of the following form: i. [u]h1[v]h2→[ ]h1[u0]h2, h1∈Hi, h2∈H, u ∈Mf(Γi), v, u0∈ Mf(Γ),|u|>0(evolutional communication rules); A tissue P system with communication rules, extended division rules and rinputs Π= (Γ, H, M1,...,Mq,R,I) of degree qcan be viewed as a set of qcells such that M1,...,Mqrepresent the multisets of objects initially placed in the qcells of the system. A rule of the type [ u]h1[v]h2→[v0]h1[u0]h2is called an evolutional communication rule. A rule of the type [ a]h→[a1]h1. . . [as]hsis called an extended division rule. The length of evolutional communication rules is defined by |u|+|v|+|u0|+|v0|. The length of extended division rules is defined by s+ 1. These rules were introduced in [9], and more deeply investigated in [4, 5, 6] An instantaneous description or a configuration at an instant tof a tissue P system with evolutional communication rules and extended division rules is described by the cells present and the corresponding multisets of objects over Γ associated with all the cells present in the system (not in the inputs). The initial configuration is ((1,M1),...,(q, Mq)). A rule [ u]h1[v]h2→[v0]h1[u0]h2, h2∈His applicable to a configuration Ct at an instant tif there exist a cell labelled by h1containing the multiset uand a cell labelled by h2containing the multiset v. When applying such a rule, the objects specified by uand vdisappear from their respective cells and multisets v0 and u0appear in h1and h2, respectively. If |u|= 0 (respectively, |v|= 0), then |u0|= 0 (resp., |v0|= 0) must be satisfied (this would correspond to symport rules). If h2∈H1∪ · · · ∪ Hr, the rule is applicable to a configuration Ctat an instant tif there exist a cell labelled by h1containing the multiset uand the cell of the external input isuch that h2∈Hicontains the multiset v. The behaviour of the application of the rule is similar to when h2∈H. A rule [ a]h→[a1]h1. . . [as]hsis applicable to a configuration Ctat an instant tif there exists a cell labelled by hcontaining an object a. When applying such a rule, the cell his divided in snew cells labelled by hi(1 ≤i≤s), where ais changed to aiin the corresponding cell and the rest of the contents is replicated in each cell. We can think that the external inputs are independent systems that are computing a function. In each computational step, they will have different contents, that will be stated when the system is defined. In this sense, the contents of each cell of the system has to be defined for every configuration. The rules from Rof a tissue P system with evolutional communication rules, extended division rules and external inputs are applied in a non-deterministic Contour Approximation with P Systems 57 maximally parallel manner (at each step we apply a multiset of rules which is maximal; that is, no further applicable rule can be added), with the following important remark: if a cell is divided, then the division rule is the only one which is applied to that cell at that step; that is, extended division rules interrupts the communication of that cell with others in that step. The new cells resulting from division will be able to interact with other cells from the next step. Let us fix a tissue P system with evolutional communication rules, extended division rules and rinputs Π. We say that configuration Ctyields configuration Ct+1 in one transition step, denoted by Ct⇒ΠCt+1 if we can pass from Ctto Ct+1 by applying the rules from Ras follows: A transition step is divided in two micro-steps. 1. First, rules from Ri,1≤i≤rare applied in a maximally parallel and nondeterministic way. The “input systems” cannot receive any new contents from the main system. This first step is denoted as Ct C0 t; 2. Second, rules from Rare applied as stated above. This is denoted as C0 t→ Ct+1; We say that a transition step Ct⇒ΠCt+1 is a transition Ct C0 t→ Ct+1. Acomputation of Πis a (finite or infinite) sequence of configurations such that: 1. the first term of the sequence is the initial configuration of the system; 2. each non-initial configuration of the sequence is obtained from the previous configuration by applying rules of the system in a maximally parallel manner with the restrictions previously mentioned; and 3. if the sequence is finite (called halting computation) then the last term of the sequence is a halting configuration (a configuration where no rule of the system is applicable to it). All computations start from an initial configuration and proceed as stated above. If C= (C0,...,Cp) of Π(p∈N) is a halting computation, then the length of C, denoted by |C| is p; that is, |C| is the number of non-initial configurations which appear in the finite sequence C. We denote by Ct(i), i ∈H, the multiset of objects over Γcontained in all membranes labelled by i(by applying extended division rules different membranes with the same label can be created) at configuration Ct. We denote C∗ tthe multiset Σh∈HCt(h) 6 Generating contour approximations with P systems We will use a P system of the type introduced in Section 5. It interacts with a 2D picture with contour as described by Figure 4 Let nbe the number of iterations of the Hilbert curve we want to describe, let L={00,01,10,11}nthe set of all words of length at most 2nover {00,01,10,11} and N={Ud, Ur, Ru, Rl, Ld, Lr, Du, Dl}. We consider the tissue P system 58 Rodica Ceterchi, David Orellana-Mart´ın, and Gexiang Zhang 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 Fig. 4. In each step, the external input system pic interacts with Πin such a way that a symbol 0 or 1 is sent to the corresponding cell in the system. Π= (Γ, H, Mλ,R,I) with evolutional communication rules, extended division rules and 1 external input defined as follows: 1. Working alphabet: Γ=N∪ {Uαd, Uαr, Rαu, Rαl, Lαd, Lαr, Dαu, Dαl|α∈ {0,1}} ∪ {0,1}, being λthe empty string; 2. H={00,01,10,11}∗(that is, the set of all words over {00,01,10,11}) is the set of labels; 3. Mλ={U1r} 4. The set Rconsists of the following rules: a) Rules to divide the cells with intersections: [U1d]h→[Ru ]h00 [Ur ]h01 [Ud ]h11 [Ld ]h10 [U1r]h→[Ru ]h00 [Ur ]h01 [Ud ]h11 [Lr ]h10 [R1u]h→[Ur ]h00 [Du ]h01 [Rl ]h11 [Ru ]h10 [R1l]h→[Ur ]h00 [Dl ]h01 [Rl ]h11 [Ru ]h10 [L1d]h→[Lr ]h00 [Ld ]h01 [Dl ]h11 [Ud ]h10 [L1r]h→[Lr ]h00 [Ld ]h01 [Dl ]h11 [Ur ]h10 [D1u]h→[Du ]h00 [Ru ]h01 [Ld ]h11 [Dl ]h10 [D1l]h→[Du ]h00 [Rl ]h01 [Ld ]h11 [Dl ]h10 b) Rules to divide the cells without intersections: Contour Approximation with P Systems 59 [U0d]h→[ # ]h00 [ # ]h01 [ # ]h11 [ # ]h10 [U0r]h→[ # ]h00 [ # ]h01 [ # ]h11 [ # ]h10 [R0u]h→[ # ]h00 [ # ]h01 [ # ]h11 [ # ]h10 [R0l]h→[ # ]h00 [ # ]h01 [ # ]h11 [ # ]h10 [L0d]h→[ # ]h00 [ # ]h01 [ # ]h11 [ # ]h10 [L0r]h→[ # ]h00 [ # ]h01 [ # ]h11 [ # ]h10 [D0u]h→[ # ]h00 [ # ]h01 [ # ]h11 [ # ]h10 [D0l]h→[ # ]h00 [ # ]h01 [ # ]h11 [ # ]h10 [ #0]h→[ # ]h00 [ # ]h01 [ # ]h11 [ # ]h10 5. I= (Γpic, Hpic,Rpic), where: a) Γpic ={0,1} b) Hpic is the set of the elements from Hbut with superscript pic. c) The set Rpic consists of the following rules: i. Rules to communicate if there is an interesection in a specific area: [a]pic h[Ud ]h→[ ]pic h[Uad]h [a]pic h[Ur ]h→[ ]pic h[Uar]h [a]pic h[Ru ]h→[ ]pic h[Rau]h [a]pic h[Rl ]h→[ ]pic h[Ral]h [a]pic h[Ld ]h→[ ]pic h[Lad]h [a]pic h[Lr ]h→[ ]pic h[Lar]h [a]pic h[Du ]h→[ ]pic h[Dau]h [a]pic h[Dl ]h→[ ]pic h[Dal]h                          for a ∈ {0,1}, h ∈H [ 0 ]pic h[ # ]h→[ ]pic h[ #0]h d) The contents of a cell in this system will be 0 if there is no intersection in the corresponding area of the picture, and 1 otherwise. In each configuration there will exist the cells corresponding to the resolution of the system. 7 Conclusions, Open problems, Suggestions for further developments The present paper proposes a new variant of parallel array rewriting rules, capable to generate approximations of irregular contours, based on conecting pieces of Hilbert words of different ’resolutions’. It proposes also a new variant of tissue P systems with evolutional communication rules, extended division rules and external inputs. In this variant, division rules are allowed to change the labels of the new created cells. The capability of receive input from an external source allows these systems to get more precision of a picture in each transition step. Further developments are possible along several lines. •to find means of effectively representing in a graphical manner the entire approximation, the problem being the segments which connect pieces of the SFC; 60 Rodica Ceterchi, David Orellana-Mart´ın, and Gexiang Zhang •other variants of P systems and refinements of the proposed one •use the external input as a catalyst to allow or forbid the system to evolve. •making use of the array representation in string format; •taking into account the versatility of P systems, to use this small model as a template for complex applications, which involve the manipulation of spatial data; an example would be looking for applications in robotics (global path planning). Acknowledgements The present paper is work in progress. It was supported in part by the research project TIN2017-89842-P, cofinanced by Ministerio de Econom´ıa, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigaci´on (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union. The work of GZ was supported by the National Natural Science Foundation of China (61972324, 61672437, 61702428), by Beijing Advanced Innovation Center for Intelligent Robots and Systems (2019IRS14) and Artificial Intelligence Key Laboratory of Sichuan Province (2019RYJ06). On a more personal note, RC would like to thank Luis Valencia-Cabrera for asking a very interesting question. References 1. M. Bader. Space-filling Curves - An Introduction with applications in Scientific Computing. Texts in Computational Science and Engineering. Springer-Verlag (2013). 2. R. Ceterchi, L. Zhang, L. Pan, K. G. Subramanian, G. Zhang. Generating Hilbert Words in Array Representation with P Systems, presented at ACMC2019, 14-16 November 2019, Xiamen, China (submitted) 3. D. Hilbert. ¨ Uber die stetige Abbildung einer Linie auf ein Fl¨achenst¨uck. Math. Annln. 38 459–460 (1891). 4. D. Orellana-Mart´ın, L. Valencia-Cabrera, B. Song, L. Pan, M.J. P´erez-Jim´enez. Tuning frontiers of efficiency in tissue P systems with evolutional communication rules. Complexity, to be published. 5. D. Orellana-Mart´ın, L. Valencia-Cabrera, B. Song, L. Pan, M.J. P´erez-Jim´enez. Narrowing Frontiers with Evolutional Communication rules and Cell Separation. In D. Orellana, Gh. P˘aun, A. Riscos, L. Valencia (eds.), Proceedings of the Sixteenth Brainstorming Week on Membrane Computing, Sevilla, Spain, January 30 - February 2 2018, pp. 123-162. 6. L. Pan, B. Song, L. Valencia-Cabrera, M.J. P´erez-Jim´enez. The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules. Complexity, vol. 2018, Article ID 3745210, 21 pages, 2018 (10.1155/2018/3745210). 7. G. Peano. Sur une courbe qui remplit toute une aire plane. Math. Annln. 36 157–160 (1890). Contour Approximation with P Systems 61 8. H. Sagan. Space-filling curves. Springer-Verlag. New York. 1994. 9. B. Song, C. Zhang, L. Pan. Tissue-like P systems with evolutional symport/antiport rules. Information Sciences,378 (2017), 177-193 (doi: 10.1016/j.ins.2016.10.046). P Colonies and Reaction Systems Lucie Ciencialov´a1, Ludˇek Cienciala1, and Erzs´ebet Csuhaj-Varj´u2 1Institute of Computer Science, Silesian University in Opava, Czech Republic [email protected] [email protected] 2Department of Algorithms and Their Applications, Faculty of Informatics E¨otv¨os Lor´and University P´azm´any P´eter s´et´any 1/c, 1117 Budapest, Hungary [email protected] Summary. P colonies are abstract computing devices modeling communities of very simple reactive agents living and acting in a joint shared environment which is given with a multiset of objects. Reaction systems were proposed as a computing device, components of which represent basic chemical reactions that take place in shared environment given with a set. Although P colonies operate with multisets of objects and reaction systems work with sets, the two models can be related. In this paper, we construct a P colony simulating interactive processes in a reaction system. P colonies were introduced in [7] as a variant of very simple membrane systems (P systems), inspired by so-called colonies of formal grammars. (For more information on P systems the interested reader is referred to [9], for P colonies to [1], and for grammatical model colony to [8].) A P colony is formed from agents and their shared environment. Each agent is represented by a multiset of objects in a membrane and the environment is given by multiset of objects as well. Agents are equipped with programs composed from rules, the rules are applied to (multisets of) objects. The number of objects inside each agent is set by definition and it is usually a very small number - 1, 2 or 3. The environment of the P colony is used as communication channel for agents. Through the environment, the agents are able to affect the behavior of another agent. The rules of the agents can be rewriting, communication or checking rules; these three rule types were introduced in [7]. Rewriting rule a→ballows agent to rewrite (evolve) one object ato object b. Both objects are placed inside the agent. Communication rule a↔bprovides the possibility to exchange object cplaced inside the agent and object din the environment. A checking rule is formed of two rules r1, r2which are of type rewriting or communication. Checking feature sets some kind of priority between rules r1, r2. The agent tries to apply the first rule and if it cannot be performed, the agent executes the second rule. The agents of P colonies work in a maximally parallel manner, i.e., a maximal number of enabled 70 Lucie Ciencialov´a, Ludˇek Cienciala, and Erzs´ebet Csuhaj-Varj´u 0 : e0 i-agent 1 e0 i-agent 2 e0 i-agent 3 env: They execute the first program e↔a00 j/ e ↔e;i→io. 1 : e0o i-agent 1 e0o i-agent 2 e0o i-agent 3 env: In this configuration, the i-agents have applicable programs that can generate objects corresponding to symbols from C0. 2 : a100 o i-agent 1 e00 o i-agent 2 a300 o i-agent 3 env: After performing programs haj↔e; 00 o→00i(i-agent 1 and 3) or he↔e; 00 o→00i (i-agent 2). All symbols in C0are placed in the environment. 3 : env: a1a3 e00 i-agent 1 e00 i-agent 2 e00 i-agent 3 All three agents wait until object Fappears in the environment. 2. Multiply Input This phase is to multiply the input symbols to be ”accessible” for every agent that simulates enabled reaction. Notice that in case of reaction systems all enabled reactions should be performed in parallel. We construct a-agents that generate |A| symbols that appear in the environment after the first phase. The programs for this phase are: haj↔aj/ aj→W; 1 →10i haj→aj; 10→2i haj↔e;i→i0i hW→W;i→i0i1≤i≤ |A| − 1 he→aj;i0→(i+ 1)i hW→W;i0→(i+ 1)i1≤i < |A| − 1 he→aj;i0→Fi hW→W;i0→Fii=|A| − 1 haj↔e;F↔ei hW→W;F↔ei he→aj;e→1i hW→aj;e→1i P Colonies and Reaction Systems 71 The number of a-agents is |S|. In the previously given example the second phase of simulation can be depicted as follows: 0 : a11 a-agent 1 a21 a-agent 2 a31 a-agent 3 env: a1a3 1 : a110 a-agent 1 W10 a-agent 2 a310 a-agent 3 env: a1a3 2 : a12 a-agent 1 W2 a-agent 2 a32 a-agent 3 env: a1a3 3 : e20 a-agent 1 W20 a-agent 2 e20 a-agent 3 env: a2 1a2 3 4 : a1F a-agent 1 W F a-agent 2 a3F a-agent 3 env: a2 1a2 3 5 : e e a-agent 1 W e a-agent 2 e e a-agent 3 env: a3 1a3 3F3 After generation of 3 copies of each kind of objects that appears in C0all a-agents stop working until object ajappears in the environment. When the copies of F appear in the environment, i-agents consume them, i.e. import them from the environment. From this step on, they rewrite their content y= 4 + 2k+ 2mtimes. After ysteps they are prepared to produce the next input. 3. Simulation of reactions The task of the agents in this phase is to simulate the execution of reactions performed in the same step of the interactive process of the R system. The agents executing this task are called r-agents. Because they need some timing, there is another group of agents called t-agents. In certain steps, these t-agents generate objects that trigger the action of r-agents. The r-agents look for inhibitors, reactants and generate ”semi-products” (a0 j) of reactions. After preparation, the search for inhibitors can be done in one step. If there is at least one inhibitor in the environment, then the reaction is not enabled. The r-agents have a program for each inhibitor that allows the agent to consume this inhibitor. If there is no inhibitor in the environment, then the agent has no applicable program. The number of r-agents is the same as the number of t-agents and it equals to |A|. Let r: (Rr, Ir, Pr) is a reaction in A. The programs for search for inhibitors are: 72 Lucie Ciencialov´a, Ludˇek Cienciala, and Erzs´ebet Csuhaj-Varj´u r-agents a) search for inhibitors he→e;e↔Ii he↔aj;I→Ciaj∈Ir haj→e;C→ei hC→C;e↔Ti hC→e;T→ei he↔T;I→Ri hT→e;R→R0 0i t-agents a) activation of r-agents he→e;i→(i+ 1)i0≤i < 2|A|+ 1 he→e; (2|A|+ 1) →Ii he→T0;I↔ei hT0→T;e↔ei hT↔e;e→00i he→e;i0→(i+ 1)0i0≤i0≤2k+ 2m he→e; (2k+ 2m)→0i Let us return to the previous example. Ahas three reactions: r1= ({a2},∅,{a2}) r2= ({a1, a3},{a2},{a1, a2}) r3= ({a3},{a1},{a1, a2}) and C0={a1, a3}. Then k= 2, m = 2 and there are three copies of a1and three copies of a3in the environment of the P colony. The first configuration of this phase is: 0 : e e r-agent 1 e e r-agent 2 e e r-agent 3 e7 t-agent 1 e7 t-agent 2 e7 t-agent 3 env: a3 1a3 3F3 1 : e e r-agent 1 e e r-agent 2 e e r-agent 3 e I t-agent 1 e I t-agent 2 e I t-agent 3 env: a3 1a3 3 The copies of object Fwere consumed by i-agents (see the third program of iagents in the first phase). 2 : e e r-agent 1 e e r-agent 2 e e r-agent 3 T0e t-agent 1 T0e t-agent 2 T0e t-agent 3 env: a3 1a3 3I3 3 : e I r-agent 1 e I r-agent 2 e I r-agent 3 T e t-agent 1 T e t-agent 2 T e t-agent 3 env: a3 1a3 3 P Colonies and Reaction Systems 73 4 : e I r-agent 1 e I r-agent 2 a1C r-agent 3 e00 t-agent 1 e00 t-agent 2 e00 t-agent 3 env: a2 1a3 3T3 Reaction r1has empty inhibitor set, so the corresponding r-agent has no program to apply in this configuration. There is one inhibitor, a2, in inhibitor set of reaction r2and because a2is not present in the environment, therefore r-agent 2 has no applicable program in current configuration. Due to the presence of a1in C0, the third reaction is not enabled by C0and r-agent 3 has one program to execute. The agent consumes object a1from the environment. 5 : T R r-agent 1 T R r-agent 2 e C r-agent 3 e10 t-agent 1 e10 t-agent 2 e10 t-agent 3 env: a2 1a3 3T 6 : e R0 0 r-agent 1 e R0 0 r-agent 2 C T r-agent 3 e20 t-agent 1 e20 t-agent 2 e20 t-agent 3 env: a2 1a3 3 Those agents which have object Rinside can continue the simulation of executing reaction by search for reactants. All reactants must be present in the environment to enable reaction. For every reaction we make a sequence of reactants (aj)k j=1 in random order. Then we can construct programs for search for reactants phase: r-agents b) search for reactants e↔aj/ e →F;R0 j−1→Rjaj∈Rr; 1 ≤j≤ |Rr| aj→e;Rj→R0 jaj∈Rr; 1 ≤j≤ |Rr| F→F;R0 j−1→Rj1< j ≤k F→F;Rj→R0 j1≤j≤k e→e;R0 j−1→Rj|Rr|< j ≤k e→e;Rj→R0 j|Rr|< j ≤k hF→e;R0 k→ei In the example P colony, we develop, the search for reactants is performed as follows: 74 Lucie Ciencialov´a, Ludˇek Cienciala, and Erzs´ebet Csuhaj-Varj´u 0 : e R0 0 r-agent 1 e R0 0 r-agent 2 C T r-agent 3 env: a2 1a3 3 1 : F R1 r-agent 1 a1R1 r-agent 2 e e r-agent 3 env: a1a3 3 2 : F R0 1 r-agent 1 e R0 1 r-agent 2 e e r-agent 3 env: a1a3 3 3 : F R2 r-agent 1 a3R2 r-agent 2 e e r-agent 3 env: a1a2 3 4 : F R0 2 r-agent 1 e R0 2 r-agent 2 e e r-agent 3 env: a1a2 3 Only r-agents in state (e, R0 k) can continue the simulation. They consumed all the reactants and because they pass the phase a) the corresponding reaction is enabled by Wi. In phase of products generation the r-agents will generate and put into environment ”semi-products”, i.e. objects corresponding to products. For this purpose, we also need a sequence of products for each reaction. r-agents c) generation of products he→a0 1;R0 k→P1i e→a0 j;P0 j−1→Pjaj∈Pr; 1 < j ≤ |Pr| e↔a0 j;Pj→P0 jaj∈Pr; 1 ≤j≤ |Pr| e→e;P0 j−1→Pj|Pr|< j ≤m e→e;Pj→P0 j|Pr|< j ≤m he→e;P0 m→ei 0 : F R0 2 r-agent 1 e R0 2 r-agent 2 e e r-agent 3 env: a1a2 3 1 : e e r-agent 1 a0 1P1 r-agent 2 e e r-agent 3 env: a1a2 3 P Colonies and Reaction Systems 75 2 : e e r-agent 1 e P0 1 r-agent 2 e e r-agent 3 env: a0 1a1a2 3 3 : e e r-agent 1 a0 2P2 r-agent 2 e e r-agent 3 env: a0 1a1a2 3 4 : e e r-agent 1 e P0 2 r-agent 2 e e r-agent 3 env: a0 1a0 2a1a2 3 3 : e e r-agent 1 e e r-agent 2 e e r-agent 3 env: a0 1a0 2a1a2 3 4. Consuming phase In this phase all unused over-lined objects are consumed by c-agents as well as copies of ”semi-products”. Only one copy of semi-product stays in the environment. The number of c-agents is |S|and this phase takes at most 4|A|steps. he↔D;e→eie↔aj/ e ↔a0 j;D→a00 j aj→e;a00 j→a00 j e↔aj/ e ↔a0 j;a00 j→a00 j a0 j→a0 j;a00 j↔e e↔a0 j/ e ↔e;a0 j→e he↔E;e→ei hD→e;e↔Ei a00 j→e;e↔EhE→e;e→ei 0 : e e c-agent 1 e e c-agent 2 e e c-agent 3 e0D i-agent 1 e0D i-agent 2 e0D i-agent 3 env: a0 1a0 2a1a2 3D3 1 : D e c-agent 1 D e c-agent 2 D e c-agent 3 F13 000 i-agent 1 F13 000 i-agent 2 F13 000 i-agent 3 env: a0 1a0 2a1a2 3 2 : a1a00 1 c-agent 1 a0 2a00 2 c-agent 2 a3a00 3 c-agent 3 env: a0 1a3 3 : e a00 1 c-agent 1 a0 2e c-agent 2 e a00 3 c-agent 3 env: a0 1a00 2a3 76 Lucie Ciencialov´a, Ludˇek Cienciala, and Erzs´ebet Csuhaj-Varj´u 4 : a0 1a00 1 c-agent 1 e e c-agent 2 a3a00 3 c-agent 3 env: a00 2 5 : a0 1e c-agent 1 e e c-agent 2 e a00 3 c-agent 3 env: a00 1a00 2 6 : e e c-agent 1 e e c-agent 2 e a00 3 c-agent 3 env: a00 1a00 2 · · · 9 : e e c-agent 1 e e c-agent 2 e a00 3 c-agent 3 env: a00 1a00 2 10 : e e c-agent 1 e e c-agent 2 e a00 3 c-agent 3 F22 000 i-agent 1 F22 000 i-agent 2 F22 000 i-agent 3 env: a00 1a00 2 11 : e e c-agent 1 e e c-agent 2 e a00 3 c-agent 3 E0E i-agent 1 E0E i-agent 2 E0E i-agent 3 env: a00 1a00 2 12 : e e c-agent 1 e e c-agent 2 e a00 3 c-agent 3 e0E i-agent 1 e0E i-agent 2 e0E i-agent 3 env: a00 1a00 2E3 13 : E e c-agent 1 E e c-agent 2 E a00 3 c-agent 3 e1 i-agent 1 e1 i-agent 2 e1 i-agent 3 env: a00 1a00 2 In this configuration, c-agents rewrite all objects inside them to environmental objects. Simulation can continue with the first phase - generation of input. The i-agents can consume objects of a type a00 jand they put into the environment objects ajand objects of the next input (if they are not included in products of previous step). P Colonies and Reaction Systems 77 3 Conclusions In this paper we presented the result obtained by examining P colonies with connection to R systems. In future research we plan further investigation of P colonies that resemble reaction systems in terms of shared environment and computation. Acknowledgments. The work of L. Ciencialov´a and L. Cienciala was supported by The Ministry of Education, Youth and Sports from the National Programme of Sustainability (NPU II) project IT4Innovations excellence in science - LQ1602, by SGS/11/2019. References 1. Ciencialov´a, L., Csuhaj-Varj´u, E., Cienciala, L., and Sos´ık, P.: P colonies. Bulletin of the International Membrane Computing Society 1(2):119–156 (2016). 2. Csuhaj-Varj´u, E., Kelemen, J., Kelemenov´a, A., P˘aun, Gh., Vaszil, Gy.: Computing with cells in environment: P colonies. Journal of Multiple-Valued Logic and Soft Computing 12(3-4 SPEC. ISS.), pp. 201–215 (2006) 3. Csuhaj-Varj´u, E., Kelemen, J., P˘aun, Gh., Dassow, J.(eds.): Grammar Systems: A Grammatical Approach to Distribution and Cooperation. Gordon and Breach Science Publishers, Inc., Newark, NJ, USA (1994) 4. Ehrenfeucht, A., Rozenberg, A.: Basic notions of reaction systems. In: Calude, C.S., Calude, E., Dinneen, M.J. (Eds.), Developments in Language Theory, 8th International Conference, DLT 2004. In: Lecture Notes in Computer Science, vol.3340, Springer, 27-–29 (2005) 5. Kelemenov´a, A.: P Colonies. Chapter 23.1, In: P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.) The Oxford Handbook of Membrane Computing, pp. 584–593. Oxford University Press (2010) 6. Kelemen, J., Kelemenov´a, A.: On P colonies, a biochemically inspired model of computation. In: Proc. of the 6th International Symposium of Hungarian Researchers on Computational Intelligence, Budapest TECH. pp. 40–56. Hungary (2005) 7. Kelemen, J., Kelemenov´a, A., P˘aun, G.: Preview of P Colonies: A Biochemically Inspired Computing Model. In: Workshop and Tutorial Proceedings. Ninth International Conference on the Simulation and Synthesis of Living Systems (Alife IX). pp. 82–86. Boston, Mass (2004) 8. Kelemen, J., Kelemenov´a, A.: A Grammar-Theoretic Treatment of Multiagent Systems. Cybern. Syst. 23(6), 621–633 (1992), 9. P˘aun, Gh., Rozenberg, G., Salomaa, A.(eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA (2010) 10. Rozenberg, G., Salomaa, A.(eds.): Handbook of Formal Languages I-III. Springer Verlag., Berin-Heidelberg-New York (1997) Extracting Parallelism in Simulation Algorithms for PDP systems Miguel ´ A. Mart´ınez-del-Amor, Andr´es Doncel-Ram´ırez, David Orellana-Mart´ın, Ignacio P´erez-Hurtado Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected], [email protected], [email protected], [email protected] Summary. Population Dynamics P systems is a modelling framework that have been used successfully for some important real ecosystems. This model is inherently probabilistic, and the scheme of rules is very flexible, allowing even cooperation between membranes. Thus, its simulation has been a challenge in the past years, leading to several simulation algorithms. The latest one, which has been proved to be the most accurate so far, is DCBA. The main drawback of DCBA is its complexity, requiring a very large table to handle all competitions. In this paper, we discuss two strategies to decrease this table, allowing a more lightweight version of DCBA that can be used in parallel implementations. Keywords: Membrane Computing, Population Dynamics, Parallel simulation 1 Introduction Some very important real ecosystems have been modelled using the formal framework called Population Dynamics P (PDP) systems [8, 6]. This framework consists of a multienvironment P system model [11] that contains one single cell-like P system within the nodes (environments) of a directed graph. Each of the celllike P systems have the same skeleton (membrane tree and evolution rules). Thus, PDP systems have to kinds of rules: evolution (skeleton) and communication rules. Moreover, PDP systems is a probabilistic model, in the sense that probabilities are associated with the rules. Skeleton rules may have associated different probabilities regarded the environment where they are located. The very flexible pattern of skeleton rules, where object cooperation can happen even between membranes (the active membrane and its parent), increases the complexity when designing simulation algorithms. For this reason, several 86 MA Mart´ınez-del-Amor et al. Algorithm 3 DCBA MAIN LOOP FOR ENVIRONMENTS AND MODULES Require: A PDP system Πof degree (q, m), T≥1 (time units), A≥1 (accuracy parameter), an initial configuration C0, the number of time units per cycle c, the amount of modules d, a structure mapping the rules and blocks per module MR, and another structure mapping which module is active at each step in the cycle MS. 1: for j←1to mdo .(For each environment j) 2: for k←1to ddo .(For each module k) 3: (Tj,k)←INITIALIZATION (j,Π,k,MR).(Creates the table for environment j and module k) 4: end for 5: end for 6: t←0 7: while t < T do .(For each transition step) 8: for t←tto t+c−1do .(Looping the transition steps inside a cycle) 9: s←t mod c .(The step within the cycle) 10: for j←1to mdo .(For each environment j) 11: for k←1to ddo .(For each module k) 12: SELECTION: .(Selection for environment j and module k) 13: if MS[k, s]then .(If module k is active in step s) 14: Bj,k sel ← ∅,Rj,k sel ← ∅ 15: (Tt j,k, C0 t, Bj,k sel )←PHASE 1 (j, Π, A, Ct,Tj,k, k, MR) 16: (C0 t, Bj,k sel )←PHASE 2 (j, Π, C0 t, Bj,k sel ,Tt j,k, k, MR) 17: (Rj,k sel)←PHASE 3 (j, Π, Bj,k sel , k, MR) 18: end if 19: end for 20: end for 21: for j←1to mdo .(For each environment j) 22: for k←1to ddo .(For each module k) 23: EXECUTION: .(Execution for environment j and module k) 24: if MS[k, s]then .(If module k is active in step s) 25: (Ct+1)←PHASE 4 (j, Π, C0 t, Rj,k sel, k, MR) 26: end if 27: end for 28: end for 29: end for 30: end while Section 2). Let us represent the competition relationship as an undirected graph Gc= (Vc, Ec), where Vcis the set of all rule blocks and Eis the set of edges connecting the blocks that directly compete one with each other. We will therefore say that two blocks will compete, directly or indirectly, if there exists a path between them. Thus, we can calculate partitions of competitions from the set of rule blocks as depicted in Definition 4. Definition 4. Given a set of rule blocks V={B1, . . . , Bk}, a partition of competition is a partition of the set V,P={P1, . . . , Pl}, where the following holds: Extracting Parallelism in Simulation Algorithms for PDP systems 87 a block Bibelongs to the set Piif and only if it competes, directly or indirectly, with the rest of blocks in Ci, and do not compete with any of the rule blocks form the rest of sets in P. The union of the sets in P is V. Specifically, communication rule blocks form partitions with just one element. It is easy to compute the partitions of competitions from the set of rule blocks by calculating the connected components in the graph Gc. After having this, we can redefine the DCBA algorithm to be executed locally to each partition, if it contains more than one elements (also known as µ-DCBA). Generally, we can re-structure the algorithm as shown in Algorithm 4. Algorithm 4 DCBA MAIN LOOP FOR ENVIRONMENTS AND PARTITIONS Require: A PDP system Πof degree (q, m), T≥1 (time units), A≥1 (accuracy parameter), and an initial configuration C0. 1: (p, P )←PARTITIONS (Π).(Compute the ppartitions of rules in the map P) 2: for j←1to mdo .(For each environment j) 3: for i←1to pdo .(For each partition i) 4: (Tj,i)←INITIALIZATION (j,Π,i,P).(The table for environment j and partition i) 5: end for 6: end for 7: for t←0to T−1do .(For each transition step) 8: for j←1to mdo .(For each environment j) 9: for i←1to pdo .(For each partition i) 10: SELECTION: .(Selection for environment j and partition i) 11: Bj,i sel ← ∅,Rj,i sel ← ∅ 12: (Tt j,i, C0 t, Bj,i sel)←PHASE 1 (j, Π, A, Ct,Tj,i, i, P ) 13: (C0 t, Bj,i sel)←PHASE 2 (j, Π, C0 t, Bj,i sel,Tt j,i, i, P ) 14: (Rj,i sel)←PHASE 3 (j, Π, Bj,i sel, i, P ) 15: end for 16: end for 17: for j←1to mdo .(For each environment j) 18: for i←1to pdo .(For each partition i) 19: EXECUTION: .(Execution for environment j and partition i) 20: (Ct+1)←PHASE 4 (j, Π, C0 t, Rj,i sel, i, P ) 21: end for 22: end for 23: end for Preliminary results show an improvement of around 2x of extra speedup when using the partitions to find more parallelism on a K40c GPU with a model of the Bearded Vulture in the Pyrenees [10, 4]. This means that the µ-DCBA implementations usually runs twice faster than the GPU baseline simulator [15]. 88 MA Mart´ınez-del-Amor et al. 6 Conclusions and Future Work PDP systems are a formal framework for ecosystem modelling, whose applications require efficient software simulators. In this concern, GPU-accelerated simulators have been developed so far. However, the designed algorithms for PDP systems, specially DCBA, have several bottlenecks. On the one hand, DCBA assumes that all rules in the system will depend on each other when consuming the left-hand sides. However, this is not always the case, and we can pre-compute partitions of rules actually competing for objects. On the hand, the model designer knows which rules will be applied at each step. An adaptative simulator should be able to use this information to dismiss rules that are known to be non applicable in a certain step. We have shown how to modify DCBA main loop when implementing these two ideas (adaptative DCBA and DCBA with partitions). These strategies lead to extra speedups (compared with the GPU baseline simulator) of around 2x-2.5x. Let us remark that a simulator implementing these two modes should be used carefully: •An adaptative simulator of PDP system should be used when deploying a validated model. That is, when the model is already refined and validated by the designer, and the behaviour is already known and proved to work. For example, when using the simulator in virtual experimentation environments. •A simulator with partitions of PDP systems (e.g. µ-DCBA) can be used not only in virtual experimentation environments, but also in the validation of the model. That is, when the designer is still debugging the model, this strategy can help since it works automatically from the set of rules. However, the performance is not as good as with adaptative simulators (according to our preliminary results), and would require some initial pre-computation for partitions. Future work includes the development of a µ-DCBA in a stable simulator along with the already existing adaptative simulator. Moreover, we plan to use these improvements to go to the next step and implement parallel parameter calibration methods for the models. We are also working on an automatic inclusion of the GPU simulators inside generic simulation tools such as MeCoSim and P-Lingua, since the only way to use these tools is by a manual protocol [18]. Finally, we are looking into further improvements of the GPU adaptative simulators by including features such as for object counters [2]. Acknowledgements This work was supported by the research project TIN2017-89842-P (MABICAP), co-financed by Ministerio de Econom´ıa, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigaci´on (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union. Extracting Parallelism in Simulation Algorithms for PDP systems 89 References 1. Alhazov, A.: Maximally parallel multiset-rewriting systems: Browsing the configurations. In: Proceedings of the Third Brainstorming Week on Membrane Computing. pp. 1–10. F´enix Editora, Seville, Spain (February 2005), http://www.gcn.us.es/ 3BWMC/bravolpdf/bravol1.pdf 2. Mart´ınez-del Amor, M.´ A., Orellana-Mart´ın, D., P´erez-Hurtado, I., Valencia-Cabrera, L., Riscos-N´u˜nez, A., P´erez-Jim´enez, M.J.: Design of specific P systems simulators on GPUs. In: Hinze, T., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) Membrane Computing. pp. 202–207. Springer International Publishing, Cham (2019) 3. Mart´ınez-del Amor, M.A., P´erez-Hurtado, I., Garc´ıa-Quismondo, M., Mac´ıas-Ramos, L.F., Valencia-Cabrera, L., Romero-Jim´enez, ´ A., Graciani, C., Riscos-N´u˜nez, A., Colomer, M.A., P´erez-Jim´enez, M.J.: DCBA: Simulating Population Dynamics P Systems with Proportional Object Distribution. In: Csuhaj-Varj´u, E., Gheorghe, M., Rozenberg, G., Salomaa, A., Vaszil, G. (eds.) Membrane Computing. Lecture Notes in Computer Science, vol. 7762, pp. 257–276. Springer Berlin Heidelberg, Berlin, Heidelberg (2013) 4. Cardona, M., Colomer, M.A., P´erez-Jim´enez, M.J., Sanuy, D., Margalida, A.: Modeling ecosystems using P systems: the bearded vulture, a case study. In: Corne, D., Frisco, P., P˘aun, G., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, Lecture Notes in Computer Science, vol. 5391, pp. 137–156. Springer Berlin Heidelberg (2009) 5. Colomer, M., P´erez-Hurtado, I., P´erez-Jim´enez, M., Riscos-N´u˜nez, A.: Comparing simulation algorithms for multienvironment probabilistic P systems over a standard virtual ecosystem. Natural Computing 11(3), 369–379 (2012) 6. Colomer, M.A., Margalida, A., Valencia-Cabrera, L., Palau, A.: Application of a computational model for complex fluvial ecosystems: The population dynamics of zebra mussel Dreissena polymorpha as a case study. Ecological Complexity 20, 116 – 126 (2014) 7. Colomer, M., Margalida, A., P´erez-Jim´enez, M.: Population Dynamics P System (PDP) Models: A Standardized Protocol for Describing and Applying Novel BioInspired Computing Tools 8(5), e60698 (2013) 8. Colomer, M., Margalida, A., Sanuy, D., P´erez-Jim´enez, M.J.: A bio-inspired computing model as a new tool for modeling ecosystems: The avian scavengers as a case study. Ecological Modelling 222(1), 33–47 (2011) 9. Colomer-Cugat, M.A., Garc´ıa-Quismondo, M., Mac´ıas-Ramos, L.F., Mart´ınez-del Amor, M.A., P´erez-Hurtado, I., P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A., ValenciaCabrera, L.: Membrane System-Based Models for Specifying Dynamical Population Systems, pp. 97–132. Springer International Publishing, Cham (2014) 10. Doncel-Ram´ırez, A.: Simulaci´on Acelerada de Sistemas P de Din´amica de Poblaciones con GPU. Master thesis (Universidad de Sevilla), july 2018 11. Garc´ıa-Quismondo, Manuel and Mart´ınez-del-Amor, M.A., P´erez-Jim´enez, M.J.: Probabilistic Guarded P Systems, A New Formal Modelling Framework. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Sos´ık, P., Zandron, C. (eds.) Membrane Computing. pp. 194–214. Lecture Notes in computer Science, Springer International Publishing, Cham (2014) 12. Mart´ınez-del-Amor, M., Mac´ıas-Ramos, L., Valencia-Cabrera, L., P´erez-Jim´enez, M.: Parallel simulation of Population Dynamics P systems: updates and roadmap 15(4), 565–573 (2015) 90 MA Mart´ınez-del-Amor et al. 13. Mart´ınez-del-Amor, M., P´erez-Hurtado, I., P´erez-Jim´enez, M., Riscos-N´u˜nez, A., Colomer, M.: A new simulation algorithm for multienvironment probabilistic P systems. In: IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2010). vol. 1, pp. 59–68 (September 2010) 14. Mart´ınez-del-Amor, M.A., Karlin, I., Jensen, R.E., P´erez-Jim´enez, M.J., Elster, A.C.: Parallel simulation of probabilistic P systems on multicore platforms. In: Proceedings of the Tenth Brainstorming Week on Membrane Computing. vol. II, pp. 17–26. F´enix Editora, Seville, Spain (February 2012), http://www.gcn.us.es/ 10BWMC/10BWMCvolII/papers/parallel-dcba.pdf 15. Mart´ınez-del-Amor, M.A., P´erez-Hurtado, I., Gastalver-Rubio, A., Elster, A.C., P´erez-Jim´enez, M.J.: Population Dynamics P Systems on CUDA. In: Gilbert, D., Heiner, M. (eds.) Computational Methods in Systems Biology, pp. 247–266. Lecture Notes in Computer Science, Springer Berlin Heidelberg (2012) 16. Mart´ınez-del-Amor, M.A., P´erez-Hurtado, I., Orellana-Mart´ın, D., P´erez-Jim´enez, M.J.: Adaptative parallel simulators for bioinspired computing models. Future Generation Computer Systems 107, 469 – 484 (2020) 17. P´erez-Hurtado, I., Orellana-Mart´ın, D., Zhang, G., P´erez-Jim´enez, M.J.: P-lingua in two steps: flexibility and efficiency. Journal of Membrane Computing 1(2), 93–102 (Jun 2019) 18. Valencia-Cabrera, L., Mart´ınez-del Amor, M.´ A., P´erez-Hurtado, I.: A Simulation Workflow for Membrane Computing: From MeCoSim to PMCGPU Through PLingua, pp. 291–303. Springer International Publishing, Cham (2018) 19. Zhang, G., Shang, Z., Verlan, S., Mart´ınez-del-Amor, M.A., Yuan, C., ValenciaCabrera, L., P´erez-Jim´enez, M.J.: An overview of hardware implementation of membrane computing models. ACM Comput. Surv. 53(4) (Aug 2020) An optimal solution to the SAT problem with tissue P systems David Orellana-Mart´ın, Luis Valencia-Cabrera, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {dorellana, lvalencia, marper}@us.es Summary. In the framework of membrane computing, several frontiers of efficiency have been found with respect to the resources that different families of P systems take to solve a decision problem. Each of these frontiers provides a new way to tackle the Pversus NP problem. In this sense, optimal frontiers are needed in order to separate close variants of P systems. In a previous work, an efficient solution to SAT was given in the framework of P systems from T DC(3). In this work, we will provide an optimal solution to the SAT problem in terms of length of the rules. Key words: Membrane Computing, tissue P systems, symport/antiport rules, SAT problem. 1 Introduction One of the most prolific fields within the framework of Membrane Computing is computational complexity theory. The search for frontiers of efficiency has produced several results in terms of correspondences between classic computational complexity classes and membrane computing complexity classes. In particular, several results with tissue P systems [5] have been achieved. Recognizer tissue P systems were introduced in [6]. In [3], it was demonstrated that the complexity class of tissue P systems from T DC(1) are non-efficient systems through the dependency graph technique. In [6], an efficient solution to the SAT problem is given by means of a family of tissue P systems from T DC(5). In this work, we present an optimal solution for SAT with a family of tissue P systems from T DC(2). This implies that NP ∪co −NP ⊆PMCT DC(2). However, this last result is not new, since in [9] it was presented a solution to HAM-CYCLE, a well-known NP-complete problem, with a family of P systems from T DC(2). The novelty of this work is to present an efficient SAT solver, given the relevance of the problem. The paper is 92 D. Orellana, L. Valencia, M.J. P´erez organized as follows. In Section 2, some prerequisites about languages and sets are given. The next section is devoted to introduce tissue P systems, and the complexity classes associated to them. In Section 4, an efficient solution to SAT by means of tissue P systems from T DC(2) is given, and in the next section an overview of the computations is given. Finally, the work finishes with some conclusions. 2 Preliminaries An alphabet Γis a non-empty set whose elements are called symbols. A string u over Γis an ordered finite sequence of symbols; that is, a mapping from a natural number n∈Nonto ΓThe number nis called the length of the string uand it is denoted by |u|The empty string (with length 0) is denoted by λ. The set of all strings over an alphabet Γis denoted by Γ∗. A language over Γis a subset of Γ∗. Amultiset over an alphabet Γis an ordered (Γ, f) where fis a mapping from Γ onto the set of natural numbers N. The support of a multiset m= (Γ, f) is defined as supp(m) = {x∈Γ|f(x)>0}. A multiset is finite (respectively, empty) if its support is a finite (respectively, empty) set. We denote by ∅the empty multiset. Let m1= (Γ, f1), m2= (Γ, f2) be multisets over Γ, then the union of m1and m2, denoted by m1+m2, is the multiset (Γ, g) where g(x) = f1(x) + f2(x) for each x∈Γ. The difference of m1and m2, denoted by m1\m2, is the multiset (Γ, g) where g(x) = f1(x)−f2(x) for each x∈Γ. We denote by M(Γ) the set of all multisets over Γ. The Cantor pairing function is used to encode two natural numbers into a single one, and is defined as follows: given x, y ∈N,hx, yi=(x+y+1)(x+y) 2+y 3 Tissue P systems with symport/antiport rules Definition 1. A recognizer tissue P system with symport/antiport rules and division rules of degree q≥1is a tuple Π= (Γ, Σ, E,M1,...,Mq,R, iin, iout), where: 1. Γ,Σand Eare finite alphabets such that Σ, E ⊆ Γand Σ∩ E =∅. 2. M1,...,Mqare multisets over Γ\(Σ∪ E). 3. Ris a set of rules of the following types: (a) Communication rules: (i, u/v, j), for i, j ∈ {0,1, . . . , q}, i 6=j, u, v ∈ M(Γ),|u|+|v|>0. (b) Division rules: [a]i→[b]i[c]i, for i∈ {1, . . . , q}, a, b, c ∈Γ. 4. iin ∈ {1, . . . , q}and iout =env. A recognizer tissue P system with symport/antiport rules and division rules Π= (Γ, Σ, E,M1,...,Mq,R, iin, iout) of degree q≥1 can be viewed as a se of qcells, labelled by 1, . . . , q with an environment labelled by 0 such that: (a) An optimal solution to the SAT problem with tissue P systems 93 M1, . . . Mqare the multisets of objects initially placed in the qcells of the system; (b) Eis the set of objects located initially placed in the environment of the system, all of them appearing in an arbitrary number of copies; and (c) iin ∈ {1, . . . , q}, iout =env represent distinguished cells where objects of the instance are introduced and which will encode the output of the system, respectively. When applying a rule (i, u/v, j), the objects of the multiset represented by u are sent from region ito region jand, simultaneously, the objects of multiset vare sent from region jto region i. The length of the communication rule (i, u/v, j) is defined as |u|+|v|, that is, the total number of objects which appear in the rule. A communication rule (i, u/v, j) is called a symport rule if u=λor v=λ. A symport rule (i, u/λ;j), with i6= 0, j 6= 0 provides a virtual arc from cell ito cell j. A communication rule (i, u/v, j) is called an antiport rule if u6=λand v6=λ. An antiport rule (i, u/v, j), with i6= 0, j 6= 0, provides two arcs: one from cell i to cell jand another one from cell jto cell i. Thus, every tissue P systems has an underlying directed graph whose nodes are the cells of the system and the arcs are obtained from communication rules. In this context, the environment can be considered as a virtual node of the graph such that their connections are defined by communication rules of the form (i, u/v, j), with i= 0 or j= 0. When applying a division rule [ a]i→[b]i[c]i, cell iis duplicated into two new cells with the same label. Object adissapears and an object bis created in the first new cell and an object cis created in the second new cell. The rest of the objects within the cell iare duplicated in the two new cells. The rules of a system like the one above are used in a non-deterministic maximally parallel manner as it is customary in Membrane Computing. At each step, all communication rules which can be applied will be applied in a maximally parallel way (at each step we apply a multiset of rules which is maximal, no further applicable rule can be added). Only a single division rule can be applied to each cell. If a division rule is applied to a cell, we say that this cell is is “blocked”, and no communication rules can be applied to that cell in that computational step. An instantaneous description or a configuration at any instant of a tissue P system is described by all multisets of objects over Γassociated with all the cells present in the system, and the multiset of objects over Γ\ E associated with the environment at that moment. Bearing in mind that the objects from E have infinite copies in the environment, they are not properly changed along the computation. The initial configuration is (M1,...,Mq;∅). A configuration is a halting configuration if no rule of the system is applicable to it. Let us fix a tissue P system with symport/antiport rules Π. We say that configuration Ciyields configuration Ci+1 in one transition step, denoted Ci⇒ΠCi+1, if we can pass from Cito Ci+1 by applying the rules from Rfollowing the previous remarks. A computation of Πis a (finite or infinite) sequence of configurations such that: (a) the first term of the sequence is an initial configuration of the system; (b) each non-initial configuration of the sequence is obtained from the previous configuration by applying the rules of the system in a maximally parallel manner with the restrictions previously mentioned; and (c) if the sequence is finite (called 94 D. Orellana, L. Valencia, M.J. P´erez halting computation), then the last term of the sequence is a halting configuration. All computations start from an initial configuration and proceed as stated above;only halting computations give a result, which is encoded by the objects present in the environment in the halting configuration. Given that they are recognizer P systems, all computations halt and return the same output. We denote a recognizer membrane system Πwith the input multiset min the input region as Π+m. 3.1 Complexity classes associated to tissue P systems Let Rbe a class of recognizer membrane systems. We say that PMCRis the class of problems solvable efficiently in a uniform way by means of a family of recognizer membrane systems from R. The class of recognizer tissue P systems with symport/antiport rules with length at most kand division rules is denoted by T DC(k), k ≥1. For more information about computational complexity theory in the framework of membrane computing, we refer the reader to [7, 8]. 4 A solution to SAT in T DC(2) In this section, an efficient solution to the SAT problem by means of a family of P systems will cell division and symport/antiport rules of length at most 2 is presented. For each pair of natural numbers n, p ∈N, we will consider the recognizer tissue P system with cell division and symport/antiport rules Π(hn, pi)=(Γ, E, Σ, M1,...,Mnp+3,R, iin, iout) of degree np + 3 defined as follows: (a) Γ=Σ∪ E ∪ {yes,no, α, β0, γ0}∪{cj|1≤k≤p} ∪ {αk|0≤k≤np −1}∪{ai,j |1≤i≤n, 1≤j≤p} ∪ {Ti,j, Fi,j |1≤i≤n, 1≤j≤p} ∪ {xi,j,k, xi,j,k |1≤i≤n, 1≤j≤p, 0≤k≤np} (b) E={αk|np ≤k≤2np + 2}∪{βk|1≤k≤2np + 4} ∪ {γk|1≤k≤2np + 5}∪{xi,j,k, xi,j,k |1≤i≤n, 1≤j≤p, np + 1 ≤k≤2np} (c) Σ={xi,j,0, xi,j,0|1≤i≤n, 1≤j≤p} (d) Mi=∅for 1 ≤i≤np,Mnp+1 ={yes,no, β0, γ0},Mnp+2 ={ai,j |1≤i≤ n, 1≤j≤p}∪{cj|1≤j≤p}∪{α},Mnp+3 ={α0}. (e) The set of rules Ris the following: 1. Rules to generate pcopies of the 2ntrue possible truth assignments. For this, 2np partial truth assignments will be generated. [ai,j ]np+2 →[Ti,j ]np+2[Fi,j ]np+2 (np + 2, Ti,jFi,j0, /λ, env)for 1≤i≤n, 1≤j, j0≤p An optimal solution to the SAT problem with tissue P systems 95 2. Rules to generate 2np copies of cod(ϕ). (np + 1, xi,j,0/λ, i +n·(j−1)) (np + 1, xi,j,0/λ, i +n·(j−1))for 1≤i≤n, 1≤j≤p [xi,j,k ]i+n·(j−1) →[xi,j,k+1 ]i+n·(j−1)[xi,j,k+1 ]i+n·(j−1) [xi,j,k ]i+n·(j−1) →[xi,j,k+1 ]i+n·(j−1)[xi,j,k+1 ]i+n·(j−1) for 1≤i≤n, 1≤j≤p, 0≤k≤np −1 (i+n·(j−1), xi,j,k/xi,j,k+1, env) (i+n·(j−1), xi,j,k/xi,j,k+1, env)for 1≤i≤n, 1≤j≤p, np ≤k≤2np −1 3. Rules to check which clauses are satisfied by the truth assignment (np + 2, Ti,j/xi,j,2np, i +n·(j−1)) (np + 2, Fi,j/xi,j,2np, i +n·(j−1))for 1≤i≤n, 1≤j≤p (np + 2, cjxi,j,2np/λ, env) (np + 2, cjxi,j,2np/λ, env)for 1≤i≤n, 1≤j≤p [αk]np+3 →[αk+1 ]np+3 [αk+1 ]np+3 for 0≤k≤np −1 (np + 3, αnp+k/αnp+k+1, env)for 0≤k≤np + 1 (np + 1, βk/βk+1, env)for 0≤k≤2np + 3 (np + 1, γk/γk+1, env)for 0≤k≤2np + 4 (np + 2, α/α2np+2, np + 3) (np + 2, α2np+2cj/λ, env)for 1≤j≤p 4. Rules to return a negative answer (np + 1, β2np+4, γ2np+5/λ, np + 3) (np + 1,no/β2np+4, np + 3) (np + 3,no/λ, env) 5. Rules to return a positive answer (np + 1, β2np+4/α2np+2, np + 2) (np + 1, α2np+2yes/λ, env) (f) iin =np + 1 and iout =env 5 An overview of the computations In this section, we will explain a brief overview of the computations. Let ϕbe a propositional logic formula in conjunctive normal form, where V ar(ϕ) = {x1, . . . , xn}. Then, ϕis of the form ϕ=C1∧. . . ∧Cp, where Cj is a clause such that Cj=l1,j ∨. . . lpj,j, li,j ∈ {xi,¬xi}. The pair (cod, s) for this family is cod(ϕ) = {xi,j |xi∈Cj}∪{xi,j | ¬xi∈Cj}, and s=hn, pi. For that, let us remember that the input is an instance of the SAT problem. Let ϕthe input formula with nvariables and pclauses. The tissue P system that will give the answer to the instance is Π(hn, pi) + cod(ϕ). 102 Gheorghe P˘aun (Q1) There are plenty of open problems and research topics formulated in the MC literature. Some of these problems were solved, some of these research vistas were explored, many others might be now obsolete, of no much interest, but many enough still wait for research efforts. For instance, I would like to recall the attention about the problems collected in [2], also available in a preliminary form in a Brainstorming volume, [1]. I believe that a nice and useful analysis would be to systematically examine the proposals from this paper and see the status of each of them, thus revealing the topics which need/deserve our attention from now on. (Q2) The previous idea was to look to the past – now I would like to suggest to look to the future... With the mentioning that the future started yesterday... It is about the Fourth Industrial Revolution. The key-words describing it are of the kind: connectivity, artificial intelligence, machine learning, cyber-systems, robots. Which of these syntagma are “reachable” by MC, which were already addressed, which suggestions can we get from this direction? Very general questions, but a good answer can have rather positive consequences. What about a “very distributed” P system/colony, about swarms of membranes? Much work is still needed in the learning (deep learning?) direction. Both these issues can have nice practical applications (the same with evolutionary computing, membrane algorithms and connected areas, making use of the “brute force” brought into the stage by the complex systems of weak components cooperating in a cleaver manner). 3 Three “Hybridization” Suggestions Suggestions of the forms bellow were formulated many times, in more general or more specific terms. I recall them, with some further details. (Q3) Systematic comparison of “basic” classes of P systems – cell-like, tissuelike, spiking neural, and numerical, with multiset rewriting rules, active membranes, symport/antiport, spiking rules, programs (production-repartition) rules, respectively, with various specific features – catalysts, polarizations, regular expression guarding the (spiking) rules, unique object (the spike), etc. Many combinations of these ingredients were considered – but not all of them and not in a systematic manner. We know, for instance, the power (also the efficiency?) of one-object cell-like P system, or of cell-like SN P systems, but I no not remember papers examining numerical P systems using only one variable (in each region), or using the notion of anti-matter. A biological detail which is not satisfactorily captured in SN P systems is the sigmoidal function involved in the spiking operation. Maybe by borrowing the way of evolving variables in numerical P systems and using “programs” (again: with two parts, producing and then distributing) in SN P systems one can obtain something of interest. Seven Research Suggestions 103 (Q4) Bridging P and R was requested for several times and there are some attempts in this direction, but for sure much more remains to be done. The two areas are rather connected (cell-structure, evolution rules, biochemical metaphor), but they also differ in essential details (multisets, active membranes, symport/antiport and spiking rules, etc. in MC, zero or arbitrarily large multiplicity, no-surviving principle, different goals than computing, etc., in reaction systems). Borrowing notions investigated in R and investigating them for P (which of them make sense? which of them are decidable?) was suggested many times. Let me formulate one really “hybridization” idea: in R systems, the evolution is influenced by the environment, which provides arbitrary (multi)sets of objects to the system; what about having these objects produced by a P system – or by several P systems. The idea is illustrated in Figure 1. Of course, the P systems work “in the MC style” (multisets, maximal parallelism, objects that do not evolve persist, etc.) while Ris a reaction system. Plenty of questions appear: examine the usual R questions for such a hybrid system; what about computability in this framework? (the first question is how to define the result of a computation); what about the case when the P systems not only send objects to the environment, but they can also bring objects back inside? what about using simple P systems (non-universal), or of various types? in the case of SN P systems, we will have two possibilities: to distinguish between the spikes of various SN P systems or not – in the latter case, the R system is supposed to get only one (type of) object from the environment; how R systems with only one object in their alphabet behave? Find other types of P-R hybrid systems. ' & $ %             # " ! @ @R     @ @I Π1Π2 Π3Π4 R Fig. 1. (Q5) A similarly promising topic, partially, but not enough explored, is that of bringing to MC further notions from the quantum area. Two immediate ideas are the following. 104 Gheorghe P˘aun 1. To consider P systems with qobjects, objects having a name and a probability associated, a number between 0 and 1: (a, α), a ∈A, 0≤α≤1. Taking αas a “standard” probability does not seem to be very productive (there are some attempts of this kind). Maybe processing the objects with rules of the form a→(b, β)(c, γ), β, γ ∈[−1,1], with the effect (a, α)→(b, α ⊕β)(c, α ⊕γ),where α⊕δ=(0,if α+δ < 0, α+δ, if 0 ≤α+δ≤1, 1,if α+δ > 1, might be more interesting. Maybe also a multiplicative operation can be considered. How to define a successful computation? By halting? And which could be the result of a computation? (Maybe the distance between two prescribed events, without halting, maybe the string of objcts which reach probability 1.) Should the objects of the form (a, 0) be preserved in the system or they should be eliminated? 2. The second idea refers to objects as well, but also to their evolution: entanglement. Define objects which have identical evolution, irrespective where they are placed. There is no obvious definition – e.g., in the case of cooperative rules. Should entanglement be hereditary? (Copies of the same object, having a common ancestor, should be necessarily entangled?) A good definition is the first step – after that, questions about computing power and efficiency are to be formulated. Is entanglement a further door towards efficiency? (Entanglement means, in some sense, sending signals at an arbitrary distance in no time, which looks to be a powerful operation.) Maybe entanglement combined with the idea of qobjects? Maybe also imitating efficiency ideas from quantum computing? 4 Two More Precise Proposals (Q6) There is a fundamental feature of P systems which, in some sense, is departing from the (bio)chemistry: the localization of evolution rules. In theoreticalabstract terms, the (bio)chemistry is the same everywhere, the “dictionary” of reactions is unique. What is applicable-active in a given “reactor” (compartment of a cell) is selected according to the local reactants, enzymes, catalysts, promoters and inhibitors, as well as according to the reaction conditions (e.g., temperature). This directly leads to the idea of homogeneity, of considering P systems, of any kind, with the same set of rules in each compartment. The idea was investigated for many classes of P systems, but not for numerical P systems. I am also not aware of efficiency results for homogeneous P systems. Seven Research Suggestions 105 The same for the various ways of using the rules (semantics): maximally parallel, sequential, minimally parallel – whatever definition for these notions is chosen. What about a sort of an additional “uniform” restriction of the following form: if Pis the homogeneous set of rules present in all compartments (instead of using different rules in different compartments, depending on the local reactants and “reaction conditions”), choose a subset P0⊆P(maximal?) and use it (in the maximally parallel way, etc.) in all compartments. Power and efficiency results should be looked for. (Q7) Still more specific is the last question: consider SN P systems with astrocytes producing calcium, with calcium directly involved in the spiking activity. Formally, the system will contain two types of cells, astrocytes α1, . . . , αm,of the form (cpi,0, Ai), pi,0≥0, with the rules in Aiof the form Ec/cs→ct, s ≥1, t ≥0,and neurons σ1, . . . , σn,of the form (ari,0, Ri), ri,0≥0, with the rules in Riof the form Ea/ascs0→at, s, s0≥1, t ≥0, where Ec, Eaare regular expressions over the one-letter alphabets consisting of c and a, respectively. The idea is clear: producing tspikes in a neuron means consuming both sspikes and s0calcium units. The synapses should link either astrocytes or neurons, as well astrocytes to neurons (but not conversely: links (σi, αj) are not permitted). Of course, versions are possible: with the regular expressions in neurons also depending on the calcium units (hence over the alphabet {a, c}), with delay, with or without the possibility of replicating calcium, when an astrocyte sends objects cto several neurons. Now, the whole investigation program usual in the SN P systems area should be explored: normal forms, universality, small universal systems, plasticity, homogeneity, etc. Are astrocytes of this form improving the results known for usual SN P systems? 5 Final Remarks This note had two main goals: to show that still there is much work to do in membrane computing, even at this basic level (not to speak about applications, which is by far the most promising and most important direction of research at this stage), and to recall again and again that a very important task of all of us at this moment is to... write-read-cite, supporting our journal JMC!... Acknowledgements. This work was supported by the research project TIN201789842-P (MABICAP), co-financed by Ministerio de Econom´ıa, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigaci´on (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union. 106 Gheorghe P˘aun References 1. M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez (Eds.) Frontiers of Membrane Computing. Open Problems and Research Topics, Proc. 10th BWMC, Sevilla Univ., 2012, vol. 1, 171–249. 2. M. Gheorghe, Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg (Eds.) Frontiers of Membrane Computing. Open Problems and Research Topics, Intern. J. Found. Computer Sci., 24, 5 (2013), 547–623. Some open problems for application of spiking neural P systems Hong Peng School of Computer and Software Engineering, Xihua University, Chengdu, China E-mail: [email protected] Recently, three variants of spiking neural P systems have been proposed: coupled neural P systems (CNP systems) [1], dynamic threshold neural P systems (DTNP systems) [2] and nonlinear spiking neural P systems (NSNP systems) [3]. It was proven that the three variants are Turing universal number generating/accepting devices and function computing devices. The potential motivation of proposing the variants is to provide a modeling tool for real-life applications, for example, image processing tasks. Some open problems related to the variants are listed as follows. Q1 As stated in the existing SNP systems, some problems that refer to these variants can be investigated, for example, language generator, sequential and asynchronous modes. Q2 CNP systems and DTNP systems have all or part of spiking mechanism, coupling mechanism and dynamic threshold mechanism. How to apply the two variants to deal with some image processing tasks? for example, image fusion, image segmentation, object segmentation, feature extraction, object detection, and so on. Since image is two-dimensional (or three-dimensional for color image), CNT (or DTNP) systems can be considered as twodimensional (or three-dimensional) array of neurons. Moreover, due to local spatial characteristics of an image, local topological structure should be further considered. Q3 NSNP systems has a nonlinear spiking mechanism. Potentially, NSNP systems as a modelling tool could have the ability to handle nonlinear problems. Similarly, how to apply the variant to deal with these image processing tasks? Q4 Local convolutional structures are easily introduced into these variants with local topological structure, like convolutional neural networks (CNN). How to use them to build deep SNP systems? How to develop the corresponding learning algorithms? 108 Hong Peng References 1. H. Peng, J. Wang. Coupled neural P systems. IEEE Transactions on Neural Networks and Learning Systems, 2019, 30(6), 1672-1682. 2. H. Peng, J. Wang, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez. Dynamic threshold neural P systems. Knowledge-Based Systems 163, 2019, 875–884. 3. H. Peng, Z. Lv, B. Li, X. Luo, J. Wang, X. Song, T. Wang, M.J. P´erez-Jim´enez, A. RiscosN´u˜nez. Nonlinear spiking neural P systems, International Journal of Neural Systems, 2020. https://doi.org/10.1142/S0129065720500082 Modelling of Grey Wolf Optimization Algorithm Using 2D P Colonies Daniel Valenta1, Lucie Ciencialov´a1,2, and Ludˇek Cienciala1,2 1Institute of Computer Science, Silesian University in Opava, Czech Republic 2Research Institute of the IT4Innovations Centre of Excellence, Silesian University in Opava, Czech Republic {daniel.valenta, lucie.ciencialova, ludek.cienciala }@fpf.slu.cz Summary. In this paper, we investigate a possibility of Grey wolf optimization algorithm simulation by 2D P colonies. We introduce a new kind of 2D P colony equipped with a blackboard. It is used by agents to store information that is reachable by all the agents from every place in the environment. Key words: 2D P colonies, blackboard, Grey wolf optimization algorithm. 1 Introduction 2D P colonies are kind of P colonies, very simple membrane systems inspired by colonies of formal grammars. The interested reader is referred to [8] for detailed information on membrane systems (P systems) and to [4] and [3] for more information to grammar systems theory. For more details on P colonies consult the survey [2]. 2D P colony consists of a finite number of agents - finite collections of objects in a cell - and their joint shared environment. The environment of 2D P colony is represented by a 2D grid of square cells. In each cell, there is a multiset of objects. The agents have programs consisting of rules. These rules are of three types: they may change the objects of the agents and they can be used for interacting with the joint shared environment of the agents and movement rule. The direction of the movement of the agent is determined by the contents of cells surrounding the cell in which the agent is placed. The program can contain at most one motion rule. To achieve the greatest simplicity in agent behaviour, one other condition was set. If the agent moves, it cannot communicate with the environment. So if the program contains a motion rule, then the other rule is an evolution rule. The number of objects inside each agent is set by definition and it is usually a very small number: 1, 2 or 3. When the agent is moving around the 2D environment it has no information about the states and placements of the other agents. For remote information ex- 110 Daniel Valenta, Lucie Ciencialov´a, and Ludˇek Cienciala change, we add the agents the possibility to store and read the information from a blackboard. It is a table with an unchangeable structure given by definition. Agents can change values inside cells but not captions and the number of rows or columns. Grey wolf optimization algorithm (GWO) is a meta-heuristic optimization technology. Its principle is to imitate the behaviour of grey wolves in nature to hunt cooperatively. Four types of grey wolves such as alpha, beta, delta, and omega are used for simulating the leadership hierarchy. In addition, the three main steps of hunting, searching for prey, encircling prey, and attacking prey, are implemented. The algorithm was introduced by Mirjalili et al. in 2014 in [9]. 2 Grey wolf optimization algorithm This section is to explain the way the GWO works. Grey wolf optimization algorithm is inspired by social dynamics found in packs of grey wolves and by their ability to dynamically create hierarchies in which every member has a clearly defined role. We distinguish the following wolves: •Alpha male and female make up the dominant pair. The pack follows their lead during hunts, while locating a place to sleep, and so on. The most important attributes are their organisational abilities and discipline. •Beta wolves support and respect the Alpha pair during its decisions. •Delta wolves are subservient to Alpha and Beta wolves, follow their orders, and control Omega wolves. There are three types of Delta wolves: scouts – they observe the surrounding area and warn the pack, sentinels – they protect the pack when endangered and caretakers – they provide aid to old and sick wolves. •Omega wolves help to filter the pack’s aggression and frustrations by serving as scapegoats. In GWO, the agents (wolves) primary goal in its environment is to find and hunt down prey, which in our case equals finding the optimal solution to the given problem. The environment is represented by a mathematical fitness function characterising the specific problem. A value found at the current position of the wolf refers to the highest-quality prey located. The wolf with the best value is ranked as Alpha, the second as Beta, third as Delta, and all the other as Omega. The hunting technique of a wolf pack can be described in 5 steps: •Search for prey (point A in Fig. 2.) – wolves are attempting to find the most valuable prey with respect to the effort required to successfully hunt it. •Exploitation of prey (point B in Fig. 2.) – wolves are attempting to draw attention to themselves and to separate the prey from its herd. •Encircling prey (point C in Fig. 2.) – the attempt to push the prey into a situation it cannot escape from. •The prey is surrounded (point D in Fig. 2.) – it can no longer escape. Modelling of Grey Wolf Optimization Algorithm Using 2D P Colonies 111 Fig. 1. wolf pack hierarchy •Attack (point E in Fig. 2.) – wolves attack the prey’s weak spots (belly, legs, snout) until it succumbs to fatigue. Afterwards, they bring it down and crush its windpipe. Fig. 2. Hunting technique of grey wolves in [6] The algorithm is inspired by this process and smoothly transitions between scouting and hunting phases. In the scouting phase, the pack extensively scouts its environment through many random movements so that the algorithm does not 118 Daniel Valenta, Lucie Ciencialov´a, and Ludˇek Cienciala 5 Proposed model of 2D P colony with the blackboard As for the proposed definition of 2D P colony model with the blackboard, it is adapted to the suggestions from the previous chapter so that it allows simulation of the Grey wolf algorithm. 5.1 Definition Pgw = (A, e, env, B1, B2, . . . , Bn, X, f), where: •A={R}S{e, m, f}, •e∈Ais the basic environmental object, •env is a pair (m×n, f (x)), where m×n, m, n ∈N, •B1, B2, . . . , Bnare the agents, Bi= (Oi, Pi,[rx, ry]), where: –Oi= 2, –P1=P2=... =Pn,Pirules are defined below, –rx, ryare the initial coordinates, •Xis the blackboard defined as structure in Fig. 6., •fis the final object, f∈A. Fig. 6. Blackboard structure The initial agents’ configuration is: (O1[e], O2[e], env[i]), where i∈N. Programs Piassociated with i-th agent are: 1. (e1, e2, x) : e1, e2↔x;x∈R 2. (x, y, e); x, y ∈R: a) y←Get(BB[Alpha]) and Compare(x, y): i. x>y: I’m new Aplha, Update(BB[Alpha]); ii. x<y:y←Get(BB[Beta]) and Compare(x, y): A. x>y: I’m new Beta, Update(BB[Beta]); B. x<y:y←Get(BB[Delta]) and Compare(x, y): •x>y: I’m new Delta, Update(BB[Delta]); •x<y: I’m Omega: y↔e;e→m;m↔y; 3. (x, y, m); x, y ∈R: a) P ingBB[i] and y←Get(BB[i]); Modelling of Grey Wolf Optimization Algorithm Using 2D P Colonies 119 b) P ingBB[i] + mv1; mv1=(⇐,⇒,⇑,⇓) and y←Get(BB[i]); c) Compare(x, y); i. x>y:Do(mv1); ii. x<y: A. P ingBB[i] + mv2; mv2=(⇐,⇒,⇑,⇓)−mv1; mv16=mv2 B. y←Get(BB[i]) and Compare(x, y); •x>y:Do(mv2); •x<y: ... (try it with mv3 and mv4) – Can’t move: y↔m;m→f;f↔m; 4. (x, y, f); x, y ∈R: Stop the agent. } Pirules definition use the following symbols: • ← means Get from the blackboard, • → means Rewrite agent’s object, • ↔ means Change agent’s object with environment object, •”⇐” = LEF T , ” ⇒” = RIGHT , ” ⇑” = UP , ” ⇓” = DOW N At this point it is important to focus on the use of the blackboard by the agents. Agents can use blackboard functions: •Get(BB[i]); i= agent’s index - agent igets its distance from the prey (it is calculated by the blackboard), •Update(BB[x]) ; x=Alpha, Beta, Delta - agent update Balpha,Bbeta, or Bdelta field value, •P ing[BB[i]] ; iis the agent’s index - agent can ping the blackboard from some position, its distance from the prey is recalculated. Fig. 7. Blackboard in use The agent concludes it is Alpha and it rewrites the corresponding blackboard field in Fig. 7. on the left side. On the right side of Fig. 7., the agent concludes it is Omega and it will try to move with blackboard’s assistance. 120 Daniel Valenta, Lucie Ciencialov´a, and Ludˇek Cienciala Finally, the following derivation can be created. Fig. 8., a sequence of derivation steps is depicted. The first step (iteration) (point 1 in Fig. 8.) starting with two agents randomly initialized into the environment. They are in the initial configuration - two objects einside the agent. In the second iteration (point 2 in Fig. 8.), agents exchange their objects for objects placed in the environment (computed by fitness function). In next iterations (point 3 in Fig. 8.), agents get Alpha value from the blackboard and try to compare it to their own value. If Alpha value is empty, the first agent to try to compare its value will become the Alpha and update the blackboard. If more than one agent tries to write value into the blackboard in the same position the winner is non-deterministically chosen. The same process is used for declaring Beta and Delta agents (point 4 in Fig. 8.). If the agent’s fitness value is lower than Delta, this agent becomes Omega. At this point (point 5 in Fig. 8.) this agent rewrites the environmental object to m. Afterwards, it will try to move (point 6 in Fig. 8.). Before moving, however, it will compare the distances. The algorithm iterates until no more movement which would improve the fitness value is possible. 6 Conclusion In this paper we introduce extended model of 2D P colonies that can simulate solving optimization problem by Grey wolf optimization algorithm. The model will be improved in the near future. It is assumed that the function Compare() can be replaced by special equivalent rules, like (x > y, e) : action. It is also assumed that the other functions, such as Do(mv1), can be replaced by the rules in a form closer to the common rules of P systems. When it comes to testing the model and comparing it with the original version of GWO, the observation of the behaviour of the modified model is the aim of our further work. Potentially, the modified model could be faster or more efficient (in its approach towards the divergence between scouting for prey and hunting) compared to the original algorithm. Acknowledgments. The work was supported by The Ministry of Education, Youth and Sports from the National Programme of Sustainability (NPU II) project IT4Innovations excellence in science - LQ1602 and by the Silesian University in Opava under the Student Funding Scheme, project SGS/11/2019. References 1. Cienciala, L., Ciencialov´a, L., Perdek, M.: 2D P colonies. In: Csuhaj-Varj´u E., Gheorghe M., Rozenberg G., Salomaa A., Vaszil Gy. (eds) Membrane Computing. CMC Modelling of Grey Wolf Optimization Algorithm Using 2D P Colonies 121 2012. Lecture Notes in Computer Science, vol 7762. Springer, Berlin, Heidelberg, pp. 161–172 (2012) 2. Ciencialov´a, L., Csuhaj-Varj´u, E., Cienciala, L., and Sos´ık, P.: P colonies. J Membr Comput 1, 178—197 (2019) 3. Csuhaj-Varj´u, E., Kelemen, J., P˘aun, Gh., Dassow, J.(eds.): Grammar Systems: A Grammatical Approach to Distribution and Cooperation. Gordon and Breach Science Publishers, Inc., Newark, NJ, USA (1994) 4. Kelemen, J., Kelemenov´a, A.: A Grammar-Theoretic Treatment of Multiagent Systems. Cybern. Syst. 23(6), 621–633 (1992) 5. Kelemen, J., Kelemenov´a, A., P˘aun, Gh.: Preview of P colonies: A biochemically inspired computing model. In: Workshop and Tutorial Proceedings. Ninth International Conference on the Simulation and Synthesis of Living Systems (Alife IX). pp. 82–86. Boston, Massachusetts, USA (September 12-15 2004) 6. Muro, C., Escobedo, R., Spector, L., Coppinger, R.P.: Wolf-pack (Canis lupus) hunting strategies emerge from simple rules in computational simulations, Behavioural Processes 88(3), 192–197 (2011) 7. P˘aun, Gh.: Computing with membranes. J. Comput. Syst. Sci. 61(1), 108–143 (2000) 8. P˘aun, Gh., Rozenberg, G., Salomaa, A.(eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA (2010) 9. Mirjalilia, S., Mirjalilib, S.M., Lewisa, A.: Grey Wolf Optimizer. Advances in Engineering Software 69, 46—61(2014) 122 Daniel Valenta, Lucie Ciencialov´a, and Ludˇek Cienciala Fig. 8. Example of derivation Author Index Alhazov, Artiom, 1, 9, 21, 33 Ceterchi, Rodica, 49 Cienciala, Ludˇek, 63, 109 Ciencialov´a, Lucie, 63, 109 Csuhaj-Varj´u, Erzs´ebet, 63 Doncel-Ram´ırez, Andr´es, 79 Freund, Rudolf, 21, 33 Ivanov, Sergiu, 21, 33 Leporati, Alberto, 9 Manzoni, Luca, 9 Mart´ınez-del-Amor, Miguel ´ A, 79 Mauri, Giancarlo, 9 Orellana-Mart´ın, David, 49, 79, 91 P˘aun, Gheorghe, 101 Peng, Hong, 107 P´erez-Hurtado, Ignacio, 79 P´erez-Jim´enez, Mario J., 91 Valencia-Cabrera, Luis, 91 Valenta, Daniel, 109 Zandron, Claudio, 9 Zhang, Gexiang, 49