Working with Positive Integers in P Colony rw-Automata

Abstract

We introduce new variant of P colonies that we call P colony rw-automaton - a theoretical model from the membrane computing model family. Its inspiration comes from nature and the structure and functioning of living organisms. The model is formed from agents - a collection of objects embedded in a membrane, equipped with programs to manipulate objects. The agents share objects placed on the tape and in the environment. In this paper, we focus on natural number encoding and sorting of positive natural numbers by an algorithm similar to Bead sort executed by the P colony rw-automata.

Keywords

• eol>membrane computing
• P Colony rw-automata
• natural number representation
• sorting
• Bead sort

1. Introduction

transition, within the P colony. A finite sequence of consecutive configuration changes, initiated from the initial P colony, introduced in [ 1 ], is a theoretical computing configuration, constitutes a computation. The output of model inspired by structure and behavior of simple one- this computation is determined by counting the numcell organisms living in a shared environment. The P ber of copies of a specific distinguished object, known colony is formed from basic units agents equipped with as the "final object," present in the environment at the programs. The crucial role play the environment, it can conclusion of the process. store products of agents functioning and through the The environment serves a dual purpose: functioning as environment the agents can send "messages" to each a communication channel for the agents and also serving other. The functioning of agents is based on objects. as a storage medium for the objects. Its strategic role lies

Within each agent, there exists a finite multiset of ob- in synchronizing the collaborative eforts of the agents jects. These objects undergo processing by a finite set throughout the entire computation process. of associated programs unique to each agent. The num- The programs in the P colony comprise three distinct ber of objects residing in each agent remains constant types of rules. The first type, known as "evolution rules", throughout the operation of the agent community, and takes the form of → , indicating that an object this fixed quantity is referred to as the "capacity" of the within the agent is rewritten or evolved into object . P colony. The second type, referred to as "communication rules",

The agents collectively share an environment, which follows the pattern ↔ . Upon executing a commuis represented by another multiset of objects. Among nication rule, object inside the agent swaps positions these objects, one particular type is identified as the "en- with object in the environment. As a result, object is vironmental object." This type is assumed to exist in an now located inside the agent, and object resides in the infinitely countable number of copies within the envi- environment. ronment. (It should be noted that in the literature, one The third type of rules, called "checking rules," are may also encounter instances where the environmental derived from two rules of either evolution or communisymbol appears in an arbitrarily large number of copies cation types. When a checking rule 1/2 is executed, in the environment). rule 1 takes precedence over rule 2. This means that

By utilizing their respective programs, the agents can the agent first checks if rule 1 is applicable; if so, it must alter the objects available to them and exchange some of be used. In case rule 1 is not applicable, the agent uses their objects with those found in the environment. These rule 2. coordinated actions lead to a configuration change, or In P colony rw-automaton we distinguish between communication rules that work with objects in a multiset (called non-tape rules) and communication rules that work with objects on tape (called tape rules).

We will present the possibilities of this new variant of P colonies by examples of working with natural numbers (conversions to diferent number systems) and sorting a given number of natural numbers.

The structure of the paper is as follows: after an introductory section, we introduce the basic concepts related ITAT 2023: Information Technologies – Applications and Theory, September 22–26, 2023, Vysoké Tatry, Slovakia * Corresponding author. † These authors contributed equally. " [e-mail] (L. Ciencialová); [e-mail] (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 CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) • , 1 ≤ ≤ , are agents, where each agent = (, ) is defined as follows: – is a multiset over consisting of objects, the initial state (or the initial content) of the agent; – = {,1, . . . , , } is a finite set of programs, where each program consists of rules, which are in one of the following forms each: (1) → , , ∈ , called an evolution rule; (2) ↔ , , ∈ , called a communication rule; (3) 1/2, called a checking rule; 1, 2 are evolution rules or communication rules. to the original P colony model, which we then develop into a new variant called P colony rw-automaton. In the third section we give examples of the P colony rwautomaton, which implements the conversion of a natural number given in the decimal system (on a tape) into the unary system (the number of certain objects in the environment). In the next example we will discuss the opposite conversion, i.e. the conversion of a number in the unary representation to a number in the decimal system, which will be placed on the tape at the end of the calculation. Last we will give how to construct a P colony rw-automaton that is able to sort a given number of natural numbers. These numbers are placed on the tape in such a way that the beginning and end of their enumeration is marked, and they are also separated from each other by a special object. At the end of the calculation, the tape will list the same numbers ordered by size from largest to smallest.

