Models of P Colonies Lucie Ciencialová1,*,† , Luděk Cienciala1,† 1 Institute of Computer Science, Faculty of Philosophy and Science in Opava, Silesian Univerity in Opava, Opava, Czech Republic Abstract This paper explores different models of P colonies, including restricted, homogeneous, and those with senders and consumers. P colonies, inspired by the behavior of simple unicellular organisms in a shared environment, are theoretical computational models where agents interact through finite programs within a common environment. The study examines transformations between these P colony types and their impact on new findings related to the computational completeness of P colonies under specific parameter constraints. Keywords membrane computing, P Colonies, agent-based model, nature-inspired computation model 1. Introduction modify the objects they possess and exchange some of their objects with those in the environment. These co- In this paper, we concentrate on various previously ordinated actions result in a configuration change, or published P colony models, specifically the restricted transition, within the P colony. A finite sequence of con- P colony, the homogeneous P colony, and P colonies with secutive configuration changes, starting from the initial senders and consumers. The original model of P colony configuration, constitutes a computation. The output of was introduced in [1] as a theoretical computing model this computation is determined by counting the number inspired by structure and behavior of simple one-cell of copies of a specific distinguished object, known as the organisms living in a shared environment. “final object”, present in the environment at the end of The P colony consists of basic units called agents, each the process. equipped with programs. The environment plays a cru- The environment serves a dual purpose: it acts as a cial role, storing the products of agent activities and en- communication channel for the agents and also functions abling agents to send “messages" to each other through as a storage medium for objects. Its critical role lies it. The agents operate based on objects. in synchronizing the collaborative efforts of the agents Each agent contains a finite multiset of objects, which throughout the entire computation process. are processed by a finite set of unique programs asso- The programs thus allow P colony agents to change ciated with each agent. The number of objects within both their own contents and the contents of the environ- each agent remains constant during the computation of ment. The programs consist basically of six distinct types the agent community, known as the "capacity" of the P of rules: rewriting, communication, checking, generating, colony. In this paper, we will focus on P colonies with a consuming and transporting rules. The first two types of capacity of 2, specifically on P colonies where each agent rules are used in restricted and homogeneous P colonies. contains exactly two objects. Communication and rewriting rules can be combined The agents share a common environment, represented to checking rules. In this paper, we do not consider the by another multiset of objects. Among these objects, a use of this combination of rules, which determine the specific type called the "environmental object" is assumed priority between two participating rules. P colonies with to exist in an infinitely countable number of copies. It senders and consumers uses insertion and deletion rules. is worth noting that some literature may also describe The structure of the paper is as follows: after an intro- cases where the environmental symbol appears in a very ductory section, we introduce the basic concepts of the large, but finite, number of copies. original P colony model, its restricted and homogeneous By utilizing their respective programs, the agents can versions and P colony with senders and consumers. In the third part, we will focus on transformations between ITAT 2024: Information Technologies – Applications and Theory, these types of P colonies. We will compare the results September 20–24, 2024, Čergovské Vrchy, Slovakia * Corresponding author. regarding the computational power of these types of P † These authors contributed equally. colonies in terms of the proposed transformations. " lucie.ciencialova@fpf.slu.cz (L. Ciencialová); ludek.cienciala@fpf.slu.cz (L. Cienciala)  0000-0002-0877-7063 (L. Ciencialová); 0000-0001-7116-9338 (L. Cienciala) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings 2. Preliminaries and Definitions • Σ is the alphabet of the colony, its elements are called objects, Throughout the paper we assume the reader to be famil- • 𝑒 is the basic (environmental) object of the colony, iar with the basics of the formal language theory and 𝑒 ∈ Σ, membrane computing [2, 3]. • 𝑓 is final object of the colony, 𝑓 ∈ Σ, For an alphabet Σ, the set of all words over Σ (includ- • 𝑣𝐸 is the initial content of the environment, 𝑣𝐸 ∈ ing the empty word, 𝜀), is denoted by Σ* . We denote (Σ − {𝑒})* , the length of a word 𝑤 ∈ Σ* by |𝑤| and the number • 𝐵𝑖 , 1 ≤ 𝑖 ≤ 𝑛, are the agents, every agent is the of occurrences of the symbol 𝑎 ∈ Σ in 𝑤 by |𝑤|𝑎 . structure 𝐵𝑖 = (𝑜𝑖 , 𝑃𝑖 ), where 𝑜𝑖 is a multiset over A multiset of objects 𝑀 is a pair 𝑀 = (𝑂, 𝑓 ), where Σ, it defines the initial state (content) of the agent 𝑂 is an arbitrary (not necessarily finite) set of objects and 𝐵𝑖 and |𝑜𝑖 | = 𝑐 and 𝑃𝑖 = {𝑝𝑖,1 , . . . , 𝑝𝑖,𝑘𝑖 } is the 𝑓 is a mapping 𝑓 : 𝑂 → 𝑁 ; 𝑓 assigns to each object in 𝑂 finite set of programs of three types: its multiplicity in 𝑀 . Any multiset of objects 𝑀 with the set of objects 𝑂 = {𝑥1 , . . . 𝑥𝑛 } can be represented as (1) generating program with generating rules a string 𝑤 over alphabet 𝑂 with |𝑤|𝑥𝑖 = 𝑓 (𝑥𝑖 ); 1 ≤ 𝑖 ≤ 𝑎 → 𝑏𝑐 and transporting rules (𝑑, 𝑜𝑢𝑡) - 𝑛. Obviously, all words obtained from 𝑤 by permuting the number of generating rules is the same the letters can also represent the same multiset 𝑀 , and as the number of transporting rules. 𝜀 represents the empty multiset. (2) consuming program with consuming rules 𝑎𝑏 → 𝑐 and transporting rules (𝑑, 𝑖𝑛) - the number of consuming rules is the same as 2.1. P Colonies the number of transporting rules. In the following we describe the concept of a P Colony. (3) rewriting/communication program can con- The original definition of P colony was introduced in tain three types of rules: [1]. In this paper, we will use an extended definition ◇ 𝑎 → 𝑏, called a rewriting rule, [4], which we have slightly modified by excluding the ◇ 𝑐 ↔ 𝑑, called a communication rule, possibility of an evolving environment. ◇ 𝑟1 /𝑟2 , called a checking rule; each of Rewriting rule 𝑎 → 𝑏 allows an agent to rewrite (evolve) 𝑟1 , 𝑟2 is a rewriting or a communi- one object 𝑎 placed inside the agent to object 𝑏. cation rule. Communication rule 𝑎 ↔ 𝑏 exchanges one object 𝑎 We first note that throughout the paper, we use term placed inside the agent for object 𝑏 from the en- “object 𝑎 is inside agent 𝐴” and term “𝑎 ∈ 𝑤, where 𝑤 is vironment. the state of agent 𝐴” as equivalent. The functioning of the P colony starts from its initial Checking rule 𝑟1 /𝑟2 , where each of 𝑟1 , 𝑟2 is a rewriting configuration (state). or a communication rule, sets a priority between The initial configuration of a P colony is an (𝑛 + 1)- these two rules. The agent try to apply the first tuple of multisets of objects present in the P colony at rule and if it cannot be performed, the agent exe- the beginning of the computation. It is given by the cutes the second rule. multisets 𝑜𝑖 for 1 ≤ 𝑖 ≤ 𝑛 and by multiset 𝑣𝐸 . For- mally, the configuration of the P colony Π is given by Generating rule 𝑎 → 𝑏𝑐 creates two objects 𝑏, 𝑐 from (𝑤1 , . . . , 𝑤𝑛 , 𝑤𝐸 ), where |𝑤𝑖 | = 𝑐, 1 ≤ 𝑖 ≤ 𝑛, 𝑤𝑖 one object 𝑎. represents all the objects present inside the 𝑖-th agent, Consuming rule 𝑎𝑏 → 𝑐 rewrites two objects 𝑎, 𝑏 to one and 𝑤𝐸 ∈ (Σ − {𝑒}) represents all the objects in the * object 𝑐. environment different from the object 𝑒. At each step of the computation (at each transition), Transporting rule of the form (𝑎, 𝑖𝑛) or (𝑎, 𝑜𝑢𝑡) is used the state of the environment and that of the agents change to transport one object from the environment into in the following manner: In the maximally parallel deriva- the agent, or from the agent to the environment, tion mode, each agent which can use any of its programs respectively. The rule is always associated with should use one (non-deterministically chosen), whereas a consuming/generating rule to keep a constant in the sequential derivation mode, one agent uses one number of objects inside the agent. of its programs at a time (non-deterministically chosen). If the number of applicable programs for one agent is Definition 1. A P colony with capacity 𝑐 ≥ 1 is the higher than one, then the agent non-deterministically structure chooses one of the programs. A sequence of transitions is called a computation. A Π = (Σ, 𝑒, 𝑓, 𝑣𝐸 , 𝐵1 , . . . , 𝐵𝑛 ), where computation is said to be halting, if a configuration is reached where no program can be applied any more. 3. Program Transformations With a halting computation, we associate a result which is given as the number of copies of the objects 𝑓 present Let Π = (𝐴, 𝑒, 𝑓, 𝑣𝐸 , 𝐵1 , . . . , 𝐵𝑛 ) be a P colony of ca- in the environment in the halting configuration. pacity 2 with 𝑛 agents. Because of the non-determinism in choosing the pro- For all transformations, we will assume a unique la- grams, starting from the initial configuration we obtain beling of programs such that each program has its own several computations, hence, with a P colony we can labeling within all agents of the P colony. 𝑛 associate a set of numbers, denoted by 𝑁 (Π), computed Let 𝑃 = ⋃︀ 𝑃𝑖 and 𝑅 be a set of all program labels by all possible halting computations of given P colony. 𝑖=1 In the original model (see [1]) the number of objects such that 𝑅 = {𝑟𝑖 | 1 ≤ 𝑖 ≤ |𝑃 |}. inside each agent is set to two. Since the application Now we will focus on transforming the different types of a program must involve all objects within the agent, of programs into one another. We will start with the the original P colony model requires that the number of conversion of restricted programs into homogeneous rules in a program equals the number of objects, which ones. is two. Moreover the initial configuration was defined as (𝑛 + 1)-tuple (𝑒𝑒, . . . , 𝑒𝑒, 𝜀) so the environment of the 3.1. Transformation from Restricted to P colony is at the beginning of the computation “empty”, Homogeneous Programs without an input information. A P colony is called restricted if each program consists If we need to transform restricted programs into homo- of one evolving rule and one communication rule. A P geneous ones, we must address the situation where ho- colony is called homogeneous if each program consists mogeneous programs change their entire content in each of one type of rules - rewriting or communication. The step—they either rewrite it or exchange it with the envi- third type of P colonies we will cover in this article are P ronment. During the simulation of executing a restricted colonies using generating and consuming programs. If program, there is a situation where, due to the rules of the agents have only generating programs in their program homogeneous program, it is necessary to pull a different set, we call them senders. If an agent has only consuming object into the agent than the original restricted program programs available, we call it a consumer. In this article, requires, and we do not have objects available that the we will not be so strict and we will also consider agents agent could have generated in the previous phase (such as that use both generating and consuming programs. 𝑟𝑖 , 𝑟𝑖′ , . . .). Even though the environment contains a large The number of agents in a given P colony is called number of environmental objects, we cannot use them the degree of Π; the maximal number of programs of an because these objects may be part of the agent’s restricted agent of Π is called the height of Π and the number of programs (for example, ⟨𝑎 → 𝑒, 𝑒 ↔ 𝑏⟩). Therefore, we the objects inside an agent is called the capacity of Π. will need to generate an appropriate number of objects The family of all sets of numbers 𝑁 (Π) computed as that are not part of the original P colony’s alphabet. Let above by P colonies of capacity at most 𝑐 ≥ 0, degree at this object be ℎ ∈ / Σ. The generation of the required most 𝑛 ≥ 0 and height at most ℎ ≥ 0, using checking number of ℎ objects can be handled by special agents programs, and working in the maximally parallel way that perform only one program—placing their content are denoted by NPCOL𝑝𝑎𝑟 𝐾(𝑐, 𝑛, ℎ). (2 objects ℎ) into the environment. Alternatively, the If one of the parameters 𝑛, ℎ is not bounded, then we re- required number of ℎ objects can simply be added to the place it with *. If only P colonies using programs without initial configuration of the environment. checking rules are considered, then we omit parameter ∀ programs 𝑟𝑖 of type < 𝑎 → 𝑏; 𝑐 ↔ 𝑑 > there are 𝐾. The family of all sets of numbers 𝑁 (Π) computed as programs in the subset 𝐶 of programs: above by restricted P colonies of capacity at most 𝑐 ≥ 0, 𝐶1. < 𝑎 → 𝑟𝑖 ; 𝑐 → 𝑟𝑖′ > degree at most 𝑛 ≥ 0 and height at most ℎ ≥ 0, not 𝐶2. < 𝑟𝑖 ↔ ℎ; 𝑟𝑖′ ↔ 𝑒 > using checking programs, and working in the maximally 𝐶3. < ℎ ↔ 𝑟𝑖 ; 𝑒 ↔ ℎ > parallel way are denoted by NPCOL𝑝𝑎𝑟 𝑅(𝑐, 𝑛, ℎ), if the 𝐶4. < 𝑟𝑖 → 𝑐; 𝑒 → ℎ > P colony is homogeneous the notation of corresponding 𝐶5. < 𝑐 ↔ 𝑟𝑖′ ; ℎ ↔ 𝑑 > family is NPCOL𝑝𝑎𝑟 𝐻(𝑐, 𝑛, ℎ). In the case of P colonies 𝐶6. < 𝑟𝑖′ → 𝑏; 𝑑 → 𝑑 > with generating and consuming programs we can use 𝐶7. < 𝑐 ↔ 𝑟𝑖′ ; ℎ ↔ ℎ > notation NPCOL𝑝𝑎𝑟 𝐺𝐶(𝑐, 𝑛, ℎ). 𝐶8. < 𝑟𝑖′ → 𝑟𝑖′ ; ℎ → ℎ > There are agents of type 𝐷 in the P colony: 𝐷1. < ℎ ↔ 𝑒; ℎ ↔ 𝑒 > Here, we have presented a variant that uses 𝑛 agents to generate 2𝑛 objects ℎ. agent agent 𝐷 env. prog. prog. programs might temporarily place some objects into the 1. 𝑎𝑐 ℎℎ 𝑥𝑑 𝐶1 𝐷1 environment that will be back inside these agents by the 2. 𝑟𝑖 𝑟𝑖′ 𝑒𝑒 𝑥𝑑ℎℎ 𝐶2 − end of the simulation. Consider a configuration that does 3. ℎ𝑒 ℎ𝑞 𝑥ℎ𝑑𝑟𝑖 𝑟𝑖′ 𝐶3 − not contain object 𝑑. During the simulation of a single 4. 𝑟𝑖 ℎ ℎ𝑞 𝑥𝑑𝑟𝑖′ ℎ 𝐶4 − computation step, one of the agents uses a program of 5. 𝑐ℎ ℎ𝑞 𝑥𝑑𝑟𝑖′ ℎ 𝐶5 − type E4 and temporarily places object 𝑑 into the envi- 6. 𝑟𝑖′ 𝑑 ℎ𝑞 𝑥𝑐ℎℎ 𝐶6 − ronment, intending to remove it in the next computation 7. 𝑏𝑑 ℎ𝑞 𝑥𝑐ℎℎ − − step using a rule of type E5. If, during the computation The program 𝑟𝑖 is simulated by performing six pro- phase when object 𝑑 is present in the environment, a grams in six computation steps. Last two programs are check for the presence of 𝑑 for a consuming program is used for entering and performing infinite loop. performed, then the programs of both agents would be applicable. 3.2. Transformation from Generating and agent env. prog. Consuming to Restricted Programs 1. 𝑎𝑐 𝑥ℎℎ𝑑 𝐹1 2. 𝑟𝑖 𝑑 𝑥ℎℎ𝑐 𝐹2 To transform a P colony with insertion and deletion pro- 3. 𝑟𝑖′ 𝑐 𝑥ℎℎ𝑟𝑖 𝐹3 grams into a P colony with restricted programs, we need 4. 𝑟𝑖 𝑏 𝑥ℎℎ𝑟𝑖′ 𝐹4 to use a similar tactic to add a certain number of auxiliary 5. 𝑟𝑖′ ℎ 𝑥ℎ𝑏 𝐹5 objects ℎ to the initial configuration of the P colony’s 6. 𝑑𝑏 𝑥ℎℎ − environment or introduce new agents that place such objects into the environment themselves. 3.3. Transformation from Restricted to Agents of type 𝐺 serve as generators of ℎ objects. 𝐺1. < ℎ → ℎ; ℎ ↔ 𝑒 > Generating and Consuming Programs 𝐺2. < 𝑒 → 𝑞; ℎ ↔ 𝑒 > Since executing a restricted program involves the agent ∀ programs 𝑟𝑖 of type < 𝑎 → 𝑏𝑑; (𝑐, 𝑜𝑢𝑡) > there are exchanging an object with another from the environ- programs in subset 𝐸 of programs of agents: ment, both generating and consuming programs must be 𝐸1. < 𝑎 → 𝑟𝑖 ; 𝑐 ↔ 𝑒 > executed during the simulation. In this paper, we allow 𝐸2. < 𝑒 → 𝑟𝑖′ ; 𝑟𝑖 ↔ ℎ > one agent to contain both types of these programs. 𝐸3. < 𝑟𝑖′ → 𝑏; ℎ ↔ 𝑟𝑖 > ∀ programs 𝑟𝑖 of type < 𝑎 → 𝑏; 𝑐 ↔ 𝑑 > there are 𝐸4. < 𝑟𝑖 → 𝑟𝑖′′ ; 𝑏 ↔ ℎ > following programs in the subset 𝐻 of programs of the 𝐸5. < 𝑟𝑖′′ → 𝑑; ℎ ↔ 𝑏 > corresponding agent: Using this program, the agent does not need an object 𝐻1. < 𝑎𝑐 → 𝑟𝑖 ; (𝑑, 𝑖𝑛) > from the environment; instead, it places an object into 𝐻2. < 𝑟𝑖 𝑑 → 𝑟𝑖′ ; (𝑒, 𝑖𝑛) > the environment. Two objects ℎ are required for the 𝐻3. < 𝑟𝑖′ → 𝑟𝑖′′ 𝑐; (𝑒, 𝑜𝑢𝑡) > simulation. 𝐻4. < 𝑟𝑖′′ → 𝑟𝑖′′′ 𝑏; (𝑐, 𝑜𝑢𝑡) > agent env. prog. 𝐻5. < 𝑟𝑖′′′ → 𝑟𝑖 𝑑; (𝑏, 𝑜𝑢𝑡) > 1. 𝑎𝑐 𝑥ℎℎ 𝐸1 𝐻6. < 𝑟𝑖 𝑑 → 𝑑; (𝑏, 𝑖𝑛) > 2. 𝑟𝑖 𝑒 𝑥ℎℎ𝑐 𝐸2 Objects 𝑟𝑖 , 𝑟𝑖′ , 𝑟𝑖′′ , 𝑟𝑖′′′ , and 𝑟𝑖 serve to mark the phase ′ 3. 𝑟𝑖 ℎ 𝑥𝑐ℎ𝑟𝑖 𝐸3 of the restricted program simulation, and they are used 4. 𝑟𝑖 𝑏 𝑥ℎℎ𝑐 𝐸4 to generate the necessary objects accordingly. 5. 𝑟𝑖′′ ℎ 𝑥ℎ𝑐𝑏 𝐸5 step agent H env. prog. 6. 𝑑𝑏 𝑥ℎℎ𝑐 − 1. 𝑎𝑐 𝑥𝑑 𝐻1 ∀ programs 𝑟𝑖 of type < 𝑎𝑐 → 𝑏; (𝑑, 𝑖𝑛) > there is 2. 𝑟𝑖 𝑑 𝑥 𝐻2 subset 𝐹 of programs of the agent: 3. 𝑟𝑖′ 𝑒 𝑥 𝐻3 𝐹 1. < 𝑎 → 𝑟𝑖 ; 𝑐 ↔ 𝑑 > 4. 𝑟𝑖′′ 𝑐 𝑥 𝐻4 ′ 𝐹 2. < 𝑑 → 𝑟𝑖 ; 𝑟𝑖 ↔ 𝑐 > 5. 𝑟𝑖′′′ 𝑏 𝑥𝑐 𝐻5 ′ 𝐹 3. < 𝑐 → 𝑏; 𝑟𝑖 ↔ 𝑟𝑖 > 6. 𝑟 𝑑 𝑥𝑏𝑐 𝐻6 𝑖 𝐹 4. < 𝑟𝑖 → ℎ; 𝑏 ↔ 𝑟𝑖′ > 7. 𝑑𝑏 𝑥𝑐 − 𝐹 5. < 𝑟𝑖′ → 𝑑; ℎ ↔ 𝑏 > To execute the consuming program, the presence of ob- ject 𝑑 in the environment is required. This condition also 3.4. Transformation from Homogeneous applies to the execution of the first restricted program in to Generating and Consuming the simulation of rule 𝑟𝑖 . If this check were to occur at a Programs later stage in the simulation, it could lead to an improper Homogeneous programs can be of two types: either both application of the program, as the simulation of other objects in the agent are rewritten into new objects (not necessarily different from the original ones), or both ob- In addition to ensuring that during the first step of sim- jects inside the agent are exchanged with two objects ulating program 𝑟𝑖 , the agent does not emit any objects that were originally in the environment. that could affect the applicability of other programs in the We begin the transformation by simulating a homoge- P colony, it is also necessary to match the length of the neous program in which the agent exchanges its entire program simulation of 𝑟𝑖 to the number of steps required content with the environment. Both objects inside the for a successful simulation of the above-mentioned type agent are moved to the environment, and two objects of homogeneous program. The reader can notice that oth- from the environment are moved to the agent. This sec- erwise, the simulation could be completed in two steps ond transfer imposes a strong applicability condition for by using two programs (𝐽1 and the modified 𝐽7). If the the rule, which cannot be checked by consuming pro- simulation of one type of homogeneous program took a grams in a single step. Therefore, we perform the check different number of steps than the simulation of the other in two consecutive steps. We must also adjust the sim- type, the simulation of steps of computation would start ulation of the second type of homogeneous program to to overlap, and the applicability of individual programs ensure that, during the first two steps of their applica- might not reflect the configuration of the original model. tion, the agent does not introduce any objects into the step agent env. prog. environment that might influence the applicability of 1. 𝑎𝑐 𝑥 𝐽1 the second program in the simulation. If another agent 2. 𝑟𝑖 𝑒 𝑥 𝐽2 adds an object (e.g., 𝑏) to the environment in the first 3. 𝑟𝑖1 𝑒 𝑥 𝐽3 step, which was not previously present, it can change the 4. 𝑟𝑖2 𝑒 𝑥 𝐽4 applicability of the program. 5. 𝑟𝑖3 𝑎 𝑥 𝐽5 ∀ programs 𝑟𝑖 of type < 𝑎 ↔ 𝑏; 𝑐 ↔ 𝑑 > there is a 6. 𝑟𝑖4 𝑒 𝑥 𝐽6 subset 𝐼 of set of programs of the agent: 7. 𝑟𝑖5 𝑒 𝑥 𝐽7 𝐼1. < 𝑎𝑐 → 𝑟𝑖 ; (𝑏, 𝑖𝑛) > 8. 𝑑𝑏 𝑥 − 𝐼2. < 𝑟𝑖 𝑏 → 𝑟𝑖1 ; (𝑑, 𝑖𝑛) > 𝐼3. < 𝑟𝑖1 𝑑 → 𝑟𝑖2 ; (𝑒, 𝑖𝑛) > 3.5. Transformation from Homogeneous 𝐼4. < 𝑟𝑖2 → 𝑟𝑖3 𝑎; (𝑒, 𝑜𝑢𝑡) > to Restricted Programs 𝐼5. < 𝑟𝑖3 → 𝑟𝑖4 𝑐; (𝑎, 𝑜𝑢𝑡) > 𝐼6. < 𝑟𝑖4 → 𝑟𝑖5 𝑒; (𝑐, 𝑜𝑢𝑡) > We will conclude the section on transformations with 𝐼7. < 𝑟𝑖5 → 𝑏𝑑; (𝑒, 𝑜𝑢𝑡) > the conversion of homogeneous programs into restricted 𝐼8. < 𝑟𝑖 𝑏 → 𝑙; (𝑒, 𝑖𝑛) > programs. 𝐼9. < 𝑙 → 𝑙𝑒; (𝑒, 𝑜𝑢𝑡) > To begin with, it should be noted that this transforma- Program 𝐼8 allows the computation to continue if the tion is not complete. In situations where the P colony is homogeneous program 𝑟𝑖 was selected for simulation in a halt configuration, but the agent configuration and but was not applicable in the original P colony due to the the environment’s content allow for the initiation of the absence of object 𝑑 in the environment. Program 𝐼9 is simulation of a homogeneous program with communica- included in the agent’s set of programs only once, and tion rules, it results in an infinite loop instead of halting its execution results in an infinite loop. the computation. We present the transformation here for step agent env. prog. the sake of completeness. 1. 𝑎𝑐 𝑥𝑏𝑑 𝐼1 ∀ programs 𝑟𝑖 of type < 𝑎 → 𝑏; 𝑐 → 𝑑 >: 2. 𝑟𝑖 𝑏 𝑥𝑑 𝐼2 1. < 𝑎 → 𝑟𝑖 ; 𝑐 ↔ 𝑒 > 3. 𝑟𝑖1 𝑑 𝑥 𝐼3 2. < 𝑟𝑖 → 𝑟𝑖′ ; 𝑒 ↔ 𝑐 > 4. 𝑟𝑖2 𝑒 𝑥 𝐼4 3. < 𝑐 → 𝑟𝑖′′ ; 𝑟𝑖′ ↔ 𝑒 > 5. 𝑟𝑖3 𝑎 𝑥 𝐼5 4. < 𝑟𝑖′′ → 𝑑; 𝑒 ↔ 𝑒 > 6. 𝑟𝑖4 𝑐 𝑥𝑎 𝐼6 5. < 𝑑 → 𝑑; 𝑒 ↔ 𝑟𝑖′ > 7. 𝑟𝑖5 𝑒 𝑥𝑎𝑐 𝐼7 6. < 𝑟𝑖′ → 𝑟𝑖′′′ ; 𝑑 ↔ 𝑒 > 8. 𝑑𝑏 𝑥𝑎𝑐 − 7. < 𝑟𝑖′′′ → 𝑏; 𝑒 ↔ 𝑑 > ∀ programs 𝑟𝑖 of type < 𝑎 → 𝑏; 𝑐 → 𝑑 > there is a To better illustrate how executing individual restricted subset 𝐽 of set of programs of the agent: programs leads to the same outcome as executing the 𝐽1. < 𝑎𝑐 → 𝑟𝑖 ; (𝑒, 𝑖𝑛) > homogeneous program 𝑟𝑖 , we will provide a step-by- 𝐽2. < 𝑟𝑖 → 𝑟𝑖1 𝑒; (𝑒, 𝑜𝑢𝑡) > step demonstration. The following table presents the 𝐽3. < 𝑟𝑖1 → 𝑟𝑖2 𝑒; (𝑒, 𝑜𝑢𝑡) > configurations of the agent and the environment, along 𝐽4. < 𝑟𝑖2 → 𝑟𝑖3 𝑒; (𝑒, 𝑜𝑢𝑡) > with the applicable rule for the agent. 𝐽5. < 𝑟𝑖3 → 𝑟𝑖4 𝑒; (𝑒, 𝑜𝑢𝑡) > 𝐽6. < 𝑟𝑖4 → 𝑟𝑖5 𝑒; (𝑒, 𝑜𝑢𝑡) > 𝐽7. < 𝑟𝑖5 → 𝑏𝑑; (𝑒, 𝑜𝑢𝑡) > agent env. prog. 4. Computational Power of P 1. 𝑎𝑐 𝑥 1 2. 𝑟𝑖 𝑒 𝑥𝑐 2 colonies 3. 𝑟𝑖′ 𝑐 𝑥 3 For restricted P colonies, not using checking rules, the 4. 𝑟𝑖′′ 𝑒 𝑥𝑟𝑖′ 4 following results are known: 5. 𝑑𝑒 𝑥𝑟𝑖′ 5 6. 𝑑𝑟𝑖′ 𝑥 6 • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝑅(2, *, 5) = 𝑁 𝑅𝐸 in [5], 7. 𝑟𝑖′′′ 𝑒 𝑥𝑑 7 • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝑅(2, 2, *) = 𝑁 𝑅𝐸 in [6], 8. 𝑏𝑑 𝑥 − • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝑅(2, 57, 8) = 𝑁 𝑅𝐸 in [7]. The program 𝑟𝑖 : < 𝑎 → 𝑏; 𝑐 → 𝑑 > is simulated by performing seven programs in seven computation steps. For homogeneous P colonies, not using checking rules, ∀ programs 𝑟𝑖 of type < 𝑎 ↔ 𝑏; 𝑐 ↔ 𝑑 >: the following results are known: To simulate execution of the program 𝑟𝑖 the agent has a subset 𝐴 of programs : • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝐻(2, 92, 3) = 𝑁 𝑅𝐸 in [7], 𝐴1. < 𝑎 → 𝑟𝑖 ; 𝑐 ↔ 𝑑 > • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝐻(2, 70, 5) = 𝑁 𝑅𝐸 in [7], 𝐴2. < 𝑑 → 𝑟𝑖′′ ; 𝑟𝑖 ↔ 𝑐 > • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝐻(2, 2, 163) = 𝑁 𝑅𝐸 in [7]. 𝐴3. < 𝑐 → 𝑑; 𝑟𝑖′′ ↔ 𝑒 > 𝐴4. < 𝑒 → 𝑒; 𝑑 ↔ 𝑟𝑖′′ > For P colonies using generating and consuming pro- 𝐴5. < 𝑟𝑖′′ → 𝑒; 𝑒 ↔ 𝑟𝑖′ > grams there are known results only for cases when agents 𝐴6. < 𝑟𝑖′ → 𝑏; 𝑒 ↔ 𝑑 > contain only one type of such programs, the agents are Agent 𝐵 (for every agent in original P colony there called senders and consumers. is one agent of type 𝐵, or for every communication pro- • 𝑁 𝑃 𝐶𝑂𝐿𝑠𝑐 (2, 2, *) = 𝑁 𝑅𝐸 in [8, 9]. gram there is one such agent): 𝐵1. < 𝑒 → 𝑎; 𝑒 ↔ 𝑟𝑖 > From the transformations described, we can derive 𝐵2. < 𝑟𝑖 → 𝑟𝑖′ ; 𝑎 ↔ 𝑏 > data for new results related to restricted, homogeneous, 𝐵3. < 𝑏 → 𝑐; 𝑟𝑖′ ↔ 𝑒 > and especially P colonies with generating and consuming 𝐵4. < 𝑒 → 𝑒; 𝑐 ↔ 𝑒 > programs. 𝐵5. < 𝑟𝑖 → 𝑙; 𝑎 ↔ 𝑒 > For homogeneous P colonies, we can add the following 𝐵6. < 𝑙 → 𝑙; 𝑒 ↔ 𝑒 > result: The agent, by executing programs from set 𝐴, sends object 𝑟𝑖 to the environment, which acts as a label for • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝐻(2, 57, 64) = 𝑁 𝑅𝐸. the executed program and simultaneously checks for the presence of object 𝑑 in the environment. Agent 𝐵, For homogeneous P colonies, we find that the class based on the object 𝑟𝑖 , checks for the presence of object of P colonies with at most 57 agents, each having up to 𝑏 in the environment. This checking process involves 64 programs, is computationally complete. This result moving the checked object inside the agent. Programs allows us to reduce the number of agents from 70 to 57 𝐵5 and 𝐵6 ensure an infinite loop if the program 𝑟𝑖 by increasing the number of programs associated with being simulated is not applicable (i.e., object 𝑏 is missing each agent. from the environment). Program 𝐵5 can also be applied For P colonies with generating and consuming pro- even if object 𝑏 is present in the environment because grams, there are four new results: the selection of a program from the set of applicable programs is random. Since the computation is defined • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝐺𝐶(2, 2, 1305) = 𝑁 𝑅𝐸, as nondeterministic, a corresponding computation exists • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝐺𝐶(2, 57, 48) = 𝑁 𝑅𝐸, for the case where program 𝑟𝑖 is applied in the correct • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝐺𝐶(2, 70, 41) = 𝑁 𝑅𝐸, configuration. Other computations result in infinite loops • 𝑁 𝑃 𝐶𝑂𝐿𝑝𝑎𝑟 𝐺𝐶(2, 92, 25) = 𝑁 𝑅𝐸. and thus do not lead to a result. agent agent 𝐵 env. prog.𝐴 prog.𝐵 1. 𝑎𝑐 𝑒𝑒 𝑏𝑑 𝐴1 − 5. Conclusion 2. 𝑟𝑖 𝑑 𝑒𝑒 𝑏𝑐 𝐴2 − 3. 𝑟𝑖′′ 𝑐 𝑒𝑒 𝑏𝑟𝑖 𝐴3 𝐵1 In this study, we explored various P colony mod- 4. 𝑒𝑑 𝑎𝑟𝑖 𝑏𝑟𝑖′′ 𝐴4 𝐵2 els—restricted, homogeneous, and those using gener- 5. 𝑒𝑟𝑖′′ 𝑟𝑖′ 𝑏 𝑎𝑑 − 𝐵3 ating and consuming programs—highlighting their op- 6. 𝑒𝑟𝑖′′ 𝑐𝑒 𝑎𝑑𝑟𝑖′ 𝐴5 𝐵4 erational differences. Our analysis showed that each 7. 𝑒𝑟𝑖′ 𝑒𝑒 𝑎𝑑𝑐 𝐴6 − model has unique computational capabilities, shaped by 8. 𝑏𝑑 𝑒𝑒 𝑎𝑐 − − its rule types and agent structure. For example, restricted P colonies, with their mix of rewriting and communi- [7] L. Cienciala, L. Ciencialová, Some new re- cation rules, exhibit different computational behaviors sults of P colonies with bounded parameters, than homogeneous colonies, which use only one type of Natural Computing (2016) 1–12. doi:10.1007/ rule. Transformations between these models also reveal s11047-016-9591-0. insights into their computational power. [8] L. Cienciala, L. Ciencialová, P colonies and their ex- In the final section of the paper, we presented six new tensions, in: J. Kelemen, A. Kelemenová (Eds.), Com- results that illustrate the dependence of the number of putation, Cooperation, and Life, Springer-Verlag, agents and the maximum number of programs associ- Berlin, Heidelberg, 2011, pp. 158–169. ated with a single agent on the computational complete- [9] L. Ciencialová, L. Cienciala, P. Sosík, Generalized P ness of P colonies constrained by these parameters. For colonies with passive environment, in: C. Graciani, P colonies with generating and consuming programs, D. Orellana-Martín, A. Riscos-Núñez, Á. Romero- these are the first results, as the computational power Jiménez, L. Valencia-Cabrera (Eds.), Fourteen Brain- of colonies using such program combinations associated storming Week on Membrane Computing, 2016, pp. with a single agent has not yet been explored. 151–162. 6. Acknowledgments This work is supported by the Silesian University in Opava under the Student Funding Plan, project SGS/9/2024. References [1] J. Kelemen, A. Kelemenová, Gh. Păun, Preview of P colonies: A biochemically inspired computing model, in: Workshop and Tutorial Proceedings. Ninth Inter- national Conference on the Simulation and Synthesis of Living Systems (Alife IX), Boston, Massachusetts, USA, 2004, pp. 82–86. [2] J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison- Wesley, 1979. [3] Gh. Păun, G. Rozenberg, A. Salomaa, The Oxford Handbook of Membrane Computing, Oxford Univer- sity Press, Inc., New York, NY, USA, 2010. [4] L. Ciencialová, L. Cienciala, P. Sosík, Generalized P colonies with passive environment, Theoretical Computer Science 724 (2018) 61–68. doi:https:// doi.org/10.1016/j.tcs.2017.12.009. [5] R. Freund, M. Oswald, P colonies working in the max- imally parallel and in the sequential mode, in: D. Za- harie, D. Petcu, V. Negru, T. Jebelean, G. Ciobanu, A. Cicortas, A. Abraham, M. Paprzycki (Eds.), Sev- enth International Symposium on Symbolic and Nu- meric Algorithms for Scientific Computing (SYNASC 2005), 25-29 September 2005, Timisoara, Romania, IEEE Computer Society, 2005, pp. 419–426. doi:10. 1109/SYNASC.2005.55. [6] L. Cienciala, L. Ciencialová, A. Kelemenová, On the number of agents in P colonies, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4860 LNCS (2007) 193–208.