In this paper we introduce the notion of transferable programs as shared knowledge applied in diferent types of P colonies. We will discuss the basic type of P colonies and 2D P colonies. We will show the possibilities of using transferable programs using examples.
from this set to the environment.
The agent’s program set consists of two kinds of
proP colony is very simple computational device related to grams.
membrane systems inspired by colonies of formal gram- The first type can be named internal programs. These
mars. Since 2004, when P colonies were introduced in are the agent’s essential programs and cannot be shared.
[
A basic P colony consists of a finite number of agents grams. These are programs that allow agents to perform and their joint shared environment. The agents are activities they did not know how to do - their program set formed from a finite number of objects and their func- did not contain such programs. These can be instructions tioning is based on programs consisting of rules. These on how to use various devices present in the environment, rules are of two types: they may change the objects of instructions contained in someone else’s DNA, etc. the agents and they can be used for interacting with the The paper is structured as follows: after the introducshared environment of the agents. In the case of a ba- tory section introducing readers to preliminaries and sic P colony, the environment is a multiset of objects. basic notions, there is a section on basic P colonies and The number of objects inside each agent is set by defi- their extension to transferable programs. The fourth nition and it is usually a very small number: 1, 2 or 3. section is devoted to shared programs in a 2D P colony The environment is processed by the agents and it is environment. In conclusion, we summarize the content used as a communication channel for the agents as well of the paper and outline future research goals for the since through the environment, the agents can afect the behaviour of P colonies. behaviour of another agent.
The idea of shared knowledge lies in transferable
programs. These are programs that are equipped with a 2. Preliminaries and Basic Notions
condition that, when satisfied, allows the program to
be transferred to the agent’s program set or, conversely,
Throughout the paper we assume the reader to be
familiar with the basics of the formal language theory and
membrane computing [
IbTeArT2’32–22:7I,n2fo0r2m2,aZtiuobnetreecch,nSololovgaikeisa– Applications and Theory, Septem- For an alphabet Σ , the set of all words over Σ (includ" lucie.ciencialova@fpf.slu.cz (L. Ciencialová); ing the empty word, ), is denoted by Σ * . We denote ludek.cienciala@fpf.slu.cz (L. Cienciala) the length of a word ∈ Σ * by || and the number © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License of occurrences of the symbol ∈ Σ in by ||. CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org)
A multiset of objects is a pair = (, ), where The third type of rules is the checking rule. A checking
is an arbitrary (not necessarily finite) set of objects and rule is formed from two rules of one of the two previous
is a mapping : → ; assigns to each object in types. If a checking rule 1/2 is performed, then the rule
its multiplicity in . Any multiset of objects with the 1 has higher priority to be executed over the rule 2.
set of objects = {1, . . . } can be represented as This means that the agent checks whether or not rule
a string over alphabet with || = (); 1 ≤ ≤ 1 is applicable. If the rule can be executed, then the
. Obviously, all words obtained from by permuting agent must use this rule. If rule 1 cannot be applied,
the letters can also represent the same multiset , and then the agent uses rule 2.
represents the empty multiset. The program determines the activity of the agent: the
agent can change its state and/or the state of the
environment.
3. Basic P colonies The environment is represented by a finite number
of copies of non-environmental objects and countably
The original concept of a P colony was introduced in [
the initial state (or the initial content) of the At each step of the computation (at each transition), the agent; state of the environment and that of the agents change in – = {,1, . . . , , } is a finite set of pro- the following manner: In the maximally parallel derivagrams, where each program consists of tion mode, each agent which can use any of its prorules, which are in one of the following forms grams should use one (non-deterministically chosen), each: whereas, in the sequential derivation mode, only one ∗ → , , ∈ , called an evolution agent at a time is allowed to use one of its programs (nonrule; deterministically chosen). If the number of applicable ∗ ↔ , , ∈ , called a communi- programs for an agent is higher than one, then the agent cation rule; non-deterministically chooses one of the programs. ∗ 1/2, called a checking rule; 1, 2 A sequence of transitions is named a computation. are both evolution rules or both com- A computation is halting if in the last configuration that munication rules. is obtained there is no program that can be applied. With a halting computation, we associate a result which is
Now, we add brief explanations of the components of given as the number of copies of the objects present in the P colony. the environment in the halting configuration.
The first type of rules associated with the programs Because of the non-determinism in choosing the proof the agents, the evolution rules, are of the form → . grams, starting from the initial configuration we obtain This means that object inside the agent is rewritten to several computations, hence, with a P colony, we can (evolved to be) object . associate a set of numbers, denoted by (Π) , computed
The second type of rules, the communication rules, are by all possible halting computations of given P colony.
of the form ↔ . If a communication rule is performed, In the original model (see [
Such programs can be considered knowledge sources
Although P colonies are very simple computing de- (and in some cases object sources). Permanent transfervices, due to their (mainly parallel) working mode and able programs may allow an agent to produce an object distributed nature they demonstrate large expressive that does not exist in the environment and that the agent (computational) power. In most cases, computational could not otherwise obtain before getting the program. = pow pow pow pow pow
4n p s-b ︀(⟨ ︁(⟨ ︁(⟨ ︁(⟨ ︁(⟨ ︁(⟨ s-b s-b s-b ⟩ ⟩ ⟩ ⟩ → tt , ↔ , { pow } → l , ↔ , { pow } → tth , ↔ , { tt } → lh , ↔ , { l } → ts , ↔ ︀⟩ , { tc })︀ ︁) ︁) ︁) ︁)
saw wood lathe drill drill angle grinder → tp , → ⟩ , { ts }︁) paint spray gun completeness can be obtained with these constructs even with very few components and very few restrictions on the programs. 3.1. P Colonies with transferable
programs In this section, we focus on the definition of transferable programs. Under what conditions can a program be transferred into an agent, and under what conditions can an agent transfer a program into an environment?
A transferable program is an ordered pair (program, condition). We distinguish two kinds of conditions: 1.
Object condition - for a program to be transferred, the destination must contain (or must not content) certain objects. A condition is specified as a set of multisets of objects. Each of the multisets has a size equal to the capacity P of the colony. 2. program condition - for a program to be transferred, the destination must contain (or not contain) a certain program.
Let Π
be a P colony of capacity 2 with one agent and working with objects , , , . Examples of transferable programs are: • (⟨ → ; ↔ ⟩ ; {}) – when such program is placed in the environment an agent can consume it only if it contains two copies of object ; when such a program is placed in the agent it can be transferred into environment only if the environment contains at least two copies of object ; objects.
there) • (⟨ → ; ↔ ⟩ ; {¬, ¬}) – when such program is placed in the environment an agent can consume it only if it does not contain two copies of object or one object and one object ; such a program cannot be transferred into the environment. The conditions can never be met, the environment always contains environmental • (⟨ → ; ↔ ⟩ ; {⟨ → ; ↔ ⟩}) – this program can only be
moved if program ⟨ → ; ↔ ⟩ is contained inside the recipient (in its program set if it is an agent, or directly in the environment if the program is to be moved
We call a transferable program (program; condition) permanent (denoted by the in the subscript) if each time the program is moved to a diferent destination, one copy of the program remains at the original location. p 4n s-b l lh lc tt tth ttn tt1l tt2l tt3l tc ts tp } pow pow tt l tc ts
Initial content of the environment is now defined as multiset over ∪ {set of transferable programs }.
Using transferable programs within a computation – In every step of a computation an agent can apply one of its applicable programs or transfer program in or out. It means that moving a program takes one step of computation as well as applying the program.
Example 1. Let Π 1 be a P colony with one agent whose environment is a workshop with machines that enable the processing of the product. If the agent has (contains) raw materials that the machine can process, then the agent uses the machine. That is, it obtains a program from the environment that allows it to process the raw materials.
︁(
, , tp , , ︁) is defined as follows: P colony Π 1 = = { pow piece of wood, paint, four nuts, leg, leg with hole, complete leg, ⟨ ↔ ttn , ↔ lc
, → , put nuts on the holes
→−− − − − − − p−− o−− w−− − − − − − − − − − ⟩ ⟩ ⟩ , ⟩ ⟩ ⟩ ⟩ ⟩ ⟩ Agent is in the initial state and its set of programs agent. These programs allow the agent to process pieces is formed from its ability to work with or without hand of wood into a table top or leg. we can imagine that the agent, by transferring the program, "picks up" a saw or uses a wood lathe. →−− − − − − − p−− o−− w−− − − − − − − − − − (︂⟨ ︁) program. This program allow it to consume one piece of the agent obtain leg with hole. Then agent put the leg to
The agent himself can’t process a piece of marrow.
There are two programs in the environment that (if the →−− − − − − − − p−− o−− w−− − − −−− − − − ︂(⟨ ︁( ︁) agent contains a piece of wood) can be transferred to the pow → l ,↔ ,{ pow }
Now the agent can use this program to make the table top from piece of wood.
pow → tt ,↔ ,{ pow }
Because of non-determinism the agent can import the second transferable program instead of using the first one.
In the next step, the agent can import a new program from the environment that allows it to drill holes in the table top. In the next step, the agent use imported program and then the agent move the table top with holes into ︀) ︁) ︁( ︂(⟨ ︂(⟨ the environment.
tt →−− − − − − − − − − − − − − − − − − − − ︂(⟨ ︀) ︀( →−− − − − − − − − − − − − − − − − − − −
tt ︁( ︁( ︁( ︀( , , take a piece of wood
take a screw bolt → , mount the screw bolt put down complete leg
take four nuts take the table top ↔ tt1l , lc
→ , mount the complete leg ↔ , ↔ ,
put down the table top ⟨ ↔ tt1l , ↔ lc
, take the table top with leg and the second complete leg ↔ tt2l , lc
→ , mount the second leg ↔ , ↔ ,
put down the table top ⟨ ↔ tt2l , ↔ lc
, take the table top with 2 legs and the second complete leg ↔ tt3l , lc → ,
mount the third leg ↔ , ↔ ,
put down the table top ⟨ ↔ tt3l , ↔ lc
take the table top and the third complete leg ↔ tc , lc → ,
mount the fourth leg → ts , ↔ ︀⟩ , ⟩ on the table top ↔ , ↔ , put down the painted table
take the paint tools: = { ⟨ ↔ ⟨ ⟨ ⟨ ⟨ ⟨ ⟨ ⟨ ⟨ ⟨ ⟨ ⟨ ⟨ ⟨ lh lh lc tth tth ttn tt1l tt1l tt2l tt2l tt3l tt3l tp ︀⟨ ts } wood. ⟩ ⟩ ⟩ ⟩ ⟩ ⟩ ︁) ︁) pow ︀( tt ︀) pow ︂) ︂) ︁( ︂) ︁( ︁( ︀( tt ︀) tth
︁) ︂) ︂) ()
︀( ttn )︀ pow → l ,↔ ,{ pow } (︁
import l → lh ,↔ ,{ l } l → lh ,↔ ,{ l } ︁(
⟨ lh ↔,↔⟩ l→h−− − − − − − − − − ↔ lh ,↔ s-b ⟩ ⟨ lh → lc , s-b →⟩
⟨ lc ↔,↔⟩ →c−− l − − −−− − − − ︁( ︁( ︁( ︁( ︁( ︁( ︁) ︁) ︁) ︁) ︁) →−− − − −(− −−−−−)− − →t−n−− t − − − − l−c−− − − − − − − →−− − − (−− − − −−)−− − t→t1−−l− − − − − l− c−− − − − − − − →−− − − (−− − − −−)−− − t→t2−−l− − − − − l− c−− − − − − − − ⟨ ⟨ ︁) ︁) ︁) ⟨ ⟨ ↔ tt3l ,↔ lc ⟩
⟨ tt3l → ttc , lc →⟩ →−− − − (−− − − −−)−− − tt3 →−− l− − − l−c−− − − − − − − − ︁) ︁( tt3l lc
︁) ︀( ttc )︀ ⟩ ⟩ ⟩ ⟩ import tc → ts ,↔ ,{ tc } tc → ts ,↔ ,{ tc } ⟨ ts → ts ,↔⟩
import ts → tp ,→ ,{ ts } ts → tp ,→ ,{ ts } ︁( ︂) ︂) ︂) ︂) () ︀( tc ︀) ︀( ts ︀) ︀( ts ︀) tp
︁) ︀( →−t−−s− − − −−− − − −
︀)
The last executed program is to put painted table into ︁( ︁( ︁( ︁( l
︁) ︁) ︁) l
︁) lh lc ︂) ︂) ︁( ︂) () lh s-b () ttn lc
() tt1l lc
() tt2l lc () ︁( ︁( ︁( ︁) ︁) ︁) ︁) ↔ ttn ,↔ lc ⟩ ⟨ ttn → tt1l , lc →⟩
⟨ tt1l ↔,↔⟩ tt →1−l−− − − −−− − − − ↔ tt1l ,↔ lc ⟩ ⟨ tt1l → tt2l , lc →⟩
⟨ tt2l ↔,↔⟩ tt →2−l−− − − −−− − − − ↔ tt2l ,↔ lc ⟩ ⟨ tt2l → tt3l , lc →⟩
⟨ tt3l ↔,↔⟩ tt →3−l−− − − −−− − − − ︁( tt1l
︁) tt2l tt3l ︁) ︁) ︁) ︁) ︁) ︁( ︁( ︂(⟨ ︂(⟨ ⟨ ︁( ︁( ︁(
The agent can make the legs and the table tops up to a total quantity of five. Only such computations where agents makes one table top and four legs leads to successful end - production of one painted table. grams. gun.
During the computation, the agent can export programs that allow the processing of a piece of wood - if there is a piece of wood in the environment the program can be transferred. After processing the last piece of wood, the program remains in the agent’s set of pro
When the agent contains the complete table, it can import program that allows agent to use angle grinder and proceed from the complete table to the sanded table.
Then the agent can take the paint and import the last program to spray the table with paint using a paint spray ︀( ︀( ︀( ︀( ︁(
tc →−− − − − − − − − − − − − − − − − − − ︂(⟨
→−− − − − − − − − − − − − −−− − − − tc ts →−− − − − − − − − − − − − − − − − − − − ︂(⟨
→−− − − − − − − − − t−s−− − − −−− − −
︀) environment.
︁( ︀) ︀) ︀) ︂(⟨ ︂(⟨
︁) t→p−− − −− − − − − − ⟨ tp ↔,↔⟩
︀( e )︀
If we add a special object to the environment, which will be part of the condition for transfer in all transferable programs, the agent can end computation only when it "returns" all transferred programs back to the environment.
In [
As in the original model, the P colony is of capacity two and the agents are equipped with sets of the programs formed from rules – communication and evolution. The main change is in the environment. The authors put the agents into the 2D grid of square cells and they provide the agent with the possibility to move – the motion program. 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 motion program can contain one motion rule and one evolution rule.
Definition 2.
A 2D P colony is a construct Π = ( , , , 1, . . . , , ), ≥ 1, where • is an alphabet of the colony, its elements are
called objects, • ∈ is the basic environmental object of the 2D
P colony, • is a pair ( × , ), where × , , ∈ is the size of the environment and is the initial contents of environment, it is a matrix of size × of multisets of objects over − { }. • , 1 ≤ ≤ , are agents, each agent is a construct = (, , [, ]) , 0 ≤ ≤ , 0 ≤ ≤ , where – is a multiset over , it determines the
initial state (contents) of the agent, || = 2, – = {,1, . . . , , } , ≥ 1, 1 ≤ ≤ is a finite set of programs, where each program contains exactly 2 rules, which are in one of the following forms each: ∗ → , called the evolution rule,
, ∈ , ∗ ↔ , called the communication rule,
, ∈ , ∗ [,] → , 0 ≤ , ≤ 2, ∈ {⇐
, ⇒, ⇑, ⇓}, called the motion rule, • ∈ is the final object of the colony.
A configuration of the 2D P colony is given by the state of the environment - matrix of type × with multisets of objects over − { } as its elements, and by the state of all agents - pairs of objects from alphabet and the coordinates of the agents. An initial configuration is given by the definition of the 2D P colony.
A computational step consists of three parts. The first part lies in determining the set of applicable programs according to the current configuration of the 2D P colony.
In the second part, we have to select from this set one program for each agent, in such a way that there is no collision between the communication rules belonging to diferent programs. The third part is the execution of the chosen programs.
A change of the configuration is triggered by the execution of programs and it involves changing the state of the environment, contents and placement of the agents.
A computation is non-deterministic and maximally parallel. The computation ends by halting when there is no agent with applicable program.
The result of the computation is the number of copies of the final object placed in the environment at the end of the computation.
The aim of introducing 2D P colonies is not studying their computational power but monitoring their behaviour during the computation. 4.1. 2D P Colonies with transferable
programs We can introduce transferable programs into 2D P colonies model.
Aspects of transferable programs composed of evolutionary and communication rules have already been mentioned in the previous section.
A transferable motion program can upgrade an agent’s motion capabilities. For example, an agent that previously could only move in one direction now has the ability to move left, right, or backwards.
The agent’s program The transferred program ⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇑; →
⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇐; →
If the agent had any restrictions in the original motion programs under which it could move in a certain direction, these restrictions can be changed. For example, if the agent could only move to the left if there was an object on the left, then after importing the program, it will also be able to move to the left if there is an object to the left of the agent. The agent’s program The transferred program ⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇐; →
⟨ ⎡ ⎣ ⎤ ⟩ ⎦ → ⇐; →
Similarly, constraints can be imposed on the agent’s content. The agent may be given "one-time permission" to turn left in the form of object , which it will be able to rewrite to another object while according to the agent’s movement rule agent moves left.
The transferred program ⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇐; →
The first agent 1 = (, 1, [0, 0]) has a set of programs 1 that include the following programs: Example 2. Consider a 2D P colony with two agents or 2. apply one of the motion programs. Executing Π 2 = (, , , 1, 2, ). The first agent can move the motion program changes the agent’s position and around the environment and spread the transferable pro- also changes its state to . In the following step, the gram allowing the agent to consume slave object. The agent can also export a program or apply a program second agent’s programs allows the agent to move only if ⟨ → ; ↔ ⟩. By executing the program, the agent slave object is inside the agent. If the second agent enters places the slave object in the cell and changes its state special position in the environment it can import a program to . that enables the agent to make its own object . The agent The second agent is in state at the beginning of the that imports such a program will then not have to follow computation. It has no applicable program until the first the first agent. agent visits its position and places transferable program (⟨ → ; ↔ ⟩ , {}) there. Thus, the movement of
The environment has a size 5 × 5 and each cell con- agent 2 is thus dependent on this program and the
tains only environmental objects except for the cell with presence of object in the environment.
address [
(⟨ → ; ↔ ⟩ , {}) ⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇒; →
⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇐; →
⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇑; →
⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇓; →
⟨ → ; ↔ ⟩ ⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇒; →
⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇐; →
⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇑; →
⟨ ⎡ ⎤ ⟩ ⎣ ⎦ → ⇓; →
The first agent 2 is defined as (, 2, [
The single cells of the 2D environment represent parts of a school building (or multiple buildings) such as classrooms, laboratories, libraries, teachers’ ofices, etc. The student’s goal is to obtain a grade in the course (object - mark). At the beginning of the computation, agent – student can contain either only environmental symbols or also an object that expresses his intention to successfully complete the course (object ). Its movement through environment can be random (the agent can use any of movement program, it can move in any direction)
There may be other agents in the environment such as teachers who will move from their ofice to the classroom or lab and back again. If they encounter a student in these rooms (the student places their marker in the environment), they can provide a program that allows the student to advance closer to obtaining the object.
Let to get the grade require attending a class, gaining knowledge by studying in the library and lab, and finally passing an exam. Thus, object can be acquired over time by a subscript that captures the facts of the actions taken (T - teacher, L - library, A - lab, C - consultation).
We can determine under which conditions it is possible to change the index just with the help of transferable programs that are available in diferent rooms - cells.
We leave it to the esteemed reader to construct particular programs for student and teacher.
The first agent starts the computation in the state In this paper we introduced the notion of transferable with two options - 1. export the transferable program, programs in two models of P colonies - basic P colonies and 2D P colonies. One of the main features of P colonies is the use of environment agents to store shared objects.
Thus, objects can be used by all agents that are in a given part of the environment and know how to handle the object (have programs that process the object). Transferable programs allow not only to share objects, but also to share the ability to handle these objects.
Our goal for the future is to introduce a type of numerical P colony with transferable programs, whose agents would acquire their abilities by moving around in an environment that has a specified structure. Agents in such a P colony would perform search algorithms known, for example, from graph theory.
This work was supported partially by European Union under European Structural and Investment Funds Operational Programme Research, Development and Education project Zvýšení kvality vzdělávání na Slezské univerzitě v Opavě ve vazbě na potřeby Moravskoslezského kraje, CZ.02.2.69/0.0/0.0/18_058/0010238 and by the Silesian University in Opava under the Student Funding Scheme, project SGS/8/2022.