The agent’s activity is governed by its programs, en

abling the agent to modify its state and/or the state of the environment.

The environment consists of a finite number (including zero) of copies of non-environmental objects and a 2. Preliminaries and Basic Notions countably infinite number of copies of the environmental object, denoted as .

Throughout the paper we assume the reader to be famil- When an agent executes a program, each object within iar with the basics of the formal language theory and the agent is afected. Depending on the rules within the membrane computing [ 2, 3 ]. program, the execution may also impact the environment.

For an alphabet Σ , the set of all words over Σ (includ- This interaction between agents and the environment is ing the empty word, ), is denoted by Σ * . We denote pivotal to the operation of the P colony. the length of a word ∈ Σ * by || and the number The functioning of the P colony begins from its initial of occurrences of the symbol ∈ Σ in by ||. configuration or initial state. The initial configuration is

A multiset of objects is a pair = (, ), where represented as an ( + 1)-tuple of multisets of objects is an arbitrary (not necessarily finite) set of objects and present in the P colony at the start of computation. These is a mapping : → ; assigns to each object in multisets are denoted as for 1 ≤ ≤ and for the its multiplicity in . Any multiset of objects with the environment. set of objects = {1, . . . } can be represented as In each step of the computation, both the environa string over alphabet with || = (); 1 ≤ ≤ ment and agent’s states undergo changes. In the "maxi. Obviously, all words obtained from by permuting mally parallel" derivation mode, all agents that can emthe letters can also represent the same multiset , and ploy any of their programs do so simultaneously (non represents the empty multiset. deterministically chosen). Conversely, in the "sequential" derivation mode, only one agent at a time is allowed to use one of its programs (non-deterministically cho2.1. P Colony sen). If an agent has multiple applicable programs, it In the following we describe the concept of a P Colony. non-deterministically selects one. Consider original definition of P colony introduced in A sequence of transitions constitutes a "computation." [ 1 ]. A computation becomes "halting" when it reaches a conifguration where no further programs can be applied. The Definition 1. A P colony of capacity , ≥ 1, is a con- result of a halting computation is determined by the numstruct ber of copies of a specific object, denoted as , present Π = ( , , , , 1, . . . , ), where in the environment during the halting configuration.

Due to the non-determinism in program selection, mul• is an alphabet, its elements are called objects; tiple computations can be derived from the initial con• ∈ is the basic (or environmental) object of the figuration. Thus, a P colony is associated with a set of colony; numbers, denoted as (Π) , which are computed through • ∈ is the final object of the colony; all possible halting computations of the given P colony. • is a finite multiset over − { }, called the

initial state (or initial content) of the environment; 2.2. P Colony rw-Automaton rules and communication (non-tape) rules, respectively.

In P colony([ 1 ]), the agents are placed in the environment – multiset of objects. One special kind of objects is called The computation starts in the initial configuration environmental and it is placed in the environment in ( , 1, . . . , , 0), i.e., when the environment and all suficient number of copies. In addition to the multiset agents are in initial state and the input string 0 is on the of objects, the P colony rw-automaton environment (like input tape. in P colony automaton [ 4 ]) contains a tape on which the Let us look at the tape in more detail. The tape is poobjects are placed in sequence one by one. We refer to tentially infinite on both sides. Since agents need another them as a string on the tape, and we call a part of the object to insert objects onto the tape, they replace object sequence of objects a substring. on the tape by the one inside the agent - they use the

