In this paper we continue our investigations in APCol systems (Automaton-like P colonies), variants of P colonies where the environment of the agents is given by a string and the functioning of the system resembles to the functioning of standard finite automaton. We introduce a new variant of APcol systems called extended APcol systems - agents capacity is not limited to two objects. We deal with the concept of agent creation in these systems and possibility of generation of strings as commands for turtle graphics.
Automaton-like P colonies (APCol systems, for short),
introduced in [
An APCol system consists of a finite number of agents and their joint shared environment. The agents are formed from a finite number of objects and their functioning is based on programs consisting of rules. These rules are of two types: they may change the objects of the agents and they can be used for interacting with the joint shared environment of the agents. While in the case of standard P colonies the environment is a multiset of objects, in case of APCol systems it is represented by a string. The number of objects inside each agent is set by definition and it is usually a very small number: 1, 2 or 3. The string representing the environment is processed by the agents and it is used as a communication channel for the agents as well, since through the string, the agents are able to affect the behaviour of another agent.
Agents are also equipped with agent creation programs. They are applicable when a special object appears inside the agent. An agent with the special object can make one copy of itself containing objects specified by the program.
The computation in APCol systems starts with an input string, representing the environment, and with each agent in its initial state.
Every computational step is done in a maximally parallel way which means that a set of the active agents per
Copyright ©2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). forming their programs is maximal - the joint action of the agents is maximally parallel if no more active agent can be added to the synchronously acting agents. An agent is active if it is able to execute at least one of its programs.
The computation ends if there are no more applicable programs in the system.
For more detailed information on APCol systems we
refer to [
In computer graphics, turtle graphics are vector graphics using a relative cursor - the “turtle” to draw curves. Commands for turtle can be formed into string and hence we can speak about a turtle representation of string. A state of the turtle is defined as a triplet (x; y; a), where the Cartesian coordinates (x; y) represent the turtle’s position, and the angle a, called the heading, is interpreted as the direction in which the turtle is facing. Given the step size d and the angle increment d , the turtle can respond to commands represented by the following symbols: F Move forward a step of length d. The state of the turtle changes to (x0; y0; a), where x0 = x + d cos a and y0 = y + d sin a. A line segment between points (x; y) and (x0; y0) is drawn. f Move forward a step of length d without drawing a line. + Turn left by angle d . The next state of the turtle is (x; y; a + d ). The positive orientation of angles is counter-clockwise.
Turn right by angle d . The next state of the turtle is (x; y; a d ).
Given a string s, the initial state of the turtle (x0; y0; a0)
and fixed parameters d and d , the turtle interpretation of s
is the curve (set of lines) drawn by the turtle in response to
the string s. Turtle graphics is used for example to interpret
strings generated by L-systems (more details reader can
find in [
In this paper we deal with APcol systems with agent
creation programs generating strings that can be interpreted
in turtle graphics. We construct APcol system generating
string representation of two space-filling curves Hilbert
curve and Peano curve. In [
Preliminaries and Basic Notions
Throughout the paper we assume the reader to be familiar
with the basics of the formal language theory and
membrane computing [
For an alphabet S, the set of all words over S (including the empty word, e), is denoted by S . We denote the length of a word w 2 S by jwj and the number of occurrences of the symbol a 2 S in w by jwja.
A multiset of objects M is a pair M = (O; f ), where O is an arbitrary (not necessarily finite) set of objects and f is a mapping f : O ! N; f assigns to each object in O its multiplicity in M. Any multiset of objects M with the set of objects O = fx1; : : : xng can be represented as a string w over alphabet O with jwjxi = f (xi); 1 i n. Obviously, all words obtained from w by permuting the letters can also represent the same multiset M, and e represents the empty multiset. 2.1
APCol system is a kind of P colony. It is formed from agents with capacity 2 processing the string. They act according to programs as it is usual in P colonies. Each program is formed from two rules of two types. The first type called rewriting is of the form a ! b and by execution of this rule, the object a inside the agent is rewritten to the object b. The second type of rules is called communication. The communication rules are of the form c $ d and by use of them, the agent replaces the symbol d in the string by object c initially placed inside the agent. If c = e (e $ d) it means that agent erases symbol d from the string. If d = e (c $ e) it means that agent inserts symbol c to the string in a place which is determined by use of another communication rule in the same program or if there is no other communication rule in the program c is placed in random position.
Let us make a few comments about the application of the programs.
1. Agent can act in only one place in the string in one step of computation. 2. ha $ b; c $ ei hc $ e; a $ bi ) ) b ! ac in the string, b ! ca in the string, ha ! b; c $ ei ) e ! c in the string, insert c anywhere to the string, and rewrite a to b inside agent ha ! b; e $ di ) d ! e in the string, delete one d from the string, and rewrite a to b inside agent If an agent contains a special object @, the agent makes a copy of itself. This action is done by executing a program formed from two rewriting rules. Let a@ be a contents of agent A1 with program p1 = h@ ! b; a ! ci. After execution of the program p1 there is one new child-agent in the APCol system with the same label and the same set of programs as the parent-agent A1 has. The contents of the parent-agent after the execution of the program is bc while the contents of the child-agent is ba.
If the parent-agent has a program p2 = ha ! c; @ ! bi, then after the execution of the program p2 the contents of parent-agent after the execution of the program is bc and the contents of the child-agent is bc, too.
The order of rules determines whether the rewriting rule without @ is used before or after the creation of the childagent.
An extended APcol system is APcol system having capacity k 1 given by definition. The increase of the capacity results in an elongation of the context for the application of programs with communication rules. In programs with agent creation rules, the increased capacity affects the content of agents - the rules listed before the agent creation rule are executed before the creation of a new agent, and the rules listed after the agent creation rule are executed only on the parent agent.
We introduce new type of rule, object occurrence conditional rule. The rule (rewritting, communication) is enriched by the prefix “oj” and it means that the rule can be executed only if object o is present in the environmental string in current configuration under the assumption that the rule itself is applicable. Prefix “ej” means that rule is applicable if rule without prefix is applicable too ( it adds no applicability condition). We also define prefix “:oj” and it means that the rule can be executed only if object o is not present in the environmental string in current configuration under the assumption that the rule itself is applicable.
Definition 1. An extended APCol system (eAPcol system for short) with capacity k 1 with agent creation is a construct
P = (O; e; @; A1; : : : ; An); where • O is an alphabet, its elements are called the objects; • e 2 O, called the basic object; • Ai; 1 i n, are agents. Each agent is a triplet Ai = (wi; Pi; Fi), where – wi is a multiset over O, describing the initial state (contents) of the agent, jwij = k, – Pi = pi;1; : : : ; pi;ki is a finite set of programs associated with the agent, where each program is a pair of rules. Each rule is in one of the following forms: * a ! b, where a; b 2 O, called an rewriting
rule, * c $ d, where c; d 2 O, called a communication rule; If @ appears on the left side of the rule in the program, all rules of this program must be rewriting; Prefix “oj” can be add to rule (not with @ on the left side) and it adds condition for applicability of the program - object o 2 O must be present in the environmental string. Prefix “:oj” can be add to rule (not with @ on the left side) and it means that program is applicable if object o 2 O is not present in the environmental string. – Fi O is a finite set of final states (contents) of agent Ai.
When an agent obtains the object @ by the execution of a rewriting or a communication rule in the program, the agent must create a new agent in the next step of the computation in the way described within the above definition.
The computation starts in the initial configuration where all agents contain their initial multiset of objects and there is an input string over the alphabet T on the eAPCol system. Consequently, an initial configuration of the eAPCol system is an (n + 1)-tuple c = (w; w1; : : : ; wn) where w is the initial state of the environment and the other n components are multisets of objects, given in the form of strings, the initial states of the agents.
A configuration of an eAPCol system P is given by (w; w1; : : : ; wnl ), where jwij = k; 1 i n, wi represents all the objects inside the agent labelled Ai and w 2 (O feg) is the string to be processed.
At each step of the computation every agent attempts to find one of its programs to use. If the number of applicable programs is higher than one, then the agent nondeterministically chooses one of them. At one step of computation, the maximal possible number of agents have to be active, i.e., have to perform a program.
By executing programs, the eAPCol system passes from one configuration to another configuration. A sequence of configurations started from the initial configuration is called a computation.
The computation halts when no agent has an applicable program. 3
Space-Filling Curves generation by eAPcol Systems In this paper, we focus on the generation of control strings for generating space-filling curves using turtle graphics. We concentrated on three curves - Hilbert, Moore and Peano. All three curves are fractal-like. A new iteration of the curve is formed according to a given rule from the previous iteration. This increases the area filled by the curve.
Various mechanisms are used to generate iterations of these curves (or control strings for turtle graphics), for example, parallel grammars or L-systems.
There are several techniques for generating these strings by eAPcol systems. We can use a sequential approach and follow the rules of parallel grammars to rewrite all occurrences of non-terminals one by one, so that the agent " moves" the object-tag that separates the processed part of the string from the unprocessed part as it rewrites nonterminals to strings.
Alternatively, we can use a parallel approach (as in
Lsystems [
In this paper, we use both approaches. We use the parallel approach to generate the string describing the curve and the transcoding of the result into the turtle graphics language is done sequentially. 3.1
In 1891 Hilbert introduced the Hilbert space-filling curve
in [
Hn+1 = g(Hn)uHnrHndj(Hn) where g; j are homomorphisms on alphabet given by: g(u) = r; g(d) = l; g(l) = d; g(r) = u – symmetry w.r.t. Oy and rotation right 90 degrees; j(u) = l; j(d) = r; j(l) = u; j(r) = d – symmetry w.r.t. Oy and rotation left 90 degrees.
The first four approximations are shown in Figure 1.
Hilbert words can be generated by context-free rules that are applied parallelly to string formed from terminals and non-terminals. To generate Hilbert words we use rewriting context-free (CF) rules over non-terminal alphabet fN; L; R;U g and terminals from fu; d; l; rg. The CF rules are:
The starting string is N. In the last step of generation of Hilbert word we use another set of rules that is formed from e-rules and all non-terminals are erased from word. Another approach is to count with terminals only in each generated word. Hilbert word H1 is obtained by execution of the first rule to starting string
The second Hilbert word, H2 is generated from N by following derivation:
N ) ) )
ruluurdrurddldr
For the turtle to draw the first approximation of the Hilbert curve, the command string is F F F. The command string for second approximation of Hilbert curve is F + F + F FF F F + F + F F FF F + F + F.
To generate Hilbert curve we construct eAPcol system with capacity three and with agent creation formed from two kind of agents.
1. The input of the system is a string s0 = an# corresponding to the number of iterations concatenated with a special symbol labelling the end of input. The output of system is command string for Turtle Graphics to generate n-th approximation of Hilbert curve concatenated with symbol #2. 2. The first agent A1 removes one occurrence of object a after all non-terminals are deleted from a string of computation. 3. The second agent A2 will generates approximations of Hilbert word in two phases.
In the first phase the agent generates symbols corresponding to the direction of movement of turtle (u; d; r; l for direction up, down, right and left) with objects called non-terminals according to CF rules. In the second phase, the agent makes a copy of itself twice. It means that in three steps the number of agents labelled by A2 rises four times (the reason is the parallel simulation of the execution of the rules listed below). 4. The last phase of computation is to “code” directions u; d; l; r into turtle language.
Now, we describe the function of the constructed system in more detail, present the programs of the agents, and illustrate the function of the system using the example of generating a command string for the first approximation of the Hilbert curve.
Agent A1 is equipped by the following programs for first three phases of computation:
A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 < #je ! e; e ! e; e ! b >; < e ! e; e ! e; b ! c >; < :Nje ! w1; e ! e; c ! e >; < :Ljw1 ! w2; e ! e; e ! e >; < :Rjw2 ! w3; e ! e; e ! e >; < :U jw3 ! w4; e ! e; e ! e >; < ajw4 ! 0; e ! g; e ! e >; < 0 ! 1; g $ a; e ! e >; < :ajw4 ! 00; e ! f ; e ! e >; < 00 ! 00; f $ #1; e ! e >; < a ! e; 1 ! 2 ; e $ g >; < g ! e; 2 ! 3 ; e ! e >; < e ! e; i ! i+1 ; e ! e >; 3 < 15 ! e; e ! e; e ! c > i 14
The second agent in the first two steps generates the starting word N. The agent places object N next to object #. The communication rule is equipped with condition a :, it means that agent can put N into string only if a is present in the sting. This is initialization phase for generation of Hilbert word.
B1 B2 < e ! #1; e ! N; e ! e >; < #1 $ #; ajN $ e; e ! e >
In our example, the initial configuration of the system is (a#; eeeA1 ; eeeA2 ). The first phase of computation is shown in the Table 1. In rows, there are configurations of the system and sets of applicable programs. If there are more than one applicable program associated with an agent, the executed program is indicated by bold.
Configuration Env. A1 A2 a# eee eee a# eeb #1Ne a#1N eec #ee
Applicable programs A1 A2 A1 B1 A2 B2
B3
In the next phase, the agent A2 replaces N by string LuNrNdR in accordance to the first CF rule. First it generates object #X , where X is non-terminal object. This program in non-deterministically chosen. If there is no such non-terminal present in the string (before this step there was no such non-terminal or the number of occurrences of non-terminal X was less than the number of agents that generated object #X ), the agent can rewrite object #X into # in the next step. It is done in fourteen steps, because agent uses program with two rewriting rules, then another one with two communication rules to generate one object of the right side of rule and one object marking the point where to insert new objects. We note that all CF rules are of the same length and all the agents are working simultaneously so when there are more agents with label A2 they can insert object in different parts of string. But the agents can consume object marker (for example #N2 - marker object for insertion of second object of CF rule with N on the left-hand side of the rule) that corresponds only to currently performed CF rule. Let X 2 fN; L; R;U g and X ! x1x2x3x4x5x6x7 is CF rule.
We demonstrate the application of the programs by continuing the example: In Table 2, we show how the computation is done when agent A2 chooses program associated with non-terminal that is not present in the string (or nonterminal is used by another copy of the agent).
Configuration Env. A1 a#1N eec a#1N eec a#1N eec
A2 #ee #Lee #ee
A1
Applicable programs
A2 B3 : <#!#L;e!e;e!e> B5 : <:Lj#L!#;e!e;e!e>
B3
In Table 3 the computation with right choice of program is shown.
After insertion of all the objects from the right-hand side of the CF rule, the agent A2 is creating new agents in two steps using programs
After this phase in the first iteration the environmental string is in the form an 1#1LuNrNdR and there are four agents labelled A2 in the eAPcol system.
In Table 5, the creation of new agents labelled A2 is shown.
When agent A1 deletes all occurrences of object a from the environmental string, f appears in the environment and agents labelled A2 delete all non-terminals from the string.
B16 B17 < f jx1 ! f ; #X1 ! e; X1 ! X1 >; < f ! f ; e $ #X ; X1 ! f >;
If the environmental string was #1LuNrNdR before this phase of computation, four agents deleted non-terminals from the string and after this phase the string is f urd.
In final phase the agent A1 rewrite objects fu; d; l; rg to symbols fF; +; g. The coding depends on two consecutive objects, for example if ru is substring of the environmental string u is replaced by +F because to draw line in direction up after line in direction right turtle must turn 90 degrees left and draw a line.
To draw Hilbert curve by turtle we have to set two parameters - the step size and the angle increment - and initial state of the turtle. For code generation it is necessary to set the angle increment d = 90 and turtle orientation to up (a = 90 ). Because of angle increment the turtle can be oriented in four directions (up, down, right, left). Boxed symbols u ; d ; r ; l can represent current turtle orientation.
There are following programs in a set of programs of agent A1: A15 A16 A17 A18 A19 A20 A21 A22 A23 A24 A25 A26 A27 A28 A29 A30 A31 A32 A33 < 00 ! u ; #1 ! #2; e ! e >; to move in the same direction as turtle is facing x 2 fu; d; r; lg < x ! x ; #2 $ f ; e $ x >; < x ! x ; f ! f ; x ! F >; < x ! x ; F $ #2; f $ e >; to rotate and move cc(u) = r; cc(r) = d; cc(d) = l; cc(l) = u; p = cc(x) < x ! x ; #2 $ f ; e $ p >; < x ! p ; f ! f 0; p ! >; < p ! p ; $ #2; f 0 $ e >; < p ! p ; #2 $ f 0; e ! F >; < p ! p ; f 0 ! f ; F ! F >; cw(u) = l; cw(l) = d; cw(d) = r; cw(r) = u; q = cw(x) < x ! x ; #2 $ f ; e $ q >; < x ! q ; f ! f 0; q ! + >; < q ! q ; + $ #2; f 0 $ e >; < q ! q ; #2 $ f 0; e ! F >; < q ! q ; f 0 ! f ; F ! F >; to rotate twice and move dc(u) = d; dc(l) = r; dc(d) = u; dc(r) = l; y = dc(x) < x ! x ; #2 $ f ; e $ y >; < x ! y ; f ! f 00; y ! + >; < y ! y ; + $ #2; f 00 $ e >; < y ! y ; #2 $ f 00; e ! + >; < y ! y ; f 00 ! f 0; + ! + >;
If the initial angle of the turtle is 90 degrees (it faces up) the agent A1 rewrites string into F F F. If the initial angle of the turtle is 0 degrees (it faces right) the agent A1 rewrites string into +F F F. The initial angle is generated by a program that launches this phase of computation and it is given by definition of used turtle graphics system. Env. a#1N a#1N a#1#N a#1#N a#1#N a#1#N a#1#N a#1#N g#1#N #1L#N1 #1L#N1 #1Lu#N2
Configuration
A1 eec eec eec w1ee w2ee w3ee w4ee 0ge 1 ae 2 eg e 3 e e 4 e
A2 #ee #N ee N#N1 ee #N1 LN1 #N1 LN1 #N1 LN1 #N1 LN1 #N1 LN1 #N1 LN1 #N eN1 #N2 uN2 #N1 eN2
Applicable programs A1 A2
B3(X=N)
B4
B6 A3 A4 A5 A6 A7 A8 A11 B7(x1=L)
A12 B8(x2=u) A13(i=3) B9 A13(i=4) B10(i=3; x3=N)
Env. #1Lu#N2 #1LuN#N3 #1LuN#N3 #1LuNr#N4 #1LuNr#N4 #1LuNrN#N5 #1LuNrN#N5 #1LuNrNd#N6 #1LuNrNd#N6 #1LuNrNdR #1LuNrNdR Applicable programs
A2
B11(i=3) B10(i=4; x4=r)
B11(i=4) B10(i=5; x5=N)
B11(i=5) B10(i=6; x6=d)
B11(i=6) B10(i=7; x7=R)
B12 B13 B14
A2
A2
A2 ee# ee#
A1 A14
Applicable programs
A2 A2 A2 B14 B15 B15 B3 B3 B3
A2 B3 The Moore curve is a variant of Hilbert curve. The first four iterations are depicted in Figure 2. To generate word representation of Moore curve we use rewriting contextfree (CF) rules over non-terminal alphabet fA; B;C; E; Fg and terminals from fu; d; l; rg. The CF rules are:
A derivation of word representation of Moore curve starts with string A. The derivation of word M1 is
and the word M2 is generated as follows:
eAPcol systems generating Moore curve are very similar to that one generating commands for Hilbert curve. They differs only in the programs for the second phase of part 3, because the generating CF rules are different. But the CF rules are of the same length and they contain the same number of non-terminals on their right hand side. A3 A4 A5 A6 A9 A10 A15 A16 n = 1
All right hand sides of the rules are again of the same length ( it is a transformation of the original curve representation), but the number of non-terminals on the right hand side of the rules has increased from 4 to 9 compared to the Hilbert curve. The phase of agent creation has to take more steps (4 steps) and system will generate some spare agents (sixteen instead of nine). Also the phase of insertion of objects from right hand side of CF rules will take more steps (35 steps). The other phases of computation stays the same as in previous subsection. 4
In this contribution we showed APcol system with agent creation as a kind of P colonies is suitable model for turtle graphics commands generation. We presented the idea of construction of APcol system with capacity two that can compute turtle commands for given number of iteration as the input. We have described the construction of the system for two space-filling curves - Hilbert curve and Peano curve. For the construction, we exploited the existence of context-free rules to generate a string of directions representing these curves. Future work in the area of APcol systems ability research may focus not only on generating space-filling curves, but also on generation of command string of other curves that use parameters (for example a change of step length ) or the stochastic command generation rules.
Notes and Comments. This work was supported partially by European Union under European Structural and Investment Funds Operational Programme Research, Development and Education project Zvýšení kvality vzdeˇlávání na Slezské univerziteˇ v Opaveˇ ve vazbeˇ na potrˇ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/11/2019.