=Paper=
{{Paper
|id=Vol-2962/paper43
|storemode=property
|title=APcol systems and Turtle Graphics
|pdfUrl=https://ceur-ws.org/Vol-2962/paper43.pdf
|volume=Vol-2962
|authors=Lucie Ciencialová,Luděk Cienciala
|dblpUrl=https://dblp.org/rec/conf/itat/CiencialovaC21
}}
==APcol systems and Turtle Graphics ==
https://ceur-ws.org/Vol-2962/paper43.pdf
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.