This paper explores diferent 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.
modify the objects they possess and exchange some of their objects with those in the environment. These coIn 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 conP 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
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 eforts 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 environeach 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 introcases 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 *SeCpotrermesbperon20d–in2g4,a2u0t2h4o,rČ.ergovské Vrchy, Slovakia 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
Throughout the paper we assume the reader to be familiar with the basics of the formal language theory and membrane computing [2, 3].
For an alphabet Σ , the set of all words over Σ (including the empty word, ), is denoted by Σ * . We denote the length of a word ∈ Σ * by || and the number of occurrences of the symbol ∈ Σ in by ||.
A multiset of objects is a pair = (, ), where is an arbitrary (not necessarily finite) set of objects and is a mapping : → ; assigns to each object in its multiplicity in . Any multiset of objects with the set of objects = {1, . . . } can be represented as a string over alphabet with || = (); 1 ≤ ≤ . Obviously, all words obtained from by permuting the letters can also represent the same multiset , and represents the empty multiset. 2.1. P Colonies In the following we describe the concept of a P Colony.
The original definition of P colony was introduced in [1]. In this paper, we will use an extended definition [4], which we have slightly modified by excluding the possibility of an evolving environment.
Rewriting rule → allows an agent to rewrite (evolve) one object placed inside the agent to object .
• Σ is the alphabet of the colony, its elements are
called objects, • is the basic (environmental) object of the colony,
∈ Σ , • is final object of the colony, ∈ Σ , • is the initial content of the environment, ∈
(Σ − { })* ,
• , 1 ≤ ≤ , are the agents, every agent is the
structure = (, ), where is a multiset over
Σ , it defines the initial state (content) of the agent
and || = and = {,1, . . . , , } is the
ifnite set of programs of three types:
(
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
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 . ForGenerating rule → creates two objects , from mally, the configuration of the P colony Π is given by one object . (1, . . . , , ), where || = , 1 ≤ ≤ , 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 diferent 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 derivathe 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.
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 cain 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 lagrams, 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 diferent 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
without an input information.
A P colony is called restricted if each program consists If we need to transform restricted programs into homoof one evolving rule and one communication rule. A P geneous ones, we must address the situation where hocolony 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 envithird 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 diferent 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. < → ; → ℎ >
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. 1. ℎℎ 1 1 2. ′ ℎℎ 2 − 3. ℎ ℎ ℎ′ 3 − 4. ℎ ℎ ′ℎ 4 − 5. ℎ ℎ ′ℎ 5 − 6. ′ ℎ ℎℎ 6 − 7. ℎ ℎℎ − −
The program is simulated by performing six programs in six computation steps. Last two programs are used for entering and performing infinite loop. 3.2. Transformation from Generating and
Consuming to Restricted Programs To transform a P colony with insertion and deletion programs into a P colony with restricted programs, we need to use a similar tactic to add a certain number of auxiliary objects ℎ to the initial configuration of the P colony’s environment or introduce new agents that place such objects into the environment themselves.
Agents of type serve as generators of ℎ objects. 1. < ℎ → ℎ; ℎ ↔ > 2. < → ; ℎ ↔ > ∀ programs of type < → ; (, ) > there are programs in subset of programs of agents: 1. < → ; ↔ > 2. < → ′; ↔ ℎ > 3. < ′ → ; ℎ ↔ > 4. < → ′′; ↔ ℎ > 5. < ′′ → ; ℎ ↔ >
Using this program, the agent does not need an object from the environment; instead, it places an object into the environment. Two objects ℎ are required for the simulation.
agent env. prog. 1. ℎℎ 1 2. ℎℎ 2 3. ′ℎ ℎ 3 4. ℎℎ 4 5. ′′ℎ ℎ 5 6. ℎℎ − ∀ programs of type < → ; (, ) > there is subset of programs of the agent: 1. < → ; ↔ > 2. < → ′; ↔ > 3. < → ; ′ ↔ > 4. < → ℎ; ↔ ′ > 5. < ′ → ; ℎ ↔ >
To execute the consuming program, the presence of object in the environment is required. This condition also applies to the execution of the first restricted program in the simulation of rule . If this check were to occur at a later stage in the simulation, it could lead to an improper application of the program, as the simulation of other programs might temporarily place some objects into the environment that will be back inside these agents by the end of the simulation. Consider a configuration that does not contain object . During the simulation of a single computation step, one of the agents uses a program of type E4 and temporarily places object into the environment, intending to remove it in the next computation step using a rule of type E5. If, during the computation phase when object is present in the environment, a check for the presence of for a consuming program is performed, then the programs of both agents would be applicable.
agent env. prog. 1. ℎℎ 1 2. ℎℎ 2 3. ′ ℎℎ 3 4. ℎℎ′ 4 5. ′ℎ ℎ 5 6. ℎℎ
− 3.3. Transformation from Restricted to
Generating and Consuming Programs Since executing a restricted program involves the agent exchanging an object with another from the environment, both generating and consuming programs must be executed during the simulation. In this paper, we allow one agent to contain both types of these programs.
∀ programs of type < → ; ↔ > there are following programs in the subset of programs of the corresponding agent: 1. < → ; (, ) > 2. < → ′; (, ) > 3. < ′ → ′′; (, ) > 4. < ′′ → ′′′; (, ) > 5. < ′′′ → ; (, ) > 6. < → ; (, ) >
Objects , ′, ′′, ′′′, and serve to mark the phase of the restricted program simulation, and they are used to generate the necessary objects accordingly.
step agent H env. prog.
1. 1 2. 2 3. ′ 3 4. ′′ 4 5. ′′′ 5 6. 6 7.
− 3.4. Transformation from Homogeneous to Generating and Consuming
Programs Homogeneous programs can be of two types: either both objects in the agent are rewritten into new objects (not necessarily diferent from the original ones), or both ob- In addition to ensuring that during the first step of simjects 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 afect 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 othfrom 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 diferent 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 transformaProgram 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 communicaincluded 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 → ; (, ) >
For restricted P colonies, not using checking rules, the
following results are known:
• (2, * , 5) = in [5],
• (2, 2, * ) = in [6],
• (
For homogeneous P colonies, not using checking rules,
the following results are known:
• (
For P colonies using generating and consuming programs there are known results only for cases when agents contain only one type of such programs, the agents are called senders and consumers.
• (2, 2, * ) = in [8, 9].
From the transformations described, we can derive data for new results related to restricted, homogeneous, and especially P colonies with generating and consuming programs.
For homogeneous P colonies, we can add the following result:
• (
For homogeneous P colonies, we find that the class of P colonies with at most 57 agents, each having up to 64 programs, is computationally complete. This result allows us to reduce the number of agents from 70 to 57 by increasing the number of programs associated with each agent.
For P colonies with generating and consuming
programs, there are four new results:
• (
In this study, we explored various P colony models—restricted, homogeneous, and those using generating and consuming programs—highlighting their operational diferences. Our analysis showed that each model has unique computational capabilities, shaped by 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 recation rules, exhibit diferent 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.), Comresults 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, Á. Romerothese are the first results, as the computational power Jiménez, L. Valencia-Cabrera (Eds.), Fourteen Brainof colonies using such program combinations associated storming Week on Membrane Computing, 2016, pp. with a single agent has not yet been explored. 151–162.
This work is supported by the Silesian University in Opava under the Student Funding Plan, project SGS/9/2024.