Transferable Knowledge in P Colonies Lucie Ciencialová1 , Luděk Cienciala1 1 Institute of Computer Science and Research Institute of the IT4Innovations Centre of Excellence, Silesian University in Opava, Opava, Czech Republic Abstract In this paper we introduce the notion of transferable programs as shared knowledge applied in different 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. Keywords membrane computing, P colonies, transferable knowledge, paralell computing, multi-agent system 1. Introduction from this set to the environment. The agent’s program set consists of two kinds of pro- P 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. [1], many types of these systems have been developed. This does not mean that such programs are unique in the Basically, these are P colonies with different restrictions P colony. They can be such acts of the agent that can on the type of programs used (restricted, homogeneous) be compared to the basic acts of living organisms such or working with an environment that is not only in the as respiration, digestion, and perception. Thus, they are form of a multiset, but also a string or a 2D grid. Even P functions that the organism knows by definition, does not colonies whose environment changes dynamically have have to learn, and cannot be taught to other organisms. been introduced. The interested reader is referred to [2] The second type, called transferable, is the opposite for detailed information on membrane systems (P sys- of the first type. It is the knowledge and abilities of an tems) and to [3] and [4] for more information to grammar agent that can be shared with the environment under systems theory. For more details on P colonies consult certain conditions. the surveys [5] and [6]. The environment may also contain transferable pro- 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 introduc- shared 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 affect the behaviour of P colonies. behaviour of another agent. The idea of shared knowledge lies in transferable pro- grams. 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 famil- iar with the basics of the formal language theory and membrane computing [7, 2]. ITAT’22: Information technologies – Applications and Theory, Septem- ber 23–27, 2022, Zuberec, Slovakia 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 Attribution 4.0 International (CC BY 4.0). of occurrences of the symbol 𝑎 ∈ Σ in 𝑤 by |𝑤|𝑎 . CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (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 envi- ronment. 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 [1] infinite copies of the environmental object 𝑒. and presented in a developed form in [8, 9]. In every step, each object inside an agent is affected Definition 1. A P colony of capacity 𝑘, 𝑘 ≥ 1, is a con- by the execution of a program. Depending on the rules struct in the program, the program execution may affect the environment as well. Π = (𝐴, 𝑒, 𝑓, 𝑣𝐸 , 𝐵1 , . . . , 𝐵𝑛 ), where The functioning of the P colony starts from its initial configuration (initial state). • 𝐴 is an alphabet, its elements are called objects; The initial configuration of a P colony is an (𝑛 + 1)- • 𝑒 ∈ 𝐴 is the basic (or environmental) object of the tuple of multisets of objects present in the P colony at the colony; beginning of the computation. It is given by the multisets • 𝑓 ∈ 𝐴 is the final object of the colony; 𝑜𝑖 for 1 ≤ 𝑖 ≤ 𝑛 and by multiset 𝑣𝐸 . Formally, the config- • 𝑣𝐸 is a finite multiset over 𝐴 − {𝑒}, called the uration of the P colony Π is given by (𝑤1 , . . . , 𝑤𝑛 , 𝑤𝐸 ), initial state (or initial content) of the environment; where |𝑤𝑖 | = 𝑘, 1 ≤ 𝑖 ≤ 𝑛, 𝑤𝑖 represents all the ob- • 𝐵𝑖 , 1 ≤ 𝑖 ≤ 𝑛, are agents, where each agent jects present inside the 𝑖-th agent, and 𝑤𝐸 ∈ (𝐴 − {𝑒})* 𝐵𝑖 = (𝑜𝑖 , 𝑃𝑖 ) is defined as follows: represents all the objects in the environment different – 𝑜𝑖 is a multiset over 𝐴 consisting of 𝑘 objects, from the object 𝑒. 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 deriva- grams, where each program consists of 𝑘 tion mode, each agent which can use any of its pro- rules, 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 (non- rule; 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 pro- of 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 [1]) the number of objects then object 𝑐 inside the agent and object 𝑑 in the envi- inside each agent is set to two, and the programs were ronment swap their location. Thus, after executing the formed from only two rules. Moreover, the initial config- rule, object 𝑑 appears inside the agent and object 𝑐 is uration was defined as (𝑛 + 1)-tuple (𝑒𝑒, . . . , 𝑒𝑒, 𝜀) so located in the environment. at the beginning of the computation the environment of the P colony is “empty”, it is without input information. Such programs can be considered knowledge sources Although P colonies are very simple computing de- (and in some cases object sources). Permanent transfer- vices, 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. completeness can be obtained with these constructs even Initial content of the environment is now defined as with very few components and very few restrictions on multiset over 𝐴 ∪ {set of transferable programs }. the programs. Using transferable programs within a computation – In every step of a computation an agent can apply one of 3.1. P Colonies with transferable its applicable programs or transfer program in or out. It means that moving a program takes one step of compu- programs tation as well as applying the program. In this section, we focus on the definition of transfer- able programs. Under what conditions can a program be Example 1. Let Π1 be a P colony with one agent whose transferred into an agent, and under what conditions can environment is a workshop with machines that enable the an agent transfer a program into an environment? processing of the product. If the agent has (contains) raw A transferable program is an ordered pair (program, materials that the machine can process, then the agent condition). We distinguish two kinds of conditions: 1. uses the machine. That is, it obtains a program from the Object condition - for a program to be transferred, the environment that allows it to process the raw materials. destination must contain (or must not content) certain (︁ )︁ P colony Π1 = 𝐴, 𝑒, tp , 𝑣𝑒 , 𝐵 is defined as follows: objects. A condition is specified as a set of multisets of objects. Each of the multisets has a size equal to the 𝐴 = { pow piece of wood, capacity P of the colony. 2. program condition - for a p paint, program to be transferred, the destination must contain 4n four nuts, (or not contain) a certain program. Let Π be a P colony of capacity 2 with one agent and s-b double ended screw bolt, working with objects 𝑎, 𝑏, 𝑒, 𝑓 . Examples of transferable l leg, programs are: lh leg with hole, • (⟨𝑎 → 𝑏; 𝑎 ↔ 𝑒⟩ ; {𝑎𝑎}) – when such program lc complete leg, is placed in the environment an agent can con- sume it only if it contains two copies of object 𝑎; tt table top, when such a program is placed in the agent it can tth table top with holes, be transferred into environment only if the en- ttn table top with nuts, vironment contains at least two copies of object 𝑎; tt1l table top with 1 leg, • (⟨𝑎 → 𝑏; 𝑎 ↔ 𝑒⟩ ; {¬𝑒𝑒, ¬𝑏𝑒}) – when such tt2l table top with 2 legs, program is placed in the environment an agent tt3l table top with 3 legs, can consume it only if it does not contain two tc complete table, copies of object 𝑒 or one object 𝑏 and one object 𝑒; such a program cannot be transferred into the ts sanded table, environment. The conditions can never be met, tp painted table, the environment always contains environmental 𝑒 } objects. 𝑣𝑒 = pow pow pow pow pow 4n p s-b • (⟨𝑎 → 𝑏; 𝑎 ↔ 𝑒⟩ ; {⟨𝑒 → 𝑎; 𝑒 ↔ 𝑎⟩}) – this program can only be moved if program s-b s-b s-b ⟨𝑒 → 𝑎; 𝑒 ↔ 𝑎⟩ is contained inside the recipient (︁⟨ ⟩ )︁ pow→ tt , 𝑒 ↔ 𝑒 , { pow 𝑒} saw (in its program set if it is an agent, or directly in (︁⟨ ⟩ )︁ the environment if the program is to be moved pow → l , 𝑒 ↔ 𝑒 , { pow 𝑒} wood lathe there) (︁⟨ ⟩ )︁ tt → tth , 𝑒 ↔ 𝑒 , { tt 𝑒} drill We call a transferable program (program; condition) (︁⟨ ⟩ )︁ l → lh , 𝑒 ↔ 𝑒 , { l 𝑒} drill permanent (denoted by the 𝑝 in the subscript) if each time angle grinder (︀⟨︀ ⟩︀ )︀ the program is moved to a different destination, one copy tc → ts , 𝑒 ↔ 𝑒 , { tc 𝑒} of the program remains at the original location. (︁⟨ ⟩ )︁ ts → tp , 𝑝 → 𝑒 , { ts 𝑝} paint spray gun 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 tools: agent, by transferring the program, "picks up" a saw or 𝑃 ={ ⟨ ⟩ uses a wood lathe. 𝑒 ↔ pow , 𝑒 ↔ 𝑒 , take a piece of wood (︁ )︁ import (︁ )︁ ⟨ ⟩ pow 𝑒 − −−−−−−−−−−−−−− ⟩−−−−−−− → pow 𝑒 lh → lh , 𝑒 ↔ s-b , take a screw bolt (︂⟨ )︂ ⟨ ⟩ pow → tt ,𝑒↔𝑒 ,{ pow 𝑒} lh → lc , s-b → 𝑒 , mount the screw bolt ⟨ ⟩ Now the agent can use this program to make the table lc ↔, 𝑒 ↔ 𝑒 , put down complete leg top from piece of wood. ⟨ ⟩ tth → tth , 𝑒 ↔ 4n , take four nuts (︂⟨ ⟩ )︂ ⟨ ⟩ (︁ )︁ pow → tt ,𝑒↔𝑒 ,{ pow 𝑒} (︀ )︀ tth ↔ ttn , 4n → 𝑒 , put nuts on the holes pow 𝑒 −−−−−−−−−−−−−−−−−−−−−−→ tt 𝑒 ⟨ ⟩ 𝑒 ↔ ttn , 𝑒 ↔ lc , take the table top Because of non-determinism the agent can import the and complete leg second transferable program instead of using the first one. ⟨ ⟩ In the next step, the agent can import a new program from ttn ↔ tt1l , lc → 𝑒 , mount the complete leg the environment that allows it to drill holes in the table ⟨ on ⟩ the table top top. In the next step, the agent use imported program tt1l ↔ 𝑒, 𝑒 ↔ 𝑒 , put down the table top and then the agent move the table top with holes into with the environment. ⟩ one leg import ⟨ 𝑒 ↔ tt1l , 𝑒 ↔ lc , take the table top with leg (︀ tt 𝑒 − )︀ −−−−−−−−−−−−− (︀ )︀ ⟩−−−−−− → tt 𝑒 and the second⟩ complete leg (︂⟨ )︂ ⟨ tt → tth ,𝑒↔𝑒 ,{ tt 𝑒} tt1l ↔ tt2l , lc → 𝑒 , mount the second leg (︂⟨ ⟩ )︂ tt → tth ,𝑒↔𝑒 ,{ tt 𝑒} on ⟩ the table top (︀ )︀ (︁ )︁ ⟨ tt 𝑒 −−−−−−−−−−−−−−−−−−−−→ tth 𝑒 tt2l ↔ 𝑒, 𝑒 ↔ 𝑒 , put down the table top ⟨ ⟩ with tth ⟩ two legs (︁ )︁ ↔𝑒,𝑒↔𝑒 ⟨ tth 𝑒 −−−−−−−−−−−→ (𝑒𝑒) 𝑒 ↔ tt2l , 𝑒 ↔ lc , take the table top with 2 legs and the second ⟩ complete leg Now, the agent is prepared for processing another piece of wood or mounting the nuts into the holes in the ⟨ tt2l ↔ tt3l , lc → 𝑒 , mount the third leg table top. The next scheme shows nuts assembly to the on ⟩ the table top ⟨ table top with holes. tt3l ↔ 𝑒, 𝑒 ↔ 𝑒 , put down the table top ⟨ ⟩ with three legs 𝑒↔ tth ,𝑒↔ 4n (︁ )︁ ⟨ ⟩ (𝑒𝑒) −−−−−−−−−−−−−→ tth 4n 𝑒 ↔ tt3l , 𝑒 ↔ lc , take the table top ⟨ ⟩ ⟨ and the third ⟩ complete leg (︁ )︁ tth → ttn , 4n →𝑒 (︀ )︀ tt3l↔ tc , lc → 𝑒 , mount the fourth leg tth 4n −−−−−−−−−−−−−−−−→ ttn 𝑒 on⟩︀the table top ⟨ ⟩ ttn ↔𝑒,𝑒↔𝑒 take the paint ⟨︀ ts → ts , 𝑒 ↔ 𝑝 , (︀ )︀ ttn 𝑒 − −−−−−−−−−−→ (𝑒𝑒) ⟨ ⟩ tp ↔ 𝑒, 𝑒 ↔ 𝑒 , put down the painted table The leg production is similar to the table top produc- } tion. The agent consumes a piece of wood, imports pro- The P colony starts an computation with all supplies gram for leg making using wood lathe and changes the in the environment. Agent contents two environmental piece of wood into the table leg. Then the agent import objects. In this configuration agent can use only one program for hole making with drill and by applying it program. This program allow it to consume one piece of the agent obtain leg with hole. Then agent put the leg to wood. ⟨ ⟩ the environment and consume it together with double 𝑒↔ pow ,𝑒↔𝑒 (︁ )︁ ended screw bolt to assembly screw to hole in the leg. (𝑒𝑒) −−−−−−−−−−−→ pow 𝑒 The agent can put complete leg into environment. The agent himself can’t process a piece of marrow. (︁ )︁ import (︁ )︁ pow 𝑒 − −−−−−−−−−−−−−⟩ −−−−−−−−→ pow 𝑒 There are two programs in the environment that (if the (︂⟨ )︂ pow → l ,𝑒↔𝑒 ,{ pow 𝑒} agent contains a piece of wood) can be transferred to the (︂⟨ ⟩ )︂ ⟨ ⟩ (︁ )︁ pow → l ,𝑒↔𝑒 ,{ pow 𝑒} (︁ )︁ 𝑒↔ tt3l ,𝑒↔ lc (︁ )︁ pow 𝑒 − −−−−−−−−−−−−−−−−−−−−−→ l 𝑒 (𝑒𝑒) −−−−−−−−−−−−−→ tt3l lc import (︁ )︁ (︁ )︁ ⟨ ⟩ tt3l → ttc , lc →𝑒 l 𝑒 − −−−−−−−−−−−− ⟩−−−−−→ l 𝑒 (︁ )︁ (︀ )︀ (︂⟨ l )︂ → lh ,𝑒↔𝑒 ,{ l 𝑒} tt3l lc −−−−−−−−−−−−−−−→ ttc 𝑒 During the computation, the agent can export pro- (︂⟨ ⟩ )︂ (︁ )︁ l → lh ,𝑒↔𝑒 ,{ l 𝑒} (︁ )︁ l 𝑒 −−−−−−−−−−−−−−−−−−→ lh 𝑒 grams that allow the processing of a piece of wood - if ⟨ ⟩ there is a piece of wood in the environment the program (︁ )︁ lh ↔𝑒,𝑒↔𝑒 can be transferred. After processing the last piece of lh 𝑒 −−−−−−−−−−→ (𝑒𝑒) wood, the program remains in the agent’s set of pro- ⟨ ⟩ grams. 𝑒↔ lh ,𝑒↔ s-b (︁ )︁ When the agent contains the complete table, it can (𝑒𝑒) −−−−−−−−−−−−−→ lh s-b import program that allows agent to use angle grinder ⟨ lh → lc , s-b →𝑒 ⟩ and proceed from the complete table to the sanded table. Then the agent can take the paint and import the last (︁ )︁ (︁ )︁ lh s-b −−−−−−−−−−−−−−−→ lc 𝑒 program to spray the table with paint using a paint spray gun. ⟨ ⟩ (︁ )︁ lc ↔𝑒,𝑒↔𝑒 lc 𝑒 −−−−−−−−−−→ (𝑒𝑒) (︀ )︀ import (︀ )︀ tc 𝑒 −−−−−−−−−−−−−⟩−−−−−−→ tc 𝑒 The agent can make the legs and the table tops up to (︂⟨ )︂ tc → ts ,𝑒↔𝑒 ,{ tc 𝑒} a total quantity of five. Only such computations where agents makes one table top and four legs leads to success- (︂⟨ ⟩ )︂ tc → ts ,𝑒↔𝑒 ,{ tc 𝑒} ful end - production of one painted table. (︀ )︀ (︀ )︀ tc 𝑒 −−−−−−−−−−−−−−−−−−−→ ts 𝑒 ⟨ ⟩ )︀ ts → ts ,𝑒↔𝑝 ⟨ ⟩ 𝑒↔ ttn ,𝑒↔ lc (︀ ts 𝑒 −−−−−−−−−−−−→ (𝑒𝑒) (︁ )︁ (𝑒𝑒) −−−−−−−−−−−−−→ ttn lc (︀ )︀ import (︀ )︀ ts 𝑝 − −−−−−−−−−−−−− ⟩−−−−−− → ts 𝑒 ⟨ ⟩ (︁ )︁ ttn → tt1l , lc →𝑒 (︁ )︁ (︂⟨ )︂ ttn lc −−−−−−−−−−−−−−−−→ tt1l 𝑒 ts → tp ,𝑝→𝑒 ,{ ts 𝑒} ⟨ ⟩ (︂⟨ ⟩ )︂ (︁ )︁ tt1l ↔𝑒,𝑒↔𝑒 (︀ )︀ ts → tp ,𝑝→𝑒 ,{ ts 𝑒} (︁ )︁ tt1l 𝑒 −−−−−−−−−−−→ (𝑒𝑒) ts 𝑒 − −−−−−−−−−−−−−−−−−−−→ tp 𝑒 ⟨ ⟩ The last executed program is to put painted table into 𝑒↔ tt1l ,𝑒↔ lc (︁ )︁ environment. (𝑒𝑒) −−−−−−−−−−−−−→ tt1l lc ⟨ ⟩ ⟨ ⟩ (︁ )︁ tp ↔𝑒,𝑒↔𝑒 (︀ )︀ (︁ )︁ tt1l → tt2l , lc →𝑒 (︁ )︁ tp 𝑒 −−−−−−−−−−→ e 𝑒 tt1l lc −−−−−−−−−−−−−−−−→ tt2l 𝑒 ⟨ ⟩ If we add a special object to the environment, which (︁ )︁ tt2l ↔𝑒,𝑒↔𝑒 will be part of the condition for transfer in all transferable tt2l 𝑒 −−−−−−−−−−−→ (𝑒𝑒) programs, the agent can end computation only when it "returns" all transferred programs back to the environ- ⟨ ⟩ ment. 𝑒↔ tt2l ,𝑒↔ lc (︁ )︁ (𝑒𝑒) −−−−−−−−−−−−−→ tt2l lc ⟨ ⟩ 4. 2D P Colonies (︁ )︁ tt2l → tt3l , lc →𝑒 (︁ )︁ tt2l lc −−−−−−−−−−−−−−−−→ tt3l 𝑒 In [10] a new model, called 2D P colony was introduced. ⟨ ⟩ As in the original model, the P colony is of capacity two tt3l ↔𝑒,𝑒↔𝑒 (︁ )︁ and the agents are equipped with sets of the programs tt3l 𝑒 −−−−−−−−−−−→ (𝑒𝑒) 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 pro- The result of the computation is the number of copies gram. The direction of the movement of the agent is of the final object placed in the environment at the end determined by the contents of cells surrounding the cell of the computation. in which the agent is placed. The motion program can The aim of introducing 2D P colonies is not study- contain one motion rule and one evolution rule. ing their computational power but monitoring their be- haviour during the computation. Definition 2. A 2D P colony is a construct Π = (𝐴, 𝑒, 𝐸𝑛𝑣, 𝐵1 , . . . , 𝐵𝑘 , 𝑓 ), 𝑘 ≥ 1, where 4.1. 2D P Colonies with transferable programs • 𝐴 is an alphabet of the colony, its elements are called objects, We can introduce transferable programs into 2D P • 𝑒 ∈ 𝐴 is the basic environmental object of the 2D colonies model. P colony, Aspects of transferable programs composed of evo- • 𝐸𝑛𝑣 is a pair (𝑚 × 𝑛, 𝑤𝐸 ), where 𝑚 × 𝑛, 𝑚, 𝑛 ∈ lutionary and communication rules have already been 𝑁 is the size of the environment and 𝑤𝐸 is the mentioned in the previous section. initial contents of environment, it is a matrix of A transferable motion program can upgrade an size 𝑚 × 𝑛 of multisets of objects over 𝐴 − {𝑒}. agent’s motion capabilities. For example, an agent • 𝐵𝑖 , 1 ≤ 𝑖 ≤ 𝑘, are agents, each agent is a con- that previously could only move in one direction struct 𝐵𝑖 = (𝑜𝑖 , 𝑃𝑖 , [𝑜, 𝑝]) , 0 ≤ 𝑜 ≤ 𝑚, 0 ≤ now has the ability to move left, right, or backwards. 𝑝 ≤ 𝑛, where The agent’s program ⟨⎡ 𝑒 𝑒 𝑒 ⎤ – 𝑜𝑖 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 The transferred program program contains exactly 2 rules, which are in one of the following forms each: ⟨⎡ 𝑒 𝑒 𝑒 ⎤ ⟩ ∗ 𝑎 → 𝑏, called the evolution rule, ⎣ 𝑒 𝑒 𝑒 ⎦ → ⇐; 𝑎 → 𝑎 𝑎, 𝑏 ∈ 𝐴, 𝑒 𝑒 𝑒 ∗ 𝑐 ↔ 𝑑, called the communication rule, If the agent had any restrictions in the original mo- 𝑐, 𝑑 ∈ 𝐴, tion programs under which it could move in a certain ∗ [𝑎𝑞,𝑟 ] → 𝑠, 0 ≤ 𝑞, 𝑟 ≤ 2, 𝑠 ∈ {⇐ direction, these restrictions can be changed. For example, , ⇒, ⇑, ⇓}, called the motion rule, if the agent could only move to the left if there was an • 𝑓 ∈ 𝐴 is the final object of the colony. object 𝐿 on the left, then after importing the program, it will also be able to move to the left if there is an object A configuration of the 2D P colony is given by the state 𝑇 to the left of the agent. The agent’s program 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. The transferred program 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 Similarly, constraints can be imposed on the agent’s different programs. The third part is the execution of the content. The agent may be given "one-time permission" chosen programs. to turn left in the form of object 𝐿, which it will be able A change of the configuration is triggered by the exe- to rewrite 𝐿 to another object while according to the cution of programs and it involves changing the state of agent’s movement rule agent moves left. the environment, contents and placement of the agents. The transferred program A computation is non-deterministic and maximally ⟨⎡ 𝑒 𝑒 𝑒 ⎤ ⟩ parallel. The computation ends by halting when there is ⎣ 𝑒 𝑒 𝑒 ⎦ → ⇐; 𝐿 → 𝑎 no agent with applicable program. 𝑒 𝑒 𝑒 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 [4, 4], which also contains transferable program If agent 𝐵2 reaches cell [4, 4] during the computation, it can import a program whose application can evolve (⟨𝑒 → 𝑠; 𝑒 → 𝑒⟩ , {𝑒𝑒}) . object 𝑠 from the environmental object and thus becomes independent of the presence of object 𝑠 in the environ- The first agent 𝐵1 = (𝑒𝐹, 𝑃1 , [0, 0]) has a set of pro- ment. grams 𝑃1 that include the following programs: Example 3. Imagine a student moving within the school (⟨𝑒 → 𝑒; 𝑒 ↔ 𝑠⟩ , {𝑒𝑒})𝑝 building to acquire the necessary knowledge and pass an ⟨⎡ 𝑒 𝑒 𝑒 ⎤ exam. We can simulate such a situation by using a 2D P ⟩ ⎣ 𝑒 𝑒 𝑒 ⎦ → ⇒; 𝐹 → 𝑠 colony. 𝑒 𝑒 𝑒 ⟨⎡ 𝑒 𝑒 𝑒 ⎤ ⟩ The single cells of the 2D environment represent parts ⎣ 𝑒 𝑒 𝑒 ⎦ → ⇐; 𝐹 → 𝑠 of a school building (or multiple buildings) such as class- rooms, laboratories, libraries, teachers’ offices, etc. The 𝑒 𝑒 𝑒 student’s goal is to obtain a grade in the course (object 𝑀 ⟨⎡ 𝑒 𝑒 𝑒 ⎤ - mark). At the beginning of the computation, agent – stu- ⟩ ⎣ 𝑒 𝑒 𝑒 ⎦ → ⇑; 𝐹 → 𝑠 dent 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 office to the class- The first agent 𝐵2 is defined as (𝑒𝑒, 𝑃2 , [2, 2]). Its set room or lab and back again. If they encounter a student of programs is formed by following programs: 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 different rooms - cells. 𝑒 𝑒 𝑒 We leave it to the esteemed reader to construct partic- ⟨⎡ 𝑒 𝑒 𝑒 ⎤ ⟩ ular programs for student and teacher. ⎣ 𝑒 𝑒 𝑒 ⎦ → ⇓; 𝑠 → 𝑒 𝑒 𝑒 𝑒 5. Conclusion 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 [7] G. Rozenberg, A. Salomaa, Handbook of Formal is the use of environment agents to store shared objects. Languages: Beyonds words, Handbook of For- Thus, objects can be used by all agents that are in a given mal Languages, Springer, 1997. URL: https://books. part of the environment and know how to handle the google.hu/books?id=voLFxNxAHdkC. object (have programs that process the object). Transfer- [8] J. Kelemen, A. Kelemenová, On P colonies, a bio- able programs allow not only to share objects, but also chemically inspired model of computation, in: to share the ability to handle these objects. Proc. of the 6𝑡ℎ International Symposium of Hun- Our goal for the future is to introduce a type of numer- garian Researchers on Computational Intelligence, ical P colony with transferable programs, whose agents Budapest TECH, Hungary, 2005, pp. 40–56. URL: would acquire their abilities by moving around in an en- http://conf.uni-obuda.hu/mtn2005/Kelemen.pdf. vironment that has a specified structure. Agents in such [9] E. Csuhaj-Varjú, J. Kelemen, A. Kelemenová, a P colony would perform search algorithms known, for Gh. Păun, Gy. Vaszil, Computing with cells in en- example, from graph theory. vironment: P colonies, Journal of Multiple-Valued Logic and Soft Computing 12 (2006) 201–215. [10] L. Cienciala, L. Ciencialová, M. Perdek, 2D Acknowledgments P Colonies, in: Proceedings of the 13th International Conference on Membrane Com- This work was supported partially by European Union puting, CMC’12, Springer-Verlag, Berlin, Hei- under European Structural and Investment Funds Opera- delberg, 2012, p. 161–172. URL: https://doi. tional Programme Research, Development and Education org/10.1007/978-3-642-36751-9_12. doi:10.1007/ project Zvýšení kvality vzdělávání na Slezské univerzitě 978-3-642-36751-9_12. 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. References [1] J. Kelemen, A. Kelemenová, Gh. Păun, Preview of P colonies: A biochemically inspired computing model, in: Workshop and Tutorial Proceedings. Ninth International Conference on the Simulation and Synthesis of Living Systems (Alife IX), Boston, Massachusetts, USA, 2004, pp. 82–86. [2] Gh. Păun, G. Rozenberg, A. Salomaa, The Oxford Handbook of Membrane Computing, Oxford Uni- versity Press, Inc., New York, NY, USA, 2010. [3] J. Kelemen, A. Kelemenová, A grammar- theoretic treatment of multiagent systems, Cy- bern. Syst. 23 (1992) 621–633. doi:10.1080/ 01969729208927485. [4] E. Csuhaj-Varjú, J. Kelemen, Gh. Păun, J. Dassow, Grammar Systems: A Grammatical Approach to Distribution and Cooperation, 1st ed., Gordon and Breach Science Publishers, Inc., USA, 1994. [5] A. Kelemenová, P Colonies, in: Gh. Păun, G. Rozen- berg, A. Salomaa (Eds.), The Oxford Handbook of Membrane Computing, 1st. ed., Oxford University Press, Inc., New York, NY, USA, 2010, pp. 584–593. [6] L. Ciencialová, E. Csuhaj-Varjú, L. Cienciala, P. Sosík, P colonies, Journal of Membrane Computing 1 (2019) 178–197. URL: https://doi. org/10.1007/s41965-019-00019-w. doi:10.1007/ s41965-019-00019-w.