As in the case of standard P colonies, agents of the tape communication rules - the tape cannot be empty. P colony rw-automaton contain objects, each being an We place environmental objects on it. If we place the element of a finite alphabet. With every agent, a set string on the tape, then the tape contains * * . The of programs is associated. To work with tape, agents string itself can contain environmental objects. When need to have rules in their programs that they can read working with tape, writing configuration or giving outand write to tape. Similar rules have been introduced put we omit environment objects to the left of the first for PCol Automaton in [ 5 ] and in generalized P colony object diferent from and environment objects to the automata[ 4, 6 ]. However, the function of the tape rules right of the last occurrence of a symbol diferent from . was diferent. The agents did not directly interfere with For a configuration ( , 1, . . . , , ), where is a the objects on the tape, but merely followed the objects string placed on the tape, the sets of applicable programs, from the part of the tape they were currently reading. , can be constructed in such a way that: The agent must The tape rules we use here for the P colony rw-automaton use all the rules in the program. Tape rules are used to directly modify objects on the tape, similar to the model an arbitrary object of the required type on the tape if one named APcol system([ 7 ]). In this model, programs are an rule is tape rule and the other one non tape. In the case tohrednertehderpeaiisrsanoferxuclheasn. gIfetohfeosbejaercetscboemtwmeuennicthaetiotanperualnesd, of program ⟨ ↔ ; ↔ ⟩ , a two consequent objects the agent. When a program contains two communication and in this order must be on the tape. They are replaced rules, it is the order of the rules that determines the order by objects and , respectively. If the program is of the of two consecutive objects on the tape on which the form ⟨ ↔ ; ↔ ⟩ , then a substring of the tape is agent will apply the program. For more details about find and it is replaced by string . definitions, features and computational power of APCol From the set of applicable programs the programs systems see [ 7, 8, 9 ] and details about PCol automata can to be executed are selected. These programs form a set be found in [ 5, 10 ]. for which the following conditions must be satisfied: (1) Each agent has at most one program in . (2) One Definition 2. A P colony rw-automaton of capacity 2 object in the environment or on the tape is afected by at and with agents, ≥ 1, is a construct most one agent, with at most one rule. (3) If we add any Π = ( , , , (1, 1), . . . , (, )) where program from to , the previous conditions cannot be • is an alphabet, the alphabet of the P colony satisfied.

rw-automaton, its elements are called objects; The automaton passes from one configuration to an• ∈ is the environmental object of the P colony other by using all programs from the set of selected appliautomaton; ∈ ( − { })* is a string represent- cable programs. Such transitions between configurations ing the multiset of objects diferent from , called form a computation. Since the set can be selected from the initial state of the environment ; the set of all applicable programs in multiple ways, the P • (, ), 1 ≤ ≤ , is the -th agent; where colony rw-automaton can pass from one configuration to multiple diferent configurations, resulting in multiple – is a multiset over , || = 2, the initial computations starting from the initial configuration.

state (contents) of the agent, The computation by a P colony rw-automaton may – is a set of programs, where every pro- end by halting, when there is no applicable program in gram is a pair rules, each of them is one of the last configuration. the following types: P colony rw-automaton can work in the accepting, generating or computing mode. In accepting mode, the P colony rw-automaton starts computation with the input on the tape, and if it stops, the input is accepted. When the P colony rw-automaton is working in generating ∗ tape rules of the form ↔ , called

communication tape rules; or ∗ non-tape rules of the form → , or ↔ , called rewriting (non-tape) 1. 2.

< → ; → > < ↔ #; ↔ >

0 ≤ ≤ 9 3. < ↔ #; ↔ $ > 4. < # → ; $ → >

