Communicating P Systems: Bio-inspired Computational Models for Complex Systems Erzsébet Csuhaj-Varjú Department of Algorithms and Their Applications, Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary csuhaj@inf.elte.hu Abstract: The theory of P systems or membrane systems, A computation is a sequence of configurations where a vivid scientific area in bio-inspired computing, deals the subsequent elements are obtained by transitions and with computational models inspired by architecture and the sequence starts with a so-called initial configuration. functioning of living cells and tissues, and neural systems. The result of the computation is usually defined by the This paper contains ideas on why and how purely commu- number of objects found in the so-called output region nicating P systems (important variants of P systems) can when the operation of the P system halts (no rule in any be interpreted as complex natural systems. We give a sum- of the regions can be performed). Instead of sets of num- mary of the most relevant results concerning these P sys- bers, sets of vectors of multiplicities of objects can also be tems and provide their interpretation in terms of complex considered as result. systems. We propose open problems and new directions P systems have intensively been studied during the for future research. years; for concepts, results, and a detailed overview of the area consult [18]. Since one of the main goals of introducing the notion of 1 Introduction a P system was to define a bio-inspired distributed com- puting device that is as powerful as Turing machines and P systems or membrane systems are distributed parallel combines properties of natural systems and classical mod- computing devices, inspired by architecture and function- els of (distributed) computation, the investigations in the ing of living cells. The original concept of a P system was field have mainly focused on computability and complex- introduced by Gheorghe Păun in 1998, for details see the ity questions. Recently, other areas of the theory of com- seminal paper [17]. Later the concept has been extended to putation, algorithms, simulations, applications in com- model living tissues and neural systems. Recently, mem- puter science have enhanced the research scope, only men- brane computing and its applications are a vivid, well- tioning a few. Since P systems exhibit properties of both established scientific area in natural computing and related qualitative and quantitative models, features, approaches fields of computer science. and aspects of this scientific area can be compared to that The basic model, the cell-like system consists of a hier- of various disciplines. archically embedded structure of membranes where each Studying how P systems can be used for modeling nat- membrane encloses a region which contains objects and ural, complex systems is a reasonable research direction may also contain other membranes (regions). The regions from this point of view. Some initial ideas on connections are associated with rule sets. These rules describe the evo- between natural complex systems and P automata (partic- lution and communication of the objects present in the re- ular variants of P systems) can be found in [4]. In the gions. P systems can also be considered as distributed par- following we discuss the relation between purely commu- allel multiset rewriting systems, since the rules describe nicating P systems (important variants of P systems) and the evolution and/or communication of multisets of ob- complex systems, with the approach used in [4] and con- jects in the actions. The P system operates with changing tinue developing the ideas presented in that paper. its configurations, in other words, with transitions from We first provide a brief description of interpretation of one configuration to some other one. A configuration of components and properties of cell-like P systems in terms a P system is the underlying graph structure of its regions of complex systems. Then we present such a compari- and the multisets of objects in the regions ( in other words, son in case of symport/antiport P systems and generalized compartments, nodes of the graph). The architecture of communicating P systems, both models are purely com- a cell-like P systems, called also a transition P system or municating variants of membrane systems. We close the symbol-object P system, has a tree as underlying graph, paper with some conclusions. has a rooted tree architecture. In case of tissue P sys- tems, and P systems modeling neural systems the under- lying graph is an arbitrary graph. 2 Complex Systems and P Systems Copyright c 2020 for this paper by its authors. Use permitted un- der Creative Commons License Attribution 4.0 International (CC BY Complex systems theory is an important scientific area 4.0). studying how parts of a system give rise to the collective behaviors of the system, and how the system interacts with be represented by any string x ∈ V ∗ where |x|a = M(a) for its environment. One of the main questions in the area is all a ∈ V (clearly, for a given string x, any permutation of whether or not the system as a whole is more powerful x represents the same multiset). than the sum of the power of their individual components. Examples for complex systems are, for example, social systems, social networks formed out of people, molecules 3 Symport/antiport P Systems formed out of bio-chemical ingredients, systems of agents, only to mention a few. Thus, the study of complex sys- In the case of transition P systems (the basic, cell-like tems is an interdisciplinary scientific field which focuses model), the multisets of objects are able to change (to on questions about wholes, parts, and relationships. For be rewritten) and to move across the membranes, i.e., the detailed information the reader is referred to [2], [15]. agents can evolve and can be communicated. In the fol- Examining cell-like P systems, we can conclude that the lowing we will discuss purely communicating P systems, above properties and features of complex systems are char- where objects can only be transported between neighbor- acteristic of P systems as well. Objects of a P system can ing compartments (including the environment), i.e., only be considered as elementary agents, elementary ingredi- communication of agent communities can be performed. ents of the complex system; multisets of objects form com- P systems having rules that only allow to move multisets munities of agents or collections of ingredients. Regions of objects from one compartment to one of its neighbors (or compartments) of the P system correspond to com- or simultaneously in opposite directions across the mem- ponents of the complex system, however not elementary brane, are called symport P systems or antiport P systems, components. The rules associated to the regions represent respectively; we use term symport/antiport P systems for interactions between communities of agents, they can be these two types of P systems. These notions have biologi- classified according to their forms and application mode. cal motivation and were introduced in [16]. The rules describe local activities, since they affect either Formally, a P system with symport and/or antiport rules the region in which they are executed or the neighboring (a symport/antiport P system, for short) is a construct regions. The neighboring regions of the P system represent Π = (O, T, E, µ, (w1 , R1 ), . . . , (wn , Rn , ), i0 ), where n ≥ 1, components of the complex system being in close connec- O is the finite alphabet of objects; T ⊆ O is the alphabet tion (neighboring components), and the environment itself of terminal objects; E ⊆ O is the set of objects in the en- can also be considered as a special, distinguished compo- vironment which appear in infinitely countable number of nent. The P system operates with applying its rules in the copies; µ is a membrane structure of n membranes, where same way as the complex system operates with interac- 1 indicates the skin membrane; wi ∈ V ∗ , 1 ≤ i ≤ n, is the tions between its components and its environment. The initial contents (finite multiset) of region i; Ri is a finite set behavior of a P system can be described by its configu- of rules associated to membrane i, 1 ≤ i ≤ n. The rules are ration (state) sequences or the result of a halting configu- of one of the forms (u, out; v, in) with u 6= λ , v 6= λ (an- ration sequence which starts from an initial configuration. tiport rule), (u, in), (u, out) with u 6= λ ( symport rules,) Analogous description can be used in case of complex sys- where u, v ∈ O∗ ; i0 ∈ {1, . . . , n} is the label of an elemen- tems as well. This approach provides the option to iden- tary membrane, called the output membrane. tify behavioral patterns and related properties as well. By The skin membrane separates the P system from the en- behavioral complexity we mean the complexity of the de- vironment; its region is in the root of the tree representing scription. For example, a family of P systems computing the architecture, the structure of the system. the recursively enumerable family of numbers is a family An antiport rule, (u, out; v, in) ∈ Ri , 1 ≤ i ≤ n, exchanges of complex systems that exhibits maximal complexity. multiset of objects u in region i with multiset v from the Various variants of P systems are as powerful as Tur- parent region of i. The symport rule (u, out) moves multi- ing machines, thus provide maximal computational power, set u out of region i, to its parent region, and symport rule and in terms of complex systems exhibit behavior of max- (u, in) imports u from the parent region into region i. If imal complexity. An important problem area is whether the rules are associated with the skin membrane, then the or not restricted P systems are able to exhibit such com- parent region is the environment. In the case of symport plex behavior. Furthermore, how we can interpret them in rules, if the parent region of i is the environment, then the terms of complex systems. In the following, we deal with imported multiset must contain at least one symbol not in these questions. E (otherwise an infinite number of objects would enter in Throughout the paper we assume that the reader is fa- the system). Multisets wi , 1 ≤ i ≤ n, and the membrane miliar with the theory of computation, thus we recall only structure µ represent the initial configuration of Π. At the a very few notations and notions. An alphabet V is a finite beginning, the environment does not contain any element nonempty set; the set of all strings over V is denoted by of O \ E. V ∗ , and λ denotes the empty word. A finite multiset over Symport/antiport rules can also be associated with pro- an alphabet V is a mapping M : V → N where N is the no- moters and/or inhibitors. In this case the objects are al- tation for the set of non-negative integers; M(a) is said to lowed to be transported between the regions, if the cor- be the multiplicity of a in M. A finite multiset M can also responding regions have (do not have) the promoter (in- hibitor) multiset included in their current multiset of ob- Moreover, their size parameters are bounded by constants jects. [6]. Universal antiport P systems correspond to certain Similarly to other types of P systems, symport/antiport "core" complex systems. P systems compute by performing transitions between Recall that the result of the computation of symport/an- subsequent configurations. The configurations consists of tiport P systems is the number of (terminal) objects or the multisets of objects that belong to the regions and the the set of vectors of (terminal) objects in the output re- multiset of the non-environmental objects (not elements of gion in a halting configuration. However, the computation E) which appear in the environment. Symport/antiport P can also be described by the sequence of multisets which systems usually use the non-deterministic maximally par- enter the P system during its functioning. This observa- allel working mode, but other derivation modes have also tion inspired to develop the concept of a P automaton [7], been considered (for more details, see [18, 12]). A se- a variant of accepting purely communicating P systems. quence of transitions starting with the initial configuration In this case, the input sequences of multisets imported by is a computation. the symport/antiport P system from the environment are The result of the computation in Π is the number of ob- mapped onto words over a finite alphabet, thus, form a jects from T that can be found in region i0 when the sys- language. The mapping is “easily” computable, usually tem halts. If no terminal alphabet is distinguished, then the computable in linear space. A similar notion, called an number of all objects in i0 at the end of a halting compu- analysing P system, [13] uses another mapping to define tation is the result of the computation. words of the language, the mapping that orders to every Instead of sets of numbers, sets of vectors of multiplic- multiset the set of words which are permutations of all el- ities of elements of T can also be considered as results. ements of the multiset. This mapping is denoted by f perm . Symport/antiport P systems can also be not only generat- The concept of a P automaton combines features of a P ing, but accepting devices. In this case, the input is the system and that of variants of classical automata. Sev- initial contents of a distinguished region. The symport/an- eral intersting results have been obtained on this model. tiport P system accepts the input if starting with this initial For example, P automata working in the non-deterministic configuration it enters a halting configuration by a compu- maximally parallel manner and with mapping computable tation. in linear space describe the class of context-sensitive lan- It can be observed that symport/antiport P systems can guages, while using mapping f perm , it defines a class of be considered as models for complex systems. The objects languages of sublogarithmic space complexity. For more in the membrane architecture represent very simple, ele- information the reader is referred to [18, 5]. mentary components of the system, the agents, collections P automata are models of complex natural systems (a of which interact with each other and with the environ- detailed discussion on the topic can be found in [4]). To ment of the system. The interactions, defined by the sym- prove that the statement holds, we recall some observa- port/antiport rules, are local interactions. Locality arises tions from [4]). from the fact that both symport and antiport rules involve An important property of complex systems is that the only neighboring regions (we consider the environment as interactions between the agents and the environment may the parent region of the skin region). Antiport P systems imply changes in the system itself. This is exactly the case behave in non-linear manner, since they behave in differ- for P automata, since the multisets of objects entering the ent ways to the same input multisets from the environment system from the environment can significantly change the depending on their current state. coming configuration sequence. The P automaton as com- Symport/antiport P systems are computationally com- plex system is an open system, since (multisets) of agents, plete computing devices [16]. Furthermore, for any regis- i.e., (multisets of) objects can join and leave the system ter machine, a P system of this type with only one region via symport/antiport rules. The standard P automaton is (one membrane) can be constructed such that it simulates given with a static membrane structure, that is, its archi- the register machine. Extensive investigations proved that tecture does not change during the functioning of the sys- symport/antiport P systems with small size parameters are tem, which is a rather restrictive condition. Examples for P as powerful as register machines, i.e., are computationally automata with dynamically changing membrane structure complete. These parameters are, for example, the number are the P automata with marked membranes [8]) (inspired of regions, the number of rules in the system, the number by biology) and the active P automata [3] (motivated by of objects in the multisets of the rules (for more details on natural language processing), however in these cases the these results, see [18]). underlying P systems is not a symport/antiport P system. Notice that the fact that symport/antiport P systems are P automata can also be considered as tools for describ- computationally complete prove that these systems as for- ing languages over infinite alphabets without any exten- mal models of complex systems demonstrate emergent be- sion or additional component added to the construct, since haviour since the power of the system as a whole signif- in the case of maximally parallel rule application the num- icantly exceeds the power of a single component without ber of objects entering the skin region not necessarily can any interaction. Furthermore, like in case of Turing ma- be bounded by a constant. This means that in this case chines, universal antiport P systems can be constructed. the agent population can increase fast and the number of simultaneous interactions with the environment cannot be only in a finite number of copies. The GCPS and the en- bounded by any constant. vironment interact by using the rules given above, with It would be worth studying P automata with adding the restriction that at every computation step only a finite the features of membrane creation, dissolution, division number of objects are communicated to each cell by the [18], P automata with dynamically varying structure. The environment. As usual in P systems’ theory, the rules are obtained new variants can be used for modeling self- applied in a maximally parallel manner. This implies a configurating systems and systems re-configurating their- possible change in the current state of the GCPS (the mul- selves under control coming from outside, since both the tisets representing the contents of the cells). A computa- objects inside the regions and the objects entering the sys- tion in a GCPS is a sequence of states directly following tem from the environment can launch a re-configuration in each other that starts from the initial state and ends in a the membrane structure. halting state. The result of the computation is the number of objects found in a distinguished cell, the output cell. It can be seen that GCPSs are formal models of com- 4 Generalized Communicating P Systems plex systems as well: the objects correspond the elemen- tary components, agents and the system operates with the As we discussed in the previous section, purely commu- interactions of agents. However, in this case the nodes are nicating P systems like symport/antiport P systems are of not explicitly given, instead they are defined by the interac- particular interest in membrane computing, since several tion rules between the agents. In this way, the architecture variants of P systems with only communication rules are of the system emerges in the course of functioning. computationally complete, thus these restricted systems To apply an interaction rule only two objects and at most are able to obtain maximally complex behavior (with re- four locations (nodes) are involved, thus it is worth study- spect to descriptions by computable sets of numbers, sets ing the form of interaction rules. of vectors of natural numbers, and languages). An intrigu- We recall the possible restrictions on the interaction ing question is what can we say about the type and form rules (modulo symmetry). The following cases are distin- of interactions between the agents in these systems, how guished, and then the systems is called GCPSs with mini- much extent the interactions can be simplified. mal interaction (for details see [10]. The reader may easily Generalized communicating P systems give an answer observe that these rules represent minimal interaction pat- to this question. We note that the concept was originally terns. introduced with the aim of providing a common general- ization of various purely communicating models [19]. 1. i = j = k 6= l: the conditional-uniport-out rule (the A generalized communicating P system (a GCPS for uout rule) sends b to cell l provided that a and b are short), is a tissue-like P system where each node repre- in cell i; sents a cell and each edge is represented by a rule (an in- teraction). Each node contains a multiset of objects that 2. i = k = l 6= j: the conditional-uniport-in rule (the uin can be communicated, i.e., it may move between the cells rule) brings b to cell i provided that a is in that cell; according to interaction (communication) rules. 3. i = j, k = l, i 6= k : the symport2 rule (the sym2 rule); The form of an interaction rule is (a, i)(b, j) → (a, k)(b, l) where a and b are objects 4. i = l, j = k, i 6= j : the antiport1 rule (the anti1 rule) and i, j, k, l are labels identifying the input and the output , i.e., a and b are exchanged in cells i and k; cells. Such a rule means that an object a from cell i and an object b from cell j move synchronously (in one step) 5. i = k and i 6= j, i 6= l, j 6= l: the presence-move rule to cell k and cell l, respectively. These interactions are (the presence rule) moves the object b from cell j to particularly simple, since there are only two objects (two l, provided that there is an object a in cell i and i, j, l agents) involved in them. are pairwise different cells; Formally, a generalized communicating P system (a GCPS) of degree n, where n ≥ 1, is an (n + 4)-tuple 6. i = j, i 6= k, i 6= l, k 6= l : the split rule sends a and b Π = (O, E, w1 , . . . , wn , R, h) where O is an alphabet, called from cell i to cells k and l, respectively; the set of objects of Π; E ⊆ O; called the set of environ- 7. k = l, i 6= j, k 6= i, k 6= j : the join rule brings a and b mental objects of Π; wi ∈ O∗ , 1 ≤ i ≤ n, is the multiset together to cell k; of objects initially associated to cell i; R is a finite set of interaction rules or communication rules of the form 8. l = i, i 6= j, i 6= k and j 6= k : the chain rule moves a (a, i)(b, j) → (a, k)(b, l), where a, b ∈ O, 0 ≤ i, j, k, l ≤ n, from cell i to cell k while b is moved from cell j to and if i = 0 and j = 0, then {a, b} ∩ (O \ E) 6= 0; / i.e., a ∈ /E cell i, i.e., to the cell where a located previously; and/or b ∈ / E; and h ∈ {1, . . . , n} is the output cell. The generalized communicating P system is embedded 9. i, j, k, l are pairwise different numbers: the parallel- in an environment, called cell 0, which may have certain shift rule (the shi f t rule) moves a and b from two objects in an infinite number of copies and certain objects different cells to another two different cells. During the years, GCPSs have been studied in detail. for P systems with dynamically changing underlying ar- The investigations have mainly been focused on their com- chitecture, with division and membrane creation. The re- putational power and their relation to other models like lation between P systems with infinite runs and complex Petri nets. systems would also be a challenging topic for future re- It has been shown that GCPSs in general, and even with search. minimal interaction are able to generate any recursively enumerable set of numbers. Furthermore, to obtain com- putational completeness a relatively small number of cells 6 Acknowledgement and a simple underlying hypergraph architecture is suffi- cient [10, 14, 11]. Thus, for example GCPSs with three This work was supported by NKFIH (National Research, cells and with only join, or only split, or only chain rules Development, and Innovation Office, Hungary) Grant no. are computationally complete computing devices [11]. It K 120558. is also shown that the maximal expressive power can also be obtained with GCPSs where the alphabet of objects is a singleton [9]. Moreover, computational completeness with References small number of cells can also be obtained if the objects of the environment are provided with a rewriting system [1] Balaskó, Á., Csuhaj-Varjú, E., Vaszil, G.: Dynamically generating multisets of objects step by step [1]. Changing Environment for Generalized Communicating P If we consider GCPSs as formal models of complex sys- Systems. In: Rozenberg, G. et. al (eds.) Membrane Com- puting - 16th International Conference, CMC 2015, Valen- tems, we may derive interesting consequences. Namely, cia, Spain, August 17-21, 2015, Revised Selected Papers. the maximal complexity of the collective behavior of the LNCS 9504, Springer, 2015, pp. 92–105 system (represented by the generated sets of numbers) can [2] Boccara, N.: Modeling Complex Systems. Graduate Texts be obtained with very simple, uniform interaction patterns, in Physics, Springer (2010) with only one type of elementary actions. Furthermore, at [3] Bel-Enguix, G., Gramatovici, R.: Parikh mapping and any moment of operation the number of groups, collec- iteration. In: Ciobanu, G. et al (eds.): Applications of tions of agents is a very small number. It is also proved Membrane Computing. Natural Computing Series 2235, that in case of certain type of the interaction rules there Springer, Berlin, 2006, 389—410 is no need to distinguish different types of agents in order [4] Csuhaj-Varjú, E.: P Automata: Automata-like constructs to obtain the collective behavior with maximal complexity. modeling complex natural systems. Bensch, S. et al (eds.): Furthermore, these systems are able to tolerate the changes Fifth Workshop on Non-Classical Models for Automata in the environment not caused by actions of the agents. and Applications - NCMA 2013, Umea, Sweden, August Although several questions and problems concerning 13 - August 14, 2013, Proceedings. books@ocg.at 294, generalized communicating P systems have been investi- Österreichische Computer Gesellschaft 2013, ISBN 978-3- gated, some ideas would be worth studying. For exam- 85403-294-6, 2013, 13–30 ple, what can we say about GCPSs where the interaction [5] Csuhaj-Varjú, E.: P and DP Automata: Unconventional rules change in time. Namely, the new locations of the versus Classical Automata. Int. J. Found. Comput. Sci. objects depend on the number of performed computation 24(7) (2013) 995–1008 steps. One other interesting aspect could be to introduce [6] Csuhaj-Varj,́ E., Margenstern, M., Vaszil, G., Verlan, S.: concepts from evolutionary computing in this area: those On small universal antiport P systems. Theor. Comput. Sci. interactions which are not used or rarely used change their 372(2-3) (2007) 152–164 form or are dismissed from the set of rules. It also would [7] Csuhaj-Varjú, E., Vaszil, G.: P Automata or Purely Com- be interesting to examine the concept of similarity in case municating Accepting P Systems. In: Păun G. et al (eds): Membrane Computing. WMC 2002. LNCS, vol 2597. of these systems, especially concerning behavior or the se- Springer, Berlin, Heidelberg, 2003, 219–233 quence of (multi)sets of performed interactions. [8] Csuhaj-Varjú, E., Vaszil, G.: (Mem)brane automata. Theor. Comput. Sci. 404 (1-2) (2008) 52–60. 5 Conclusion and Open Problems [9] Csuhaj-Varjú, E., Vaszil, G., Verlan, S.: On generalized communicating P systems with one symbol. In: Gheorghe, M. et al (eds.) 11th International Conference on Membrane P systems, even purely communicating variants, can be Computing, 2010, Jena, Germany, LNCS 6501, Springer, considered as formal models of natural complex systems, 2010, pp. 160–174. since they are dynamically changing systems which are [10] Csuhaj-Varjú, E., Verlan, S.: On generalized communicat- in communication (interaction) with their environments. ing P systems with minimal interaction rules. Theor. Com- To explore this relation, further investigations are needed put. Sci. 412 (2011) 124–135 to interpret such concepts as emergent phenomena, non- [11] Csuhaj-Varjú, E., Verlan, S.: Computationally Complete linearity, interaction complexity, behavioral complexity in Generalized Communicating P Systems with Three Cells. P systems theory, in case of different variants of P systems. In: Gheorghe, M. et al (eds.): Membrane Computing. CMC Especially interesting problems are to define these notions 2017. LNCS 10725. Springer, Cham., (2018), 118–128 [12] Freund, R.: How derivation modes and halting conditions may influence the computational power of P systems. J. Membr. Comput. 2 (1) (2020), 14–25. [13] Freund, R., Oswald, M.: A short note on analysing P sys- tems. Bull. EATCS 78 (2002) 231–236 [14] Krishna, S. N., Gheorghe, M., Ipate, F., Csuhaj-Varjú, E., Ceterchi, R.: Further results on generalised communicating P systems. Theor. Comput. Sci. 701 (2017) 146–160 [15] Northrop, R. B.: Introduction to Complexity and Complex Systems. CRC Press, Taylor and Francis Group, Roca Ba- ton (2010) [16] Păun, A., Păun, G.: The Power of Communication: P Sys- tems with Symport/Antiport. New Gener. Comput. 20(3) (2002) 295–306 [17] Păun, G.: Computing with Membranes. J. Comput. Syst. Sci. 61(1) (2000) 108–143 [18] Păun, G., Rozenberg, G., Salomaa, A. (eds.): The Ox- ford Handbook of Membrane Computing. Oxford Univer- sity Press (2010) [19] Verlan, S., Bernardini, F., Gheorghe, M., Margenstern, M.: Generalized communicating P systems. Theor. Com- put. Sci. 404(1-2) (2008) 170–184