APcol systems and Turtle Graphics Lucie Ciencialová, Luděk Cienciala Institute of Computer Science, Silesian University in Opava, Czech Republic lucie.ciencialova@fpf.slu.cz ludek.cienciala@fpf.slu.cz Abstract: In this paper we continue our investigations in forming their programs is maximal - the joint action of the APCol systems (Automaton-like P colonies), variants of P agents is maximally parallel if no more active agent can colonies where the environment of the agents is given by be added to the synchronously acting agents. An agent is a string and the functioning of the system resembles to the active if it is able to execute at least one of its programs. functioning of standard finite automaton. We introduce a The computation ends if there are no more applicable new variant of APcol systems called extended APcol sys- programs in the system. tems - agents capacity is not limited to two objects. We For more detailed information on APCol systems we re- deal with the concept of agent creation in these systems fer to [3, 4]. and possibility of generation of strings as commands for In computer graphics, turtle graphics are vector graphics turtle graphics. using a relative cursor - the “turtle” to draw curves. Com- mands for turtle can be formed into string and hence we 1 Introduction can speak about a turtle representation of string. A state of the turtle is defined as a triplet (x, y, α), where the Carte- Automaton-like P colonies (APCol systems, for short), in- sian coordinates (x, y) represent the turtle’s position, and troduced in [2], are variants of P colonies (introduced in the angle α, called the heading, is interpreted as the direc- [9]) - very simple membrane systems inspired by colonies tion in which the turtle is facing. Given the step size d and of formal grammars. The interested reader is referred to the angle increment δ , the turtle can respond to commands [11] for detailed information on membrane systems (P sys- represented by the following symbols: tems) and to [10] and [6] for more information to grammar systems theory. For more details on P colonies consult the F Move forward a step of length d. The state of the turtle surveys [8] and [5]. changes to (x0 , y0 , α), where x0 = x + d cos α and y0 = An APCol system consists of a finite number of agents y + d sin α. A line segment between points (x, y) and and their joint shared environment. The agents are formed (x0 , y0 ) is drawn. from a finite number of objects and their functioning is based on programs consisting of rules. These rules are of f Move forward a step of length d without drawing a line. two types: they may change the objects of the agents and they can be used for interacting with the joint shared en- vironment of the agents. While in the case of standard P + Turn left by angle δ . The next state of the turtle is colonies the environment is a multiset of objects, in case (x, y, α + δ ). The positive orientation of angles is of APCol systems it is represented by a string. The num- counter-clockwise. ber of objects inside each agent is set by definition and it is usually a very small number: 1, 2 or 3. The string repre- − Turn right by angle δ . The next state of the turtle is senting the environment is processed by the agents and it (x, y, α − δ ). is used as a communication channel for the agents as well, since through the string, the agents are able to affect the Given a string s, the initial state of the turtle (x0 , y0 , α0 ) behaviour of another agent. and fixed parameters d and δ , the turtle interpretation of s Agents are also equipped with agent creation programs. is the curve (set of lines) drawn by the turtle in response to They are applicable when a special object appears inside the string s. Turtle graphics is used for example to interpret the agent. An agent with the special object can make one strings generated by L-systems (more details reader can copy of itself containing objects specified by the program. find in [13]). The computation in APCol systems starts with an input In this paper we deal with APcol systems with agent cre- string, representing the environment, and with each agent ation programs generating strings that can be interpreted in its initial state. in turtle graphics. We construct APcol system generating Every computational step is done in a maximally par- string representation of two space-filling curves Hilbert allel way which means that a set of the active agents per- curve and Peano curve. In [1] the authors deal with gener- Copyright ©2021 for this paper by its authors. Use permitted under ation of string representation of space-filling curves by P Creative Commons License Attribution 4.0 International (CC BY 4.0). systems with array rewriting rules. 2 Preliminaries and Basic Notions parent-agent after the execution of the program is bc while the contents of the child-agent is ba. Throughout the paper we assume the reader to be familiar If the parent-agent has a program p2 = ha → c; @ → bi, with the basics of the formal language theory and mem- then after the execution of the program p2 the contents of brane computing [14, 11]. parent-agent after the execution of the program is bc and For an alphabet Σ, the set of all words over Σ (including the contents of the child-agent is bc, too. the empty word, ε), is denoted by Σ∗ . We denote the length The order of rules determines whether the rewriting rule of a word w ∈ Σ∗ by |w| and the number of occurrences without @ is used before or after the creation of the child- of the symbol a ∈ Σ in w by |w|a . agent. A multiset of objects M is a pair M = (O, f ), where O An extended APcol system is APcol system having ca- is an arbitrary (not necessarily finite) set of objects and f pacity k ≥ 1 given by definition. The increase of the capac- is a mapping f : O → N; f assigns to each object in O its ity results in an elongation of the context for the applica- multiplicity in M. Any multiset of objects M with the set tion of programs with communication rules. In programs of objects O = {x1 , . . . xn } can be represented as a string w with agent creation rules, the increased capacity affects the over alphabet O with |w|xi = f (xi ); 1 ≤ i ≤ n. Obviously, content of agents - the rules listed before the agent creation all words obtained from w by permuting the letters can also rule are executed before the creation of a new agent, and represent the same multiset M, and ε represents the empty the rules listed after the agent creation rule are executed multiset. only on the parent agent. We introduce new type of rule, object occurrence con- 2.1 Extended APCol System ditional rule. The rule (rewritting, communication) is en- riched by the prefix “o|” and it means that the rule can be APCol system is a kind of P colony. It is formed from executed only if object o is present in the environmental agents with capacity 2 processing the string. They act ac- string in current configuration under the assumption that cording to programs as it is usual in P colonies. Each pro- the rule itself is applicable. Prefix “e|” means that rule is gram is formed from two rules of two types. The first type applicable if rule without prefix is applicable too ( it adds called rewriting is of the form a → b and by execution of no applicability condition). We also define prefix “¬o|” this rule, the object a inside the agent is rewritten to the ob- and it means that the rule can be executed only if object ject b. The second type of rules is called communication. o is not present in the environmental string in current con- The communication rules are of the form c ↔ d and by use figuration under the assumption that the rule itself is appli- of them, the agent replaces the symbol d in the string by cable. 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 Definition 1. An extended APCol system (eAPcol system (c ↔ e) it means that agent inserts symbol c to the string for short) with capacity k ≥ 1 with agent creation is a con- in a place which is determined by use of another commu- struct nication rule in the same program or if there is no other Π = (O, e, @, A1 , . . . , An ), communication rule in the program c is placed in random position. where Let us make a few comments about the application of the programs. • O is an alphabet, its elements are called the objects; 1. Agent can act in only one place in the string in one • e ∈ O, called the basic object; step of computation. • @ ∈ O, called the agent creation object; 2. ha ↔ b; c ↔ ei ⇒ b → ac in the string, • Ai , 1 ≤ i ≤ n, are agents. Each agent is a triplet Ai = hc ↔ e; a ↔ bi ⇒ b → ca in the string, (ωi , Pi , Fi ), where ha → b; c ↔ ei ⇒ ε → c in the string, insert c anywhere to the string, and rewrite a to b inside agent – ωi is a multiset over O, describing the initial ha → b; e ↔ di ⇒ d → ε in the string, delete one state (contents) of the agent, |ωi | = k,  d from the string, and rewrite a to b inside agent – Pi = pi,1 , . . . , pi,ki is a finite set of programs associated with the agent, where each program If an agent contains a special object @, the agent makes is a pair of rules. Each rule is in one of the a copy of itself. This action is done by executing a program following forms: formed from two rewriting rules. Let a@ be a contents of agent A1 with program p1 = h@ → b; a → ci. After exe- * a → b, where a, b ∈ O, called an rewriting cution of the program p1 there is one new child-agent in rule, the APCol system with the same label and the same set of * c ↔ d, where c, d ∈ O, called a communi- programs as the parent-agent A1 has. The contents of the cation rule; If @ appears on the left side of the rule in n=1 n=2 n=3 n=4 the program, all rules of this program must be rewriting; Prefix “o|” can be add to rule (not with @ on the left side) and it adds condition for applicability of the program - object o ∈ O must be present in the environmental string. Prefix “¬o|” can be add to rule (not with @ on the left side) and it means that program is applicable if Figure 1: First four approximations of the Hilbert curve, object o ∈ O is not present in the environmental H1 , H2 , H3 , H4 . string. – Fi ⊆ O∗ is a finite set of final states (contents) of follow the rules of parallel grammars to rewrite all oc- agent Ai . currences of non-terminals one by one, so that the agent When an agent obtains the object @ by the execution " moves" the object-tag that separates the processed part of a rewriting or a communication rule in the program, the of the string from the unprocessed part as it rewrites non- agent must create a new agent in the next step of the com- terminals to strings. putation in the way described within the above definition. Alternatively, we can use a parallel approach (as in L- The computation starts in the initial configuration where systems [13]) that requires rewriting all non-terminals in all agents contain their initial multiset of objects and there string in one step. Because of the increasing number of is an input string over the alphabet T on the eAPCol sys- non-terminals, the number of agents that process the string tem. Consequently, an initial configuration of the eAPCol needs to increase. system is an (n + 1)-tuple c = (ω; ω1 , . . . , ωn ) where ω is In this paper, we use both approaches. We use the par- the initial state of the environment and the other n compo- allel approach to generate the string describing the curve nents are multisets of objects, given in the form of strings, and the transcoding of the result into the turtle graphics the initial states of the agents. language is done sequentially. A configuration of an eAPCol system Π is given by (w; w1 , . . . , wnl ), where |wi | = k, 1 ≤ i ≤ n, wi repre- sents all the objects inside the agent labelled Ai and w ∈ 3.1 Hilbert curve (O − {e})∗ is the string to be processed. In 1891 Hilbert introduced the Hilbert space-filling curve At each step of the computation every agent attempts in [7]. Its finite approximations, the Hilbert words, were to find one of its programs to use. If the number of ap- first described as chain-code words in [15]. The first ap- plicable programs is higher than one, then the agent non- proximation is given by H1 = urd where u, d, r, l are ob- deterministically chooses one of them. At one step of com- jects representing direction up, down, right and left, and, putation, the maximal possible number of agents have to for n > 1; the subsequent approximations are given by be active, i.e., have to perform a program. By executing programs, the eAPCol system passes from Hn+1 = γ(Hn )uHn rHn dϕ(Hn ) one configuration to another configuration. A sequence of configurations started from the initial configuration is where γ, ϕ are homomorphisms on alphabet given by: called a computation. γ(u) = r; γ(d) = l; γ(l) = d; γ(r) = u – symmetry w.r.t. Oy The computation halts when no agent has an applicable and rotation right 90 degrees; program. ϕ(u) = l; ϕ(d) = r; ϕ(l) = u; ϕ(r) = d – symmetry w.r.t. Oy and rotation left 90 degrees. 3 Space-Filling Curves generation by The first four approximations are shown in Figure 1. eAPcol Systems Hilbert words can be generated by context-free rules that are applied parallelly to string formed from termi- In this paper, we focus on the generation of control strings nals and non-terminals. To generate Hilbert words we use for generating space-filling curves using turtle graphics. rewriting context-free (CF) rules over non-terminal alpha- We concentrated on three curves - Hilbert, Moore and bet {N, L, R,U} and terminals from {u, d, l, r}. The CF Peano. All three curves are fractal-like. A new iteration of rules are: the curve is formed according to a given rule from the pre- 1. N → LuNrNdR vious iteration. This increases the area filled by the curve. Various mechanisms are used to generate iterations of 2. L → NrLuLlU these curves (or control strings for turtle graphics), for ex- ample, parallel grammars or L-systems. 3. R → UlRdRrN There are several techniques for generating these strings by eAPcol systems. We can use a sequential approach and 4. U → RdUlUuL The starting string is N. In the last step of generation Agent A1 is equipped by the following programs for first of Hilbert word we use another set of rules that is formed three phases of computation: from ε-rules and all non-terminals are erased from word. Another approach is to count with terminals only in each A1 < #|e → e; e → e; e → b >; generated word. Hilbert word H1 is obtained by execution A2 < e → e; e → e; b → c >; of the first rule to starting string A3 < ¬N|e → w1 ; e → e; c → e >; A4 < ¬L|w1 → w2 ; e → e; e → e >; A5 < ¬R|w2 → w3 ; e → e; e → e >; N ⇒ LuNrNdR ⇒ urd A6 < ¬U|w3 → w4 ; e → e; e → e >; A7 < a|w4 → 0; e → g; e → e >; The second Hilbert word, H2 is generated from N by fol- A8 < 0 → 1; g ↔ a; e → e >; lowing derivation: A9 < ¬a|w4 → 00 ; e → f ; e → e >; A10 < 00 → 00 ; f ↔ #1 ; e → e >; N ⇒ LuNrNdR ⇒ A11 < a → e; 1 → 2 ; e ↔ g >; ⇒ NrLuLlUuLuNrNdRrLuNrNdRdUlRdRrN ⇒ A12 < g → e; 2 → 3 ; e → e >; ⇒ ruluurdrurddldr A13 < e → e; i → i+1 ; e → e >; 3 ≤ i ≤ 14 A14 < 15 → e; e → e; e → c > For the turtle to draw the first approximation of the Hilbert curve, the command string is F − F − F. The com- The second agent in the first two steps generates the mand string for second approximation of Hilbert curve is starting word N. The agent places object N next to object F + F + F − FF − F − F + F + F − F − FF − F + F + F. #. The communication rule is equipped with condition a :, To generate Hilbert curve we construct eAPcol system it means that agent can put N into string only if a is present with capacity three and with agent creation formed from in the sting. This is initialization phase for generation of two kind of agents. Hilbert word. B1 < e → #1 , e → N; e → e >; 1. The input of the system is a string s0 = an # corre- B2 < #1 ↔ #; a|N ↔ e; e → e > sponding to the number of iterations concatenated with a special symbol labelling the end of input. The In our example, the initial configuration of the system is output of system is command string for Turtle Graph- (a#; eeeA1 , eeeA2 ). The first phase of computation is shown ics to generate n-th approximation of Hilbert curve in the Table 1. In rows, there are configurations of the concatenated with symbol #2 . system and sets of applicable programs. If there are more than one applicable program associated with an agent, the 2. The first agent A1 removes one occurrence of object executed program is indicated by bold. a after all non-terminals are deleted from a string of Configuration Applicable programs computation. Env. A1 A2 A1 A2 a# eee eee A1 B1 3. The second agent A2 will generates approximations a# eeb #1 Ne A2 B2 of Hilbert word in two phases. a#1 N eec #ee − B3 In the first phase the agent generates symbols cor- responding to the direction of movement of turtle Table 1: The first phase of generation of command string (u, d, r, l for direction up, down, right and left) with for H1 objects called non-terminals according to CF rules. In the next phase, the agent A2 replaces N by string In the second phase, the agent makes a copy of it- LuNrNdR in accordance to the first CF rule. First it gener- self twice. It means that in three steps the number of ates object #X , where X is non-terminal object. This pro- agents labelled by A2 rises four times (the reason is gram in non-deterministically chosen. If there is no such the parallel simulation of the execution of the rules non-terminal present in the string (before this step there listed below). was no such non-terminal or the number of occurrences of non-terminal X was less than the number of agents that 4. The last phase of computation is to “code” directions generated object #X ), the agent can rewrite object #X into u, d, l, r into turtle language. # in the next step. It is done in fourteen steps, because agent uses program with two rewriting rules, then another Now, we describe the function of the constructed system one with two communication rules to generate one object in more detail, present the programs of the agents, and il- of the right side of rule and one object marking the point lustrate the function of the system using the example of where to insert new objects. We note that all CF rules generating a command string for the first approximation are of the same length and all the agents are working si- of the Hilbert curve. multaneously so when there are more agents with label A2 they can insert object in different parts of string. But In final phase the agent A1 rewrite objects {u, d, l, r} to the agents can consume object marker (for example #N2 symbols {F, +, −}. The coding depends on two consecu- - marker object for insertion of second object of CF rule tive objects, for example if ru is substring of the environ- with N on the left-hand side of the rule) that corresponds mental string u is replaced by +F because to draw line in only to currently performed CF rule. Let X ∈ {N, L, R,U} direction up after line in direction right turtle must turn 90 and X → x1 x2 x3 x4 x5 x6 x7 is CF rule. degrees left and draw a line. To draw Hilbert curve by turtle we have to set two pa- B3 < # → #X , e → e; e → e >; rameters - the step size and the angle increment - and ini- B4 < #X ↔ X; e → #X1 ; e → e > tial state of the turtle. For code generation it is necessary B5 < ¬X|#X → #, e → e; e → e >; For a case that to set the angle increment δ = 90◦ and turtle orientation to there is no non-terminal X in the string up (α = 90◦ ). Because of angle increment the turtle can be B6 < #X1 → #X1 , X → x1 ; e → X1 >; oriented in four directions (up,  down, right, left). Boxed B7 < g|x1 ↔ #X ; #X1 ↔ e; X1 → X1 >; symbols u , d , r , l can represent current turtle B8 < #X → #X2 , e → x2 ; X1 → X2 >; orientation. B9 < x2 ↔ #X1 ; #X2 ↔ e; X2 → X2 > There are following programs in a set of programs of B10 < #Xi−2 → #Xi , e → xi ; Xi−1 → Xi >; 3 ≤ i ≤ 7 agent A1 : B11 < xi ↔ #Xi−1 ; #Xi ↔ e; Xi → Xi >; 3 ≤ i ≤ 6 B12 < x7 ↔ #X6 ; #X7 → e; X7 → X7 >; B13 < #X6 → @, e → F; X7 → e > A15 < 00 → u ; #1 → #2 ; e → e >; We demonstrate the application of the programs by con- to move in the same direction as turtle is facing tinuing the example: In Table 2, we show how the compu- x ∈ {u, d, r, l} tation is done when agent A2 chooses program associated A16 < x → x ; #2 ↔ f ; e ↔ x >; with non-terminal that is not present in the string (or non- A17 < x → x ; f → f ; x → F >; terminal is used by another copy of the agent). A18 < x → x ; F ↔ #2 ; f ↔ e >; Configuration Applicable programs to rotate and move Env. A1 A2 A1 A2 cc(u) = r; cc(r) = d; cc(d) = l; cc(l) = u; p = cc(x) a#1 N eec #ee − B3 : <#→#L ,e→e;e→e> A19 < x → x ; #2 ↔ f ; e ↔ p >; a#1 N eec #L ee − B5 : <¬L|#L →#,e→e;e→e> A20 < x → p ; f → f 0 ; p → − >; a#1 N eec #ee − B3 A21 < p → p ; − ↔ #2 ; f 0 ↔ e >; Table 2: The second phase of generation of command A22 < p → p ; #2 ↔ f 0 ; e → F >; string for H1 - wrong choice of non-terminal A23 < p → p ; f 0 → f ; F → F >; cw(u) = l; cw(l) = d; cw(d) = r; cw(r) = u; q = cw(x) In Table 3 the computation with right choice of program A24 < x → x ; #2 ↔ f ; e ↔ q >; is shown. A25 < x → q ; f → f 0 ; q → + >; After insertion of all the objects from the right-hand side A26 < q → q ; + ↔ #2 ; f 0 ↔ e >; of the CF rule, the agent A2 is creating new agents in two A27 < q → q ; #2 ↔ f 0 ; e → F >; steps using programs A28 < q → q ; f 0 → f ; F → F >; B14 < F → S; e → @; @ → e; >; B15 < S → e; e → e; @ → # > to rotate twice and move dc(u) = d; dc(l) = r; dc(d) = u; dc(r) = l; y = dc(x) After this phase in the first iteration the environmental A29 < x → x ; #2 ↔ f ; e ↔ y >; string is in the form an−1 #1 LuNrNdR and there are four agents labelled A2 in the eAPcol system. A30 < x → y ; f → f 00 ; y → + >; In Table 5, the creation of new agents labelled A2 is A31 < y → y ; + ↔ #2 ; f 00 ↔ e >; shown. A32 < y → y ; #2 ↔ f 00 ; e → + >; When agent A1 deletes all occurrences of object a from A33 < y → y ; f 00 → f 0 ; + → + >; the environmental string, f appears in the environment and agents labelled A2 delete all non-terminals from the string. B16 < f |x1 → f ; #X1 → e; X1 → X1 >; If the initial angle of the turtle is 90 degrees (it faces up) B17 < f → f ; e ↔ #X ; X1 → f >; 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 If the environmental string was #1 LuNrNdR before this rewrites string into +F − F − F. The initial angle is gener- phase of computation, four agents deleted non-terminals ated by a program that launches this phase of computation from the string and after this phase the string is f urd. and it is given by definition of used turtle graphics system. Configuration Applicable programs Configuration Applicable programs Env. A1 A2 A1 A2 Env. A1 A2 A1 A2 a#1 N eec #ee − B3(X=N) #1 Lu#N2 e 5 e #N3 NN3 A13(i=5) B11(i=3) a#1 N eec #N ee − B4 #1 LuN#N3 e 6 e #N2 eN3 A13(i=6) B10(i=4; x4 =r) a#1 #N eec N#N1 ee A3 B6 #1 LuN#N3 e 7 e #N4 rN4 A13(i=7) B11(i=4) a#1 #N w1 ee #N1 LN1 A4 − #1 LuNr#N4 e 8 e #N3 eN4 A13(i=8) B10(i=5; x5 =N) a#1 #N w2 ee #N1 LN1 A5 − #1 LuNr#N4 e 9 e #N5 NN5 A13(i=9) B11(i=5) a#1 #N w3 ee #N1 LN1 A6 − #1 LuNrN#N5 e 10 e #N4 eN5 A13(i=10) B10(i=6; x6 =d) a#1 #N w4 ee #N1 LN1 A7 − #1 LuNrN#N5 e 11 e #N6 dN6 A13(i=11) B11(i=6) a#1 #N 0ge #N1 LN1 A8 − #1 LuNrNd#N6 e 12 e #N5 eN6 A13(i=12) B10(i=7; x7 =R) g#1 #N 1 ae #N1 LN1 A11 B7(x1 =L) #1 LuNrNd#N6 e 13 e #N7 RN7 A13(i=13) B12 #1 L#N1 2 eg #N eN1 A12 B8(x2 =u) #1 LuNrNdR e 14 e #N6 eN7 A13(i=14) B13 #1 L#N1 e 3 e #N2 uN2 A13(i=3) B9 #1 LuNrNdR e 15 e @Fe A14 B14 #1 Lu#N2 e 4 e #N1 eN2 A13(i=4) B10(i=3; x3 =N) Table 3: The second phase of generation of command string for H1 - right choice of non-terminal Configuration Applicable programs Env. A1 A2 A2 A2 A2 A1 A2 A2 A2 A2 #1 LuNrNdR e 15 e @Fe − − − A14 B14 #1 LuNrNdR eec S@e S@e − − − B15 B15 #1 LuNrNdR eec ee# ee# ee# ee# − B3 B3 B3 B3 Table 4: The third phase of generation of command string for H1 - agent creation 3.2 Moore curve n=1 n=2 n=3 n=4 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 context- free (CF) rules over non-terminal alphabet {A, B,C, E, F} and terminals from {u, d, l, r}. The CF rules are: 1. A → BuBrGdG Figure 2: First four approximations of the Moore curve, M1 , M2 , M3 , M4 . 2. B → ClBuBrE 3. C → BuClCdG 3.3 Peano Curve 4. E → GdErEuB Peano defined this space-filling curve in 1890, in [12]. 5. G → ErGdGlC Represented as chain-code words, the first Peano word is P1 = uurddruu, and for n > 1; the subsequent approxi- A derivation of word representation of Moore curve starts mations are given by with string A. The derivation of word M1 is Pn+1 = Pn uλ (Pn )uPn rρ(Pn )dδ (Pn )dρ(Pn )rPn uλ (Pn )uPn A ⇒ BuBrFdF ⇒ urd where λ ; ρ; δ are homomorphisms on the alphabet of and the word M2 is generated as follows: directions{l; r; u; d} as given below: A ⇒ BuBrGdG ⇒ λ (u) = u; λ (d) = d; λ (l) = r; λ (r) = l – symmetry w.r.t. ⇒ ClBuBrEuClBuBrErErGdGlCdErGdGlC ⇒ Oy axis ⇒ lurulurrrdldrdl ρ(u) = d; ρ(d) = u; ρ(l) = l; ρ(r) = r – symmetry w.r.t. Ox axis eAPcol systems generating Moore curve are very sim- δ (u) = d; δ (d) = u; δ (l) = r; δ (r) = l – symmetry w.r.t. ilar to that one generating commands for Hilbert curve. origin. They differs only in the programs for the second phase of The constructed eAPcol system is very similar to the part 3, because the generating CF rules are different. But one that generates representation of Hilbert curve. First the CF rules are of the same length and they contain the let us introduce CF rules generating Peano curve direction same number of non-terminals on their right hand side. representation. The CF rules are: Configuration Applicable programs Env. A1 A2 A2 A2 A2 A1 A2 A2 A2 A2 #1 LuNrNdR eec ee# ee# ee# ee# − B3(X=L) B3(X=N) B3(X=N) B3(X=R) #1 LuNrNdR eec ee#L ee#N ee#N ee#R − B4 B4 B4 B4 #1 #L u#N r#N d#R eec L#L1 e N#N1 e N#N1 e R#R1 e A3 B6 B6 B6 B6 #1 #L u#N r#N d#R eew1 N#L1 L1 L#N1 N1 L#N1 N1 U#R1 R1 A4 − − − − #1 #L u#N r#N d#R eew2 N#L1 L1 L#N1 N1 L#N1 N1 U#R1 R1 A5 − − − − #1 #L u#N r#N d#R eew3 N#L1 L1 L#N1 N1 L#N1 N1 U#R1 R1 A6 − − − − #1 #L u#N r#N d#R eew4 N#L1 L1 L#N1 N1 L#N1 N1 U#R1 R1 A9 − − − − #1 #L u#N r#N d#R e f 00 N#L1 L1 L#N1 N1 L#N1 N1 U#R1 R1 A10 − − − − f #L u#N r#N d#R e#1 00 N#L1 L1 L#N1 N1 L#N1 N1 U#R1 R1 A15 B16 B16 B16 B16 f #L u#N r#N d#R u #2 e f eL1 f eN1 f eN1 f eR1 − B17 B17 B17 B17 f urd u #2 e f f #L f f #N f f #N f f #R A16 − − − − Table 5: The fourth phase of generation of command string for H1 - deletion of all non-terminals 4 Conclusion n=1 n=2 n=3 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 n=4 the input. We have described the construction of the sys- tem 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 repre- senting 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 genera- tion rules. Figure 3: First four approximations of the Peano curve, P1 , P2 , P3 P4 . Notes and Comments. This work was supported par- tially by European Union under European Structural and Investment Funds Operational Programme Re- 1. N → NuLuNrRdDdRrNuLuN search, Development and Education project Zvýšení kvality vzdělávání na Slezské univerzitě v Opavě 2. L → LuNuLlDdRdDlLuNuL ve vazbě na potřeby Moravskoslezského kraje, 3. R → RdDdRrNuLuNrRdDdR CZ.02.2.69/0.0/0.0/18_058/0010238 and by the Sile- sian University in Opava under the Student Funding 4. D → DdRdDlLuNuLlDdRdD Scheme, project SGS/11/2019. All right hand sides of the rules are again of the same length ( it is a transformation of the original curve repre- References sentation), but the number of non-terminals on the right hand side of the rules has increased from 4 to 9 compared [1] Ceterchi, R., Subramanian, K.G. Generating pictures in to the Hilbert curve. The phase of agent creation has to string representation with P systems: the case of space- take more steps (4 steps) and system will generate some filling curves. J Membr Comput 2, 369–379 (2020). spare agents (sixteen instead of nine). Also the phase of [2] Cienciala, L., Ciencialová, L., Csuhaj-Varjú, E.: Towards insertion of objects from right hand side of CF rules will P Colonies Processing Strings. In: Proc. BWMC 2014, take more steps (35 steps). The other phases of computa- Sevilla, 2014. pp. 102–118. Fénix Editora, Sevilla, Spain tion stays the same as in previous subsection. (2014) [3] Cienciala, L., Ciencialová, L., Csuhaj-Varjú, E.: P colonies processing strings. Fundamenta Informaticae 134(1-2), 51– 65 (2014) [4] Cienciala, L., Ciencialová, L., Csuhaj-Varjú, E.: A Class of Restricted P Colonies with String Environment. Natural Computing 15(4), 541–549 (2016) [5] Ciencialová, L. ,Csuhaj-Varjú, E., Cienciala, L.,Sosík, P.: P colonies. Bulletin of the International Membrane Comput- ing Society 1(2):119–156 (2016). [6] Csuhaj-Varjú, E., Kelemen, J., Păun, Gh., Dassow, J.(eds.): Grammar Systems: A Grammatical Approach to Distribu- tion and Cooperation. Gordon and Breach Science Publish- ers, Inc., Newark, NJ, USA (1994) [7] Hilbert, D. : Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Annln. 38 459–460 (1891).). [8] Kelemenová, A.: P Colonies. Chapter 23.1, In: Păun, Gh., Rozenberg, G., Salomaa, A. (eds.) The Oxford Handbook of Membrane Computing, pp. 584–593. Oxford University Press (2010) [9] Kelemen, J., Kelemenová, A., Păun, G.: Preview of P Colonies: A Biochemically Inspired Computing Model. In: Workshop and Tutorial Proceedings. Ninth International Conference on the Simulation and Synthesis of Living Sys- tems (Alife IX). pp. 82–86. Boston, Mass (2004) [10] Kelemen, J., Kelemenová, A.: A Grammar-Theoretic Treatment of Multiagent Systems. Cybern. Syst. 23(6), 621–633 (1992), [11] Păun, Gh., Rozenberg, G., Salomaa, A.(eds.): The Ox- ford Handbook of Membrane Computing. Oxford Univer- sity Press, Inc., New York, NY, USA (2010) [12] Peano, G.: Sur une courbe qui remplit toute une aire plane. Math. Annln. 36, 157–160 (1890). [13] Prusinkiewicz, P., Lindenmayer, A.: The Algorithmic Beauty of Plants. Springer-Verlag, Berlin, Heidelberg (1996) [14] Rozenberg, G., Salomaa, A.(eds.): Handbook of Formal Languages I-III. Springer Verlag., Berin-Heidelberg-New York (1997) [15] Siromoney, R., Subramanian, K.G. : Space-filling curves and Infinite graphs. Lecture notes in Comp. Sci. 153 (1983) 380–391.