Program 4. is processed only if there is no number in the input (there is no digit between symbols # and $) 5. < # → 1; ↔ > 0 ≤ ≤ 9 6. < 1 → 1; → 1 > 7. < 1 → 1; 1 ↔ > 8. < 1 → ; ↔ 1 >

Symbol 1 placed in the environment means that Module 1 finished its work.

9. < → ; 1 → > mode, it starts with only objects on the tape and the result of the computation can be found on the tape after the computation has halted. In computing mode, the input is transformed to an output, and the output is valid only when the computation stops.

3. Natural number representation

0 ≤ ≤ 9 1 ≤ ≤ 9 1. < ↔ ; ↔ / ↔ > 2. < → 2; → > 3. < 2 ↔ ; → > 4. < → ; → > 5. < → ; ↔ > 6. < → ; ↔ / ↔ >

After all objects are replaced by the second agent sends object 2 to the environment and this is message for the Controller to start pass object 1 to Module 1.

After Controller reads object $ from the tape it stops working without passing any object to the environment so all the agents have no applicable program. P colony rwautomaton with four agents divided into three modules reads decimal number from the tape and after computation halts there are the corresponding number of is placed in the environment.

Now we focus on the reverse transformation - from unary representation of number to decimal number. The unary representation of the number is stored in the environment as the number of copies of object . The result is decimal number stored on the tape at the end of computation.

The idea is to use one agent consuming objects . The agent in initial state 2 uses the second object inside it as counter. If there is no it generate object as message for the second agent to write corresponding digit onto tape and the object message for the third agent that can exchange all by . The third agent generate object to start work of the first agent again. If the first agent consumes ten s it generates one object and continue consuming .

The programs of the first agent are as follows: 1. < 2 → 0; ↔ / ↔ > 2. < → ; → ′ > 0 ≤ ≤ 9 3. < ↔ ; ′ → > 0 ≤ ≤ 9 4. < ↔ ; → > 5. < → ( + 1)′; → > 6. < ′ → ; ↔ / ↔ > 7. < 10 → 10′′; → > 8. < 10′′ → 0′; ↔ > 9. < ↔ 2; → >

The second agent started when some , 0 ≤ ≤ 9, appears in the environment. The agent consumes it and exchange # by #. The decimal number is written from the right to the left.

1. < ↔ ; → ′ > 0 ≤ ≤ 9 2. < → #; ′ → > 0 ≤ ≤ 9

< # ↔ ; ↔ # > 3. 4. < # → ; → >

The third agent has the same programs as the agent from Module 2 (programs C1.– C6.).

The P colony rw-automaton with three agents starts the computation in initial configuration with # on the tape and copies of in the environment. The first agent contain 2, the second and third agents contains each. When computation halts the resulting string can be found on the tape in the form # where is decimal representation of the number of s in the environment at the beginning of computation. If the input is given on the tape we need one more agent to "copy" objects from the tape and after reaching the end of the string it can generate object 2. In this case the first agent initial state is .

Both P colony rw-automata can easily be adjusted to perform transformation to any number system using another limits instead of 8, 9 and 10. For example for hexadecimal system 14, 15 and 16 are used in programs with instead of upper limit.

4. Sorting natural numbers

In this section, we focus on construction of such P colony

rw-automaton that finds unsorted positive integers (in decimal number system) on the tape in the form #1 2 . . . $. The input variable for construction of P colony rw-automaton is .

The idea is to transform given decimal numbers to unary representation (we need diferent -objects, we can use indices 1 to ), sort them and write sorted numbers onto tape in a form similar to input string.

We can use Controller, Module 1 and Module 2 from previous section to read the tape and place copies into the environment. Controller has to call Modules with proper index (corresponding to the order of the number stored on the tape). The Modules generate s with the same index or we can use pairs Modules each pair activated by another index.

The idea of sorting is a little bit similar to Bead sort. We run + 1 agents in parallel - agents consuming s and the last one is generating results. When there is to be consumed by agent , no object is placed to the environment by agent . When there is no in the environment agent place object to the environment. this object is consumed by agent + 1. This phase can be called consuming.

Until now, the agent + 1 generated object at each step when agents consumed their objects. The moment appears in the environment the agent increments the index of the generated object ((+1)). In the case of multiple objects (identical numbers in a sequence of numbers) the agent + 1 increases the index until it has consumed all the objects of . Only then can the other agents continue their work. We can implement this part in this way that after agent has consumed object it applies programs with rewriting rules in the next steps, and thus wait − 1 steps to allow agent + 1 to process all possible objects from the environment.

After this phase there is no object , 1 ≤ ≤ , in the environment. There are some object in the

This work is supported by the Silesian University in Opava under the Student Funding Plan,project SGS/11/2023.

environment where ∈ 1, . . . . For example if the input number by given number (in our case 10). sequence of numbers is 3, 5, 4, 3, 5, then after consuming phase the environment contains objects 11134.

In the next phase, the objects are processed, copied 6. Acknowledgments and transformed into the decimal system with writing to tape. It means that every object 1 is replaces by pair 12, then all object 1 are transformed to decimal number and this number is written to the tape. Note that the output is written from right to left and that the number of objects 1 corresponds to the smallest number References in the input sequence. The same transformation is done by all type of objects.

We list here some programs that belong to the agents consuming , and the agent + 1.

The set of programs of agent , 1 ≤ ≤ contains programs: 1. < → ; ↔ / ↔ > 2. < → 0; → > 3. < → (+1); → > 0 ≤ ≤ 2 − 2 4. < (2− 1) → ; → > 5. < ↔ ; → >

The agent +1 has following programs in its programs set (1 ≤ ≤ − 1; 2 ≤ ≤ 2 − 2; 0 ≤ ≤ 2 − 2): 1. < → ′; → > 2. < ′ → ′′; → > 3. < ′′ → 0; ↔ / ↔ > 4. < 0 → 1; → 1 > 4. < 1 → 2; 1 ↔ > 4. < () → (+1); → > 5. < (2− 2) → ; → > 6. < 0 → ( + 1)′1; → > 7. < ′ → ( + 1)′+1; → > 8. < ′ → ()′+1; ↔ / ↔ > 9. < (′2− 2) → ; → > 10. < (′2− 2) → ; → > 10. < (2− 2) → ; → >

The number of steps that P colony rw-automaton executes during the consuming phase depends on the number of given numbers () and the maximum of these numbers () and equals to (2 + 2) · .

5. Conclusion

In this research paper we introduce a new variant of

P colony – P colony rw-automaton that combines features of APcol system, generalized P colony automaton and PCol automaton. It uses tape and non-tape rules to work with objects on the tape and in the environment. The functioning of P colony rw-automaton is shown on work with natural numbers – transformation between representation of the number in unary and decimal number systems and sorting natural numbers. Within these examples of use P colony rw-automaton we show how to multiply and divide unary representation of natural

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] 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 University Press, Inc., New York, NY, USA, 2010 .

[4] K. Kántor , G. Vaszil, Generalized P Colony Automata 19 ( 2014 ) 145 - 156 .

[5] L. Cienciala , L. Ciencialová , E. Csuhaj-Varjú , Gy. Vaszil, PCol automata: recognizing strings with P colonies , in: M. Ángel del Amor, Gh . Păun, I. Pérez Hurtado de Mendoza, A. Riscos Núnez (Eds.), Eighth brainstorming week on membrane computing . Sevilla , 2010 . ( RGNC Report 01 / 2010 .), Fénix Editora , Sevilla, 2010 , pp. 65 - 76 .

[6] K. Kántor , G. Vaszil, On the classes of languages characterized by generalized P colony automata , Theoretical Computer Science 724 ( 2018 ) 35 - 44 . URL: https://www.sciencedirect.com/ science/article/pii/S0304397517309027. doi:https: //doi.org/10.1016/j.tcs. 2017 . 12 .011.

[7] L. Cienciala , L. Ciencialová , E. Csuhaj-Varjú , P colonies processing strings , Fundamenta Informaticae 134 ( 2014 ) 51 - 65 . doi: 10 .3233/ FI-2014-1090.

[8] L. Ciencialová , E. Csuhaj-Varjú , G. Vaszil , L. Cienciala, APCol systems with verifier agents , in: T. Hinze, G. Rozenberg , A. Salomaa , C. Zandron (Eds.), Membrane Computing - 19th International Conference, CMC 2018 , Dresden, Germany, September 4- 7 , 2018 , Revised Selected Papers, volume 11399 of Lecture Notes in Computer Science, Springer, 2018 , pp. 95 - 107 . URL: https://doi. org/10.1007/978-3- 030 -12797- 8 _8. doi: 10 .1007/ 978-3- 030 -12797-8\_8.

[9] L. Ciencialová , L. Cienciala , Two notes on APCol systems, Theor. Comput. Sci . 805 ( 2020 ) 161 -