arXiv:1705.02809v2 [math.GR] 1 Feb 2018

APPLICATIONS OF L SYSTEMS TO GROUP THEORY
LAURA CIOBANU, MURRAY ELDER, AND MICHAL FEROV
Abstract. L systems generalise context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L
that are strictly contained in the class of indexed languages. In this paper we show that many of the languages naturally appearing in group
theory, and that were known to be indexed or context-sensitive, are in
fact ET0L and in many cases EDT0L. For instance, the language of
primitives and bases in the free group on two generators, the BridsonGilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk’s group can be generated
by L systems. To complement the result on primitives in rank 2 free
groups, we show that the language of primitives, and primitive sets, in
free groups of rank higher than two is context-sensitive. We also show
the existence of EDT0L and ET0L languages of intermediate growth.

1. Introduction
In this paper we show that many of the context-sensitive or indexed languages arising in problems in group theory and combinatorics are in fact
ET0L or even EDT0L. The merit of giving this new formal language characterisation is that ET0L and EDT0L languages are a strict subclass of
the indexed ones, and also, the descriptions of these languages are simpler
and more algebraic than those based on indexed grammars or nested-stack
automata that were given in the literature for the sets considered here.
Both EDT0L and ET0L belong to the languages generated by L systems, which were introduced by Lindenmayer in the late 1960s in order to
model the growth of various organisms. The acronym ET0L (respectively
EDT0L) refers to Extended, Table, 0 interaction, and Lindenmayer (respectively Deterministic). ET0L and EDT0L languages have only recently
featured in group theory; their first prominent appearance was in the work
of the first two authors with Volker Diekert, in the context of equations in
groups. The language of solutions of equations in free groups as tuples of
reduced words is EDT0L [5], as are solutions in appropriate normal forms in
virtually free groups [9] and partially commutative groups [10]. The result
in [5] implies that the pattern languages studied by Jain, Miasnikov and
Stephan are EDT0L as well [19].
Date: February 5, 2018.
2010 Mathematics Subject Classification. 20F10; 20F65; 68Q42.
Key words and phrases. Free group; primitive; normal form; co-word problem; Grigorchuk
group; indexed language; ET0L language; EDT0L language.
1

In Section 2 we give the necessary background on formal languages. In
Section 3 we examine the gap between ET0L and indexed languages, and
in Section 4 we revisit an example of Grigorchuk and Machı̀ of a language
of intermediate growth and show that it is EDT0L. In the remaining sections we show why Lindenmeyer languages are relevant for group theory by
presenting several instances where L systems appear naturally. In Section
5 we describe the set of primitives in the free group on two generators as
EDT0L, improving on the context-sensitive characterisation by Silva and
Weil [27]. Furthermore, we show that the set of primitives, and primitive
sets, in free groups of rank higher than 2 is context-sensitive. In Section
6 we construct an explicit grammar to prove that the co-word problem in
Grigorchuks group is ET0L, and thus take a different approach to that of
Holt and Röver [18], who used nested-stack automata to describe the same
set. In Section 7 we show that the Bridson-Gilman normal forms for the
fundamental groups of 3-manifolds or orbifolds, proved in [2] to be indexed,
are in fact ET0L. We conclude the paper with a list of open problems.
2. ET0L and EDT0L languages
L systems were introduced by Lindenmayer in order to model the growth
of various organisms and capture the fact that growth happens in parallel
everywhere in the organism. Therefore the rewriting system had to incorporate parallelism, as opposed to the sequential behavior of context-free
grammars. The difference between sequential and parallel grammars is well
illustrated by the following example (page 2 in [26]).
Example 1. Suppose we have an alphabet A = {a} and a single rewriting
rule a −→ a2 , which is to be applied to a3 . If we apply this rule to one
a inside a3 at a time, we get the set {ai | i ≥ 3}. If we apply the rule
simultaneously to each a in a3 we obtain a6 after one rewrite, and the set
i
of words obtained via parallel rewriting is {a3·2 | i ≥ 0}.
There is a vast literature on Lindenmayer systems, see for example [26, 25],
with various acronyms such as D0L, DT0L, ET0L, HDT0L and so forth. The
following inclusions hold: EDT0L ( ET0L ( indexed, and context-free (
ET0L. Furthermore, the classes of EDT0L and context-free languages are
incomparable.
Let V be a finite alphabet. A table for V is a finite subset of V × V ∗ ,
that can be represented as in Figure 1.
V
V∗
a −→ a, b, aba
b −→ bbabb
# −→
#, b
Figure 1. A table for V = {a, b, #}.
2

If (c, v) is in some table t, we say that (c, v) is a rule for c and use the
convention that if for some c ∈ V no rule for c is specified in t, then t
contains the rule (c, c). We express the rewriting corresponding to the rule
(c, v) in t as c −→t v.
Definition 1 (ET0L). An ET0L-system is a tuple H = (V, A, T, I), where
(1) V is a finite alphabet,
(2) A ⊆ V is the subset of terminal symbols,
(3) T is a finite set of tables for V , that is, each t ∈ T is a finite subset
of V × V ∗ , and
(4) I ⊆ V ∗ is a finite set of words called axioms.
Let t ∈ T . We will write u −→t v to denote that a word v ∈ V ∗ can
be produced from u ∈ V ∗ using the rules in t; that is, if u = c1 · · · cm and
v = v1 · · · vm , where ci ∈ V and vi ∈ V ∗ , we write u −→t v to mean v was
obtained via rules cj −→t vj from table t, applied to each cj appearing in
u. More generally, u −→ v signifies u −→t v for some t ∈ T . If there exist
u0 , . . . , uk ∈ V ∗ with ui −→ ui+1 for 0 ≤ i ≤ k−1, then we write u0 −→∗ uk .
The language generated by H is defined as
L(H) = {v ∈ A∗ | w −→∗ v for some w ∈ I}.
A language is ET0L if it is equal to L(H) for some ET0L system H.
Definition 2 (EDT0L). An EDT0L-system is an ET0L system where in
each table there is exactly one rule for each letter in V . A language is
EDT0L if it is equal to L(H) for some EDT0L system H.
ET0L languages form a full AFL (abstract family of languages), that is,
they are closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation and Kleene closure, while
EDT0L are closed under all of the above except inverse homomorphism so
do not form a full AFL [7, 1].
If for some words u1 , u2 , u3 and tables t1 , t2 we have u1 −→t1 u2 and
u2 −→t2 u3 we will write u1 −→t1 t2 u3 to denote the composition of the
rewriting. This can be naturally extended to any finite sequence of rewrites.
Given a regular expression R over a finite set T = {t1 , . . . tn }, where t1 , . . . , tn
are tables, we will sometimes abuse the notation and use u1 −→R u2 to denote that there is a word r in the language generated by the regular expression R such that u1 −→r u2 . Furthermore, if the system is deterministic,
then every table is in fact a homomorphism on the free monoid V ∗ , and using this more algebraic notation we can give Asveld’s equivalent definition
for E(D)T0L languages as follows [1].
Definition 3. Let A be an alphabet and L ⊆ A∗ . We say that L is an
ET0L language if there is an alphabet C with A ⊆ C, a set H of tables (i.e.
finite subsets of C × C ∗ ), a regular language R ⊆ H ∗ and a letter c ∈ C
such that
L = {w ∈ A∗ | c −→r w for some r ∈ R}.
3

In the case when every table h ∈ H is deterministic, i.e. each h ∈ H is in
fact a homomorphism, we write r(c) = w and say that L is EDT0L.
The set R is called the regular (or rational) control, the symbol c the start
symbol and C the extended alphabet.
Convention. In any description of rational control in this paper, the maps
are always applied left to right, but in algebraic settings where f and g are
morphisms f g(a) := f (g(a)).
3. Non-ET0L languages
For completeness we present in this section a short survey of examples
of languages which are not ET0L. The first examples turn out not to be
indexed either.
Let ϕ : N+ → N+ be such that limn→∞ ϕ(n) = ∞ and let U be an arbitrary infinite subset of N. Set K(ϕ, U ) = {(baϕ(k) )k | k ∈ U }. This
construction gives us an infinite family of languages. It was proved in [11,
Theorem 2] that K(ϕ, U ) is not ET0L regardless of the choice of ϕ and U .
We show in Lemma 5 that these languages are not indexed.
Lemma 4. [15, Theorem A] (Shrinking lemma) Let L be an indexed language over a finite alphabet Σ and let m > 0 be a given integer. There is a
constant k > 0 such that each word w ∈ L with |w| ≥ k can be factorised as
a product w = w1 . . . wr such that the following conditions hold:
(i) m < r ≤ k,
(ii) wi 6= ǫ for every i ∈ {1, . . . , r},
(iii) each choice of m factors is included in a proper subproduct which
lies in L.
Lemma 5. The language K(ϕ, U ) is not indexed for any choice of ϕ and
U.
Proof. The proof follows that of [15, Corollary 4]. Assume that K(ϕ, U ) is
indexed and fix m = 1. Let k ∈ N be given by Lemma 4.
Pick k′ ∈ U such that k′ > k and k′ = min(ϕ−1 (ϕ(k′ ))). Note that such
′
′
′
k exists as limn→∞ ϕ(n) = +∞. Then w = (baϕ(k ) )k can be factorised as
w = w1 . . . wr , where 1 < r ≤ k < k ′ . As r < |w|b = k′ , by the pigeonhole
principle we see that there is some 1 ≤ i ≤ r such that |wi |b ≥ 2, i.e.
′
wi contains baϕ(k ) b as a subword. By Lemma 4, wi can be included in a
′
proper subproduct v which lies in K(ϕ, U ). However, v contains baϕ(k ) b, so
′′
′′
v = (baϕ(k ) )k for some k′′ ∈ N such that ϕ(k′ ) = ϕ(k′′ ). As v is a proper
subproduct of w we see that k′′ < k ′ . However, this is a contradiction with
k′ = min(ϕ−1 (ϕ(k′ ))), thus K(ϕ, U ) is not indexed.

Note that when ϕ is the identity function and U = N this was already
established in [17, Theorem 5.3] and later in [15, Corollary 4].
An explicit example of an indexed language which is not ET0L was given
in [14] as the language of tree-cuts. Informally speaking, a tree-cut is a
4

sequence of binary strings encoding the list of leaves of a proper rooted
binary tree, i.e. a tree in which every vertex has exactly zero or two children.
Formally, tree cuts can be defined in a recursive manner:
(i) the sequence containing only the empty string, i.e. (ǫ), is a tree-cut;
(ii) suppose that u1 , . . . , uk , v1 , . . . , vl ∈ {0, 1}∗ such that the sequences
(u1 , . . . , uk ) and (v1 , . . . , vl ) are tree-cuts, then the sequence
(0u1 , . . . , 0uk , 1v1 , . . . , 1vl )
is a tree-cut.
A sequence (v1 , . . . , vk ), where v1 , . . . , vk ∈ {0, 1} is a tree-cut if and only if
it can be obtained by repeatedly applying to the above mentioned rules. For
example, the sequence (000, 001, 01, 10, 11) is a tree-cut, but the sequence
(000, 111) is not. For more detail on tree-cuts see for example [14, Section
3].
Let a, b denote symbols distinct from 0 and 1. The language of cuts is
then defined as
L0 = {av1 0bv1 1 . . . avk 0bvk 1 | (v1 , . . . , vk ) is a cut} ⊆ {0, 1, a, b}∗ .
Carefully checking the proof of [14, Lemma 3.3] one can verify that the language L0 is accepted by a nested stack automaton and hence L0 is indexed.
It is then proved in [14, Lemma 3.4] that L0 is not ET0L.
Another example of an indexed language that is not ET0L is given in [13,
Corollary 2]. In fact, the paper suggests an infinite family of such languages.
However, the statement of [13, Theorem 3] contains a misprint, so we give
the correct statement here. For a word w ∈ Σ∗ let w denote its mirror
image, i.e. if w = x1 . . . xn , where x1 , . . . , xn ∈ Σ, then w = xn . . . x1 .
Theorem 6. (see [13, Theorem 3]) Let Σ be a finite alphabet and let Σ′ be
a copy of Σ distinct from Σ. Let h : Σ∗ → Σ′∗ be a homomorphism defined
by h(x) = x′ for every x ∈ Σ.
Let K be a context-free language over Σ such that K is not EDT0L. Then
the language
MK = {kh(k) | k ∈ K} ⊆ (Σ ∪ Σ′ )∗
is indexed but not ET0L.
It is a well known fact (see [12, Theorem 9]) that if K is the Dyck language
on at least 8 letters, then K is context-free but not EDT0L, hence MK is
indexed but not ET0L. In fact we observe below in Proposition 26 that the
word problem for free groups of rank at least 2 is not EDT0L.
4. Growth of languages
The growth of a language L ⊆ Σ∗ is the function f : N → N such that
f (n) is the number of words in L of length n. If Σ is finite then the growth
function is at most exponential. A language has intermediate growth if for
any α, β > 1 there is an integer N ∈ N such that for all n > N we have
5

nα < f (n) < β n . Bridson and Gilman showed that there are no contextfree languages of intermediate growth [3], whereas Grigorchuk and Machı̀
[16, Theorem 1] give the following example of a language of intermediate
growth which is recognisable by a one-way deterministic non-erasing stack
automaton (1DNESE), so is indexed. They define the set
A := {abi1 abi2 . . . abik | 0 ≤ i1 ≤ · · · ≤ ik , k ∈ N}
over the alphabet {a, b}.
Proposition 7. The language A is EDT0L.
Proof. We show that A is generated by an EDT0L system as in Definition
3, with the following data: the extended alphabet is {a, b, q, q ′ }, the start
symbol q, and the maps are ha , hb , h$ with ha (q) = qaq ′ , hb (q) = qb,
hb (q ′ ) = q ′ b, h$ (q) = h$ (q ′ ) = ǫ.
The rational control is given by R = {ha , hb }∗ ha h$ .
Let g ∈ {ha , hb }∗ . We can easily prove by induction on the length of g as a
word over {ha , hb } that g(q) = qbi1 aq ′ bi2 a . . . aq ′ bik where 0 ≤ i1 ≤ · · · ≤ ik ,
i.e the word starts with q, and then only q ′ appears. Then applying ha h$ to
g(q) produces a word which starts with a and contains no more q, q ′ .

Corollary 8. There exist EDT0L (and ET0L) languages of intermediate
growth.
5. Primitives and bases in free groups
Given an alphabet Σ, we will always assume that a tuple (w1 , . . . , wt ),
where w1 , . . . , wn ∈ Σ∗ , is encoded as a string w1 # . . . #w2 , where the symbol # is distinct from the ones contained in Σ.
A free basis of a free group is a tuple of elements that freely generate the
group, and a primitive (element) is an element that belongs to some free
basis of the group. In this section we show that the set of bases and the
set of primitives, written as reduced words over the standard free basis, is
EDT0L for free groups of rank 2, and context-sensitive for higher rank. It is
an open question whether the higher rank context-sensitive characterisation
can be lowered to indexed or E(D)T0L.
5.1. Bases and primitives in the free group F2 are EDT0L. In [27]
Silva and Weil showed that the set of primitives in the free group F2 on
generators {a, b}, written as reduced words over {a, b, a−1 , b−1 }, is contextsensitive and not context-free. In this section we show that both the set of
bases and the set of primitives are EDT0L.
Proposition 9. The set of free bases and the set of primitives in F2 , as
reduced words, are EDT0L.
Proof. It is a classical result due to Nielsen that two elements g, h ∈ F2
form a basis of F2 if and only if the commutator [g, h] is conjugate either to
6

[a, b] or [b, a]. Hence the set of bases in F2 can be seen as the values X, Y
satisfying the equations
Z[X, Y ]Z −1 = [a, b]
or
Z[X, Y ]Z −1 = [b, a]
where Z can take any value.
By Corollary 2.2 in [5], for any equation in a free group the set of solutions,
or any projections thereof, written as tuples in reduced words, is EDT0L.
In this case the values of (X, Y ) will provide the set of bases, and the values
of X the set of primitives.

5.2. Primitives in free groups of higher rank. While in F2 the set of
free bases can be expressed in terms of solutions to equations, this does
not hold in higher rank. It was shown in [21] that the set of primitives in
free groups of higher rank is not definable in the first order theory of the
group, and thus we cannot use our previous approach to give an EDT0L
characterisation in this case. Another approach is to produce the set of
primitives by applying all the maps in Aut(Fk ) to a free basis element.
Since Aut(Fk ) is finitely generated, we would apply all the maps in Aut(Fk ),
written as words over the generators of Aut(Fk ) - which can be seen as
rational control, to a basis element which would play the role of the axiom.
The set thus obtained would be EDT0L and contain all the primitives, but
neither as reduced nor unique words.
Since we are interested in establishing a formal language characterisation for primitives as reduced words, we use a different approach, based on
Stallings’ folding of labeled graphs, and an algorithm for testing primitivity
in a free group given in [6], to show here that they are context-sensitive. For
the sake of keeping this note succinct, we do not define here the Stallings
graph or what is meant by folding, but refer the reader to references such as
[28] and [20]. If Γ is the Stallings graph of a finitely generated subgroup of
a free group F , a pinch will signify the identification of two distinct vertices
of Γ.
A primitive set (as opposed to the set of primitives) in a free group F is
a set of elements that can be extended to a basis of F .
Lemma 10. [6, Theorem 4.4] Let n ≤ k and let W = {w1 , . . . , wn } be a
set of reduced words in Fk = F (X), where X = {x1 , . . . , xk }, such that for
every x ∈ X either x or x−1 appears in some w ∈ W . Let Γ be a graph
representing the subgroup of Fk generated by W . Then W is a primitive set
if and only if there is a sequence of pinches and folds, containing exactly
k − n pinches, that transforms Γ into the elementary wedge on X.
In the case that not every generator or inverse appears in the list of wi
then the Lemma 10 can still decide primitivity by taking a smaller value for
k.
7

A standard way to represent a Stallings graph Γ = (V Γ, EΓ) over an
alphabet X would be as a collection of labeled oriented edges, where an
edge γ ∈ EΓ is given as a triple (i(γ), t(γ), l(γ)), with i(γ) ∈ V Γ the initial
vertex of γ, t(γ) ∈ V Γ the terminal vertex and l(γ) ∈ X ∪ X −1 the label
of γ. Obviously, a word w ∈ F (X) can be represented by a graph Γw such
that |V Γw |, |EΓw | ≤ n, where n = |w|. However, as there might be up to
n vertices, and one needs log(n) space to encode the names of the vertices,
the naı̈ve implementation of Γ would require n log(n) space.
We propose a different representation of the Stallings graph, along with
two additional types of moves, and show that Lemma 10 can be realised by
a linear space algorithm. Instead of labelling an edge by a single symbol, we
will label edges by subwords, that is, an edge γ ∈ EΓ will be represented by
a triple (i(γ), t(γ), s(γ)), where i(γ) and t(γ) are as before and s(γ) ∈ F (X)
is a reduced word. In this case we say that Γ is a segment graph. Adapting
the terminology of Stallings graphs, we say that a segment graph Γ is folded
if it does not contain a pair of incident edges whose labels share a common
prefix or suffix. If a vertex v is incident to two edges with a common prefix
or suffix, then we say that v is unfolded, and otherwise call it folded.
Folding at a vertex v applies to segment graphs in three possible ways,
depending on whether two segments incident to v have exactly the same
label, or only common proper prefixes. More precisely, let γ1 , γ2 ∈ EΓ satisfy
i(γ1 ) = v = i(γ2 ), s(γ1 ) = uw1 and s(γ2 ) = uw2 for some u, w1 , w2 ∈ F (X).
I. If w1 = w2 = ǫ, then this is a usual folding of graphs.
II. If w1 = ǫ and w2 6= ǫ, then we split γ2 into γ2′ and γ2′′ by introducing
a new vertex v ′ on γ2 such that i(γ2′ ) = v, t(γ2′ ) = v ′ and s(γ2′ ) = u,
and fold γ1 with γ2′ as in case I.
III. If w1 , w2 6= ǫ, then we introduce a new vertex v ′ and a new edge
γ, such that i(γ) = v, t(γ) = v ′ , s(γ) = u, and replace edges γ1 , γ2
by new edges γ1′ , γ2′ such that i(γ1′ ) = v ′ = i(γ2′ ), t(γ1′ ) = t(γ1 ),
t(γ2′ ) = t(γ2 ), s(γ1′ ) = w1 and s(γ2′ ) = w2 .
Pinching a segment graph is defined as follows. Let γ, γ ′ ∈ EΓ satisfy
s(γ) = w1 w2 and s(γ ′ ) = w1′ w2′ for some w1 , w2 , w1′ , w2′ ∈ F (X). We remove
the edges γ, γ ′ , introduce new vertex v and up to four new edges γ1 , γ2 , γ1′ , γ2′
given by
γ1 :
γ2 :
γ1′ :
γ2′ :

i(γ1 ) = i(γ), t(γ1 ) = v, s(γ1 ) = w1 ;
i(γ2 ) = v, t(γ2 ) = t(γ), s(γ2 ) = w2 ;
i(γ1′ ) = i(γ ′ ), t(γ1′ ) = v, s(γ1′ ) = w1′ ;
i(γ2′ ) = v, t(γ2′ ) = t(γ ′ ), s(γ2 ) = w2′ .

If one of w1 , w2 , w1′ , w2′ is empty, i.e. when we are pinching a segment with
a vertex, we don’t need to introduce the vertex v.
Both foldings of type III and pinches can cause the numbers of edges and
vertices to increase; the resulting graph could potentially not fit on a linear
size tape, but the discussion below shows that this is not the case.
8

Recall that if Γ is a Stallings graph corresponding to some finite set W
then the core of Γ (or the core graph for hW i), is the smallest subgraph of Γ
in which we can read all the elements of hW i as reduced words along loops
based at the base vertex of Γ. In particular, if Γ is finite then the core of Γ
does not contain any vertices of degree one, with the exception of the base
vertex of Γ. The core of a segment graph is defined in an analogous manner.
Remark 1. (1) A set W = {w1 , . . . , wn } ⊆ Fk is primitive if and only if
the set W g = {gw1 g−1 , . . . , gwn g−1 } is primitive for some (and thus for all)
g ∈ Fk . As choosing a different base vertex in the core graph of hW i is
the same as taking a conjugate of hW i, we will assume that the base vertex
in any segment graph has degree at least 2. In fact, unless the graph is
homeomorphic to a loop, we may assume that the base vertex is of degree
at least three.
(2) Furthermore, as the core graph will never contain any leaves other
than the base vertex and as was already mentioned, we can always assume
that the base vertex is of degree at least two, hence without loss of generality
we may assume that the segment graph does not contain any leaves; this
can be achieved by pruning, i.e. repeatedly removing vertices of degree 1
(along with corresponding edges). Note that for finite graphs this procedure
always terminates.
We say that a segment graph Γ is topological if all its vertices have degree
≥ 3, unless it consists of a single vertex, or a loop attached at a degree
two vertex. Following Remark 1, we see that every segment graph can be
transformed into a topological one (representing a subgroup conjugate to
the original) by picking a different base vertex, pruning and merging edges:
suppose γ1 , γ2 ∈ EΓ such that t(γ1 ) = v = i(γ2 ) and deg(v) = 2; then we can
replace the edges γ1 , γ2 by a new edge γ such that i(γ) = i(γ1 ), t(γ) = t(γ2 )
and s(γ) = s(γ1 )s(γ2 ), and remove vertex v.
The following lemma implies that pruning will need to be done at most
once in the entire process corresponding to Lemma 10.
Lemma 11. Let Γ be a folded graph that does not contain any vertex of
degree 1 and let Γ′ be a graph obtained from Γ by performing a pinch and a
folding. Then Γ′ does not contain vertices of degree 1.
Proof. Suppose that there is v ′ ∈ V Γ′ such that deg(v ′ ) = 1. Without loss of
generality we may assume that v ′ is the initial vertex of its unique adjacent
edge γ ∈ EΓ′ . Note that the pinch and the subsequent folding uniquely
define a surjective morphism of graphs f : V Γ0 → V Γ′ , where Γ can be
obtained from Γ0 by merging. Note that Γ0 is folded and it does not contain
vertices of degree 1. Let v ∈ f −1 (v ′ ) be arbitrary. Again, without loss of
generality we may assume that v is the initial vertex of all of its adjacent
edges. It follows that all the edges adjacent to v must share a common
prefix with γ, meaning that v is not folded folded unless deg(v) = 1. As Γ0
is folded, deg(v) = 1 for every v ∈ f −1 (v ′ ), which contradicts the fact that
9

deg(u) > 1 for every u ∈ V Γ0 . Thus Γ′ does not contain vertices of degree
1.

The topological rank of a graph is the rank of its fundamental group.
Lemma 12. Let Γ be a finite topological graph of topological rank r with
r > 1. Then |EΓ| ≤ 3r − 3 and |V Γ| ≤ 2r − 2.
Proof. As r > 1 we see that deg(v) ≥ 3 for every v ∈ V Γ. From the Euler
characteristic
formula r = |EΓ| − |V Γ| + 1, and since in any graph 2|EΓ| =
P
deg(v)
by assumption 2|EΓ| ≥ 3|V Γ|, which gives the inequalities
v∈V Γ
above.

Remark 2. Folding does not cause the topological rank of a graph to increase, but pinching can increase it by 1.
Corollary 13. Let Γ be a finite topological segment graph of topological
rank r with a single unfolded vertex, and let Γ′ be the folded topological
graph obtained from Γ by folding, merging and pruning.
If r = 1 then |V Γ′ | = |EΓ′ | = 1, otherwise |V Γ′ | ≤ 2r − 2 and |EΓ′ | ≤
3r − 3.
Proof. Let r ′ denote the topological rank of the graph Γ′ ; note that r ′ ≤ r
by Remark 2.
If r ′ = 1 then, following the definition of topological graphs, we see that
Γ′ is a single vertex with an attached loop and |V Γ′ | = |EΓ′ | = 1.
If r ′ > 1 then the result follows by Lemma 12.

Proposition 14. Let Fk be a free group of rank k ≥ 2. Then the primitive
sets in Fk can be recognised in linear space.
Proof. We represent a graph with t edges on the tape of a Turing machine
by the string
#vi1 |vi2 |w1 ## . . . ##vi2t−1 |vi2t |wt #,
where vij are binary numbers and the factor #v|v ′ |w# represents the segment γ with i(γ) = v, t(γ) = v ′ and s(γ) = w.
On input a list of words w1 , w2 , . . . , wn , if n ≥ k we return NO, else we
write on the tape
#v0 |v0 |w1 ##v0 |v0 |w2 ## . . . ##v0 |v0 |wn #
which describes the bouquet of loops labeled wi at a vertex v0 . Let k′ be
the rank of the free group generated by the letters appearing in the wi , so
k′ ≤ k.
We perform folds of types I, II, III by modifying the tape as follows:
I. Scan the tape to find factors #vi |vj |u# and #vi |vk |u#; erase the
second factor and replace vk by vj everywhere on the tape.
II. Scan the tape to find #vi |vj |u# and #vi |vk |up#; overwrite the second factor with #vj |vk |p#.
10

III. Scan the tape to find #vi |vj |uap# and #vi |vk |ubq# with a 6= b, a, b ∈
X ±1 ; erase both factors and write #vi |v|u##v|vj |ap##v|vk |bq#
where the binary number v is some value not already in use.
For pruning we scan the tape to find a factor #v|v ′ |u# such that the v
(or v ′ ) does not appear in any other factor. If such a factor is found, we
delete it.
Similarly, for merging we scan the tape for a pair of factors #v|v ′ |u1 # and
#v ′ |v ′′ |u2 # (or #v ′′ |v ′ |u2 #) such that v ′′ does not occur in any other factor.
If such a pair is found, we replace them by #v|v ′′ |u1 u2 # (or #v|v ′′ |u1 u−1
2 #,
respectively).
We perform a pinch by choosing either:
(1) two distinct vertices vi , vj and replacing vj by vi everywhere on the
tape;
(2) a vertex v and a segment (vi , vj , w1 w2 ) with |wi | > 0 and replacing
#vi |vj |w1 w2 # by #vi |v|w1 ##v|vj |w2 #;
(3) two segments (vi , vj , w1 w2 ), (vp , vq , w3 w4 ) with |wi | > 0, and replacing their encodings by #vi |v|w1 ##v|vj |w2 ##vp |v|w3 ##v|vq |w4 #
where v is some value not already in use.
Note that folding and pruning moves decrease the number of letters appearing as labels of segments, and pinching and merging moves preserve this
number.
The procedure starts by performing folding moves I, II, III in any order exhaustively, and each folding is followed by all possible pruning and
merging. Then a pinch is applied, and the previous two steps repeat k′ − n
times.
Following Lemma 11 we see that we will only need to perform pruning
moves before the first pinch. Note that during this process, the number of
letters present in the labels might decrease. In this case we need to decrease
k′ accordingly.
Return YES if the tape contains
#v|v|ai1 ## . . . ##v|v|aik′ −n #
with all ij distinct and aij ∈ X ±1 , else return NO.
Termination of the algorithm is guaranteed since each fold strictly decreases the number of letters from X ±1 appearing on the tape as labels
of segments. The algorithm accepts precisely the primitive sets in Fk by
Remark 1 and Lemma 10.
Since the rank of all topological segment graphs considered is smaller
than the rank of the ambient free group, by Corollary 13 the number of
vertices in use at any time is at most 2k − 2, so in binary notation each
vertex requires at most log(2k − 2) space, the total number of segments is
at most 3k P
− 3, and the number of letters from X ±1 appearing on the tape
is at most ni=1 |wi | = N . Thus the amount of space required at any time
11

in the process is at most
(3k − 3)(2 log(2k − 2) + 4) +

n
X

|wi |,

i=1

which is linear in the input size.



From the proposition it follows that for every k there is a linearly bounded
Turing machine Tk which recognises primitive sets in Fk , hence we can state
the following corollary.
Corollary 15. Let Fk = F (X) be a free group over X, where |X| = k and
n ≤ k. Then
Pk,n = {w1 # . . . #wn | {w1 , . . . wn } is a primitive set in Fk }
∗
⊆ X ∪ X −1 ∪ {#}

is a context-sensitive language.
In particular, the set Pk (=Pk,1 ) of primitive elements is context-sensitive.
6. Co-word problem for Grigorchuk group is ET0L
In this section we show that the co-word problem for the Grigorchuk group
is ET0L, improving on Holt and Röver’s result in [18], where they showed
it is indexed. It is still an open question whether the co-word problem for
the Grigorchuk’s group is context-free.
6.1. Generators and the word problem. We refer the reader to [8] for
more details, here we give the essentials for our proof. Let T denote the
infinite rooted binary tree and let A = Aut(T). Note that A ≃ A≀C2 ≃ (A×
A) ⋊ C2 , where C2 = hα | α2 = 1i, so every g ∈ A can be uniquely expressed
as g = (gL , gR )αg for some gL , gR ∈ A and αg ∈ C2 . The Grigorchuk group
is G = ha, b, c, di ≤ A, where the generators a, b, c, d ∈ A are given by
a = (1, 1)α, b = (a, c)1, c = (a, d)1, d = (1, b)1.
One can easily verify that the following identities hold in G:
(1)

a2 = b2 = c2 = d2 = 1,
bc = cb = d, cd = dc = b, db = bd = c.

Starting with an arbitrary word w ∈ {a, b, c, d}∗ , one can rewrite w via the
identities in (1) to a word w′ which represents the same element in G and
does not contain any of
aa, bb, cc, dd, bc, cb, bd, db, cd, dc
as a subword. Thus w′ has the form w′ = x0 ax1 . . . xn−1 axn , where xi ∈
{1, b, c, d} for 0 ≤ i ≤ n and xi 6= 1 for 1 < i < n − 1, so we say that w′ is
alternating or reduced. Every non-trivial element g ∈ G can be represented
by a reduced word. The following remark has an analogous proof to that of
the uniqueness of reduced words in free groups (see [23, Section I.1]).
12

Remark 3. Every word w ∈ {a, b, c, d}∗ can be rewritten via the identities
in (1) to a unique reduced word.
However, not every reduced word represents a nontrivial element: the
word dadadada is reduced, yet it represents the identity in G.
Let G1 be the subgroup of G consisting of all elements that fix the first
level of T. Then |G : G1 | = 2, G1 = hb, c, d, aba, aca, adai and
aba = (c, a)1, aca = (d, a)1, ada = (d, 1)1.
Every element g ∈ G1 can be expressed as an alternating sequence g =
x0 xa1 . . . xn−1 xan , where xi ∈ {1, b, c, d} and xai ∈ {1, aba, aca, ada} for 0 ≤
i ≤ n such that xi 6= 1 if i > 0 and xai 6= 1 if i < n.
Let φL , φR : G1 → G be the group homomorphisms defined as




b
→ c,
b
→ a,








→ d,
→ a,


c
c



d
d
→ b,
→ 1,
φR :
φL :


aba
→ a,
aba
→
c,










aca → a,
aca → d,






ada → 1,
ada → b,
and define φ : G1 → G × G as φ(g) = (φL (g), φR (g)). Then φ is injective,
and |φi (w)| < 12 |w| + 1 < |w| for every reduced w ∈ {a, b, c, d}∗ representing
some element in G1 such that |w| > 1. Let LS be the set of words with an
odd number of a’s, that is,
LS = {w ∈ {a, b, c, d}∗ | |w|a ≡ 1

mod 2}.

Notice that the parity of |w|a is invariant under the rewrite rules (1). Indeed,
if w ∈ LS then w 6=G 1.
The following is the outline of the word problem algorithm in Grigorchuk’s
group (see [8, Section VIII.E] for more details and Figure 2 for an example).
We use ǫ to denote the empty string.
(1) reduce w
(2) if w = ǫ answer YES (meaning w =G 1),
(3) if w ∈ LS answer NO (meaning w 6=G 1),
(4) otherwise answer (φL (w) =G 1 and φR (w) =G 1).
Obviously, w 6=G 1 if and only if there are sequences w0 , . . . , wn ∈ {a, b, c, d}
and φ1 , . . . , φn ∈ {φL , φR } such that wn =G w, wi−1 =G φi (wi ) for i =
1, . . . , n and w0 ∈ LS . The main idea behind our grammar is to invert this
process, i.e. start with a word in w0 ∈ LS and generate a sequence of words
w1 , . . . , wn such that wi−1 =G φi (wi ).
6.2. ET0L grammar. In this subsection we introduce the ET0L grammar
used to generate the co-word problem for Grigorchuk’s group and give an
informal explanation of the roles of the corresponding tables.
13

Our grammar works over the extended alphabet
Σ = {S0 , S1 , a, b, c, d, δ, #},
where S0 is the start symbol, along with tables s, p, hL , hR , u, t and rational
control
R = s∗ {p∗ {hL , hR }u∗ t}∗ .
The process of generating words can be split in three phases. It is important to note that the second and third phase can occur multiple times, as
can be seen in Example 2.
Phase 1: Generate LS . First we generate the language LS of words with
an odd number of occurrences of a. This is done by table s, which can be
seen as the grammar version of a two state finite automaton producing the
regular language LS . We call the words in LS seeds.
(s)

Generate seeds
S0 → aS1 , bS0 , cS0 , dS0
S1 → aS0 , bS1 , cS1 , dS1 , ǫ
∗

Lemma 16. Let w ∈ {a, b, c, d}∗ . Then w ∈ LS if and only if S0 −→s w.
∗
In particular, if S0 −→s w then w 6=G 1.
Phase 2: Invert φL and φR . Once we have produced a seed w0 , we generate
a sequence of words w1 , . . . , wn such that wi−1 =G φi (wi ), and we create
wi from wi−1 by ‘inverting’ the maps φL and φR ; this is achieved via tables
hL , hR :

(hL , hR )

Invert
a →
b →
c →
d →
δ →

Invert
a →
b →
c →
d →
δ →

φL
b, c
ada
aba
aca
d

φR
aba, aca
d
b
c
ada

Table p introduces a new symbol δ, which serves as a placeholder for the
empty word that resulted from applying φL and φR (recall that φL (d) = 1,
φR (ada) = 1).

(p)

Insert
a →
b →
c →
d →

δ
a, δa, aδ
b, δb, bδ
c, δc, cδ
d, δd, dδ

Lemma 17. Let w, w′ ∈ {a, b, c, d}∗ and let i ∈ {L, R} be given. Then
∗
∗
w =G φi (w′ ) if and only if w −→p hi w′ . In particular, if w −→p hi w′ and
w 6=G 1 then w′ 6=G 1.
The proof follows immediately from an analysis of the tables.
14

Phase 3: Use group relations and insert trivial subwords. The following table
inverts the reduction process induced by the identities in (1). We introduce
the symbol # as a placeholder for the reduction process. This means that
# signifies the position of a subword that reduces to the trivial word.
Unreduce
a → a, #a, a#
b → b, #b, b#, c#d, d#c
c → c, #c, c#, b#d, d#b
d → d, #d, d#, b#c, c#b
# → #, a#a, b#b, c#c, d#d

(u)

At this stage we remove all the occurrences of the placeholder #. This is
achieved by table t:
Tidy #
# → ǫ

(t)

Lemma 18. Let w, w′ ∈ {a, b, c, d}∗ be arbitrary. Then w can be obtained
from w′ by reducing rules (induced by the identities in (1)) if and only if
∗
∗
w −→u t w′ . In particular, if w −→u t w′ and w 6=G 1 then w′ 6=G 1.
Example 2. Figure 2 demonstrates the word problem algorithm on input
bcddacbabcaa, showing it to be nontrivial.

bcddacbabcaa
φL dadad φR
1b1

b1b
1

φL

b

φR
c

a ∈ LS

Figure 2. Word problem algorithm applied to bcddacbabcaa.

This word can be obtained from our grammar as follows.
15

Phase 1:

S0 −→s aS1 −→s a

Phase 2:

a −→hL b

Phase 3:

b −→t b

Phase 2:

b −→p δb −→p δbδ −→hR dadad

Phase 3:

dadad −→u b#c#ac#bab#c −→u b#cd#dac#bab#c#
−→u b#cd#dac#bab#ca#a −→t bcddacbabcaa.

6.3. Proof that the ET0L grammar generates exactly the co-word
problem. Let L′ be the language generated by the ET0L grammar with
alphabet Σ, tables s, p, hL , hR , u, c given above and rational control
R = s∗ {p∗ {hL , hR }u∗ t}∗ .
Note that the rational control R is equivalent to s∗ {p∗ hL u∗ t, p∗ hR u∗ t}∗ .
Following Definition 3, L′ is ET0L. Now consider L = L′ ∩{a, b, c, d}∗ . As the
class of ET0L languages is closed under intersection with regular languages,
L is an ET0L language. Intersecting L′ with {a, b, c, d}∗ effectively discards
all words containing symbols S0 , S1 . With this in mind, we will assume that
we are only working with words that do not contain symbols S0 and S1 .
Combining Lemmas 16, 17 and 18 we can immediately show that our
grammar produces words that represent non-trivial elements in the group.
Lemma 19. Let w ∈ {a, b, c, d}∗ be arbitrary. If w ∈ L then w 6=G 1.
Proof. If w ∈ L then, by definition, there is a sequence of words
w0 , w1 , w1′ , . . . , wn , wn′ ∈ {a, b, c, d}∗
and a sequence of tables h1 , . . . , hn ∈ {hL , hR } such that
∗

(1) s −→s w0 ,
∗
(2) wi−1 −→p hi wi′ for i = 1, . . . , n
∗
(3) wi′ −→u c wi ,
(4) wn = w.
We use induction on n. If n = 0 then by Lemma 16 we see that w0 ∈ LS ,
hence w0 6=G 1.
Now suppose that the result has been established for all words that can be
obtained via sequences of length ≤ n − 1. Then wn−1 6=G 1 by the induction
hypothesis. Using Lemma 17 we see that wn−1 = φi (wn′ ), where φi = φL
if hi = hL and φi = φR if hi = hR , thus wn′ 6=G 1. Using Lemma 18 we
see that wn′ =G wn and hence wn 6=G 1, so w indeed represents a nontrivial
element of Grigorchuk’s group.

The next lemma establishes the completeness of our grammar.
16

Lemma 20. Let {a, b, c, d}∗ be arbitrary. If w 6=G 1 then w ∈ L.
Proof. Suppose that w 6=G 1. Following the algorithm described in Subsection 6.1 there is a sequence of words w0 , w0′ , . . . , wn , wn′ and a sequence of
maps φ1 , . . . , φn ∈ {φL , φR } such that
(1) wi is the reduced word obtained by reducing wi′ for i = 0, . . . , n,
(2) |wi |a is even for i ≥ 1 and odd for i = 0,
′
is obtained from wi by applying φi ,
(3) wi−1
′
(4) wn = w.
Again, we proceed by induction on n.
Suppose that n = 0, i.e. w0′ = w. As the parity of the number of
occurrences of the symbol a is invariant with respect to the reduction rules,
∗
we see that |w|a is odd. It follows by Lemma 16 that S0 −→s w and thus
w ∈ L.
Now suppose that the statement holds for all w′ ∈ {a, b, c, d}∗ for which
the word problem algorithm uses up to n−1 levels of recursion. In particular,
S0 −→s

∗ {p∗ h

Lu

∗ t,p∗ h

Ru

∗ t}∗

′
wn−1
.

∗

′
−→p hn wn , where hn = hL if φn = φL
Using Lemma 17 we see that wn−1
∗
and hn = hR if φn = φR . Similarly, using Lemma 18 we see that wn −→u t
∗
∗
′
−→p hn u t w and therefore w ∈ L.

wn′ . Altogether we see that wn−1

Combining Lemma 19 and Lemma 20 we see that a word w ∈ {a, b, c, d}∗
represents a nontrivial element of Grigorchuk’s group if and only if w ∈ L,
which implies the main result of this section.
Theorem 21. The co-word problem in Grigorchuk’s group is an ETOL
language.
7. ET0L languages and 3-manifold groups
The goal of this section is to prove Theorem 22, which is a strengthening
of Theorem B in [2], proved there for indexed instead of ET0L languages.
In 1996 Bridson and Gilman stated the theorem for all manifolds satisfying
the geometrisation conjecture, but since then Perelman [24] proved that all
compact 3-manifolds do, so we can state the result in full generality.
Theorem 22. Let M be a compact 3-manifold or orbifold, and let µ : Σ⋆ →
π1 M be a choice of generators. Then there exists a set of normal forms
L ⊆ Σ⋆ which satisfies the asynchronous fellow-traveler property and is an
ET0L language.
We follow in the footsteps of Bridson and Gilman, whose proof relies on (1)
closure properties of AFL languages, and (2) showing that an appropriate
set of normal forms for Z2 is ET0L. Note that standard regular normal
forms for Z2 will not produce an appropriate language of normal forms for
the extension Z2 ⋊ Z, which needs to satisfy the properties detailed in [2,
page 541].
17

For the sake of completeness we recall the relevant results on AFL languages. As in the paper of Bridson and Gilman (and much of the literature),
we will call a set of normal forms satisfying the asynchronous fellow-traveler
property a combing.
Proposition 23 ([2]). Let A be a full AFL class of languages (such as
regular, context-free, indexed, or ET0L).
(1) (Prop. 2.9) If G1 and G2 both have an asynchronous A-combing,
then so does the free product G1 ∗ G2 .
(2) (Theorem 2.16) Let G be a finitely generated group, and H a subgroup of finite index. Then G admits an asynchronous A-combing if
and only if H admits an asynchronous A-combing.
We first recall the crossing sequence κ(m, n) of Bridson and Gilman, which
gives the EDT0L normal form for Z2 . Let (m, n) ∈ Z2 have m > 0, n ≥ 0,
and consider the line l(m, n+ ) in the plane from (0, 0) to (m, n+ ), where
n+ is chosen slightly larger than n, but small enough to ensure that (1)
l(m, n+ ) does not contain any lattice points except (0, 0), and (2) there are
no lattice points in the interior of the triangle with vertices (0, 0), (m, n)
and (m, n+ ). For the line l(m, n+ ), the sequence formed by recording an
h each time a horizontal line in the plane is crossed and a v each time a
vertical line is crossed is called the crossing sequence κ(m, n). For example,
κ(2, 3) = hvhhv.
Theorem 24. The set L = {κ(m, n) | m > 0, n ≥ 0} is an EDT0L language.
That is, the indexed combing for Z2 in [2] is in fact EDT0L.
Proof. The proof only focuses on the first quadrant in Z2 , and it can be
easily extended to all of Z2 . As is described in [2], L can be generated by
starting with an arbitrary v k , k > 0, and alternately replacing all v’s by hi v
and all h’s by v j h. The EDT0L grammar thus first has to produce v k , and
then apply maps which mimic the morphisms described. Let {q, v, h} be the
extended alphabet, with q the start symbol. Let φq , φv , φh and φs be the
maps defined by φq (q) = qv, φv (v) = hv, φh (h) = vh and φs (q) = v.
Then φs φqk−1 (q) = v k generates the starting point of the crossing sequence, and then we apply any map in {φv , φh }⋆ to v k and obtain the set
L. Thus by Definition 3 the set L is an EDT0L language.

We remark that the EDT0L characterisation for the Z2 combing cannot
be lifted to Z2 ⋊Z and other more general groups, because EDT0L languages
do not form a full AFL, which is essential in several proofs in [2].
Proposition 25. Every semidirect product of the form Z2 ⋊ Z admits an
asynchronous ET0L combing.
Proof. The proof is exactly as that of Corollary 3.5 in [2]. More precisely,
let t be a generator of Z and L be the language of normal forms for Z2 from
Theorem 24. By [2, Theorem 3.1], the language L0 = {t∗ ∪ (t−1 )∗ }L is an
18

asynchronous combing of Z2 ⋊Z, and since ET0L languages are closed under
concatenation with a regular language and finite unions, we get that L0 is
ET0L.

Proof. (of Theorem 22) The work of Thurston, Epstein and Perelman implies
that any π1 M as in the hypothesis is commensurable to the free product of
an automatic group and (possibly) finite extensions of groups of the form
Z2 ⋊Z. Thus the proof follows immediately from Propositions 23 and 25. 
8. Open problems
Among the formal languages naturally appearing in group theory none is
more prominent than the word problem, that is, the set of words representing
the trivial element in a finitely generated group. Since EDT0L languages are
not closed under inverse homomorphism, a priori a group may have EDT0L
word problem for one finite generating set but not for another. However,
we do not know of any infinite group which has EDT0L word or co-word
problem for some finite generating set. Since EDT0L languages are relatively
close in complexity to context-free languages, one might wonder whether the
groups with context-free word problem have EDT0L word problem. A first
negative answer is given below.
Proposition 26. Let F be the free group of rank at least two. Then the
word problem in F is not EDT0L.
Proof. It was proved in [22] that if a language L is a context-free generator,
i.e. for every context-free language K there is a regular language RK and
a homomorphism hK such that K = hK (L ∩ RK ), then L is not EDT0L.
It follows by the Chomsky-Schützenberger representation theorem [4] that
every Dyck language on at least two letters is a context-free generator. It can
be easily seen that the word problem in Fn , the free group on n generators,
is isomorphic to Dn⋆ , the symmetric Dyck Language on n letters. It follows
that if n > 1 then the word problem in Fn is not EDT0L.

Question 8.1. Is the word problem for Z (for some or every finite generating
set) EDT0L?
A related open problem is to determine the class of groups having ET0L
word problem; a well known problem is to find a non-virtually free group
with indexed word problem, so a reasonable conjecture here is that the only
groups with ET0L word problem are virtually free.
Conjecture 8.2. A group has EDT0L word problem if and only if it is
finite. A group has ET0L word problem if and only if it is virtually free.
Acknowledgments
We would like to thank Sylvain Salvati for the EDT0L grammar used in
the proof of Proposition 7 and Michel Latteux for the outline for Proposition 26. We also thank Claas Röver for interesting discussions. Further, we
19

would like to thank the anonymous referee for suggesting several simplifications of the submitted manuscript.
The first two authors were partially supported by the Swiss National
Science Foundation grant Professorship FN PP00P2-144681/1, and by a
Follow-On grant of the International Centre of Mathematical Sciences in
Edinburgh. All authors were supported by the Australian Research Council
Discovery Project grant DP160100486.
References
[1] Peter R. J. Asveld. Controlled iteration grammars and full hyper-AFL’s. Information
and Control, 34(3):248–269, 1977.
[2] Martin R. Bridson and Robert H. Gilman. Formal language theory and the geometry
of 3-manifolds. Comment. Math. Helv., 71(4):525–555, 1996.
[3] Martin R. Bridson and Robert H. Gilman. Context-free languages of sub-exponential
growth. J. Comput. System Sci., 64(2):308–310, 2002.
[4] Noam Chomsky and Marcel P Schützenberger. The algebraic theory of context-free
languages. Studies in Logic and the Foundations of Mathematics, 35:118–161, 1963.
[5] Laura Ciobanu, Volker Diekert, and Murray Elder. Solution sets for equations over
free groups are EDT0L languages. Internat. J. Algebra Comput., 26(5):843–886, 2016.
[6] A. Clifford and R. Z. Goldstein. Sets of primitive elements in a free group. J. Algebra,
357:271–278, 2012.
[7] Karel Culik, II. On some families of languages related to developmental systems.
Internat. J. Comput. Math., 4:31–42, 1974.
[8] Pierre de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 2000.
[9] V. Diekert and M. Elder. Solutions of twisted word equations, EDT0L languages, and
context-free groups. ArXiv e-prints, January 2017. ICALP 2017.
[10] V. Diekert, A. Jeż, and M. Kufleitner. Solutions of Word Equations over Partially
Commutative Structures. ArXiv e-prints, March 2016.
[11] A. Ehrenfeucht and G. Rozenberg. On proving that certain languages are not ET0L.
Acta Informat., 6(4):407–415, 1976.
[12] Andrzej Ehrenfeucht and Grzegorz Rozenberg. On some context free languages which
are not ET0L languages. 1974.
[13] Andrzej Ehrenfeucht, Grzegorz Rozenberg, and Sven Skyum. A relationship between
ET0L and EDT0L languages. Theoretical Computer Science, 1(4):325–330, 1976.
[14] Joost Engelfriet, Erik Meineche Schmidt, and Jan van Leeuwen. Stack machines and
classes of nonnested macro languages. J. Assoc. Comput. Mach., 27(1):96–117, 1980.
[15] Robert H. Gilman. A shrinking lemma for indexed languages. Theoret. Comput. Sci.,
163(1-2):277–281, 1996.
[16] R. I. Grigorchuk and A. Machı̀. An example of an indexed language of intermediate
growth. Theoret. Comput. Sci., 215(1-2):325–327, 1999.
[17] Takeshi Hayashi. On derivation trees of indexed grammars: an extension of the
uvwxy-theorem. Publ. Res. Inst. Math. Sci., 9:61–92, 1973/74.
[18] Derek F. Holt and Claas E. Röver. Groups with indexed co-word problem. Internat.
J. Algebra Comput., 16(5):985–1014, 2006.
[19] Sanjay Jain, Alexei Miasnikov, and Frank Stephan. The complexity of verbal languages over groups. In Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science, pages 405–414. IEEE Computer Soc., Los Alamitos,
CA, 2012.
[20] Ilya Kapovich and Alexei Myasnikov. Stallings foldings and subgroups of free groups.
J. Algebra, 248(2):608–668, 2002.
20

[21] Olga Kharlampovich and Alexei Myasnikov. Definable sets in a hyperbolic group.
Internat. J. Algebra Comput., 23(1):91–110, 2013.
[22] Michel Latteux. Sur les générateurs algébriques et linéaires. Acta Inform., 13(4):347–
363, 1980.
[23] Roger C. Lyndon and Paul E. Schupp. Combinatorial group theory. Springer-Verlag,
Berlin, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89.
[24] Grigoriy Perelman. Ricci flow with surgery on three-manifolds. 2013.
https://arxiv.org/abs/math/0303109.
[25] G. Rozenberg and A. Salomaa, editors. Handbook of formal languages. Vol. 1.
Springer-Verlag, Berlin, 1997. Word, language, grammar.
[26] Grzegorz Rozenberg and Arto Salomaa. The Book of L. Springer, 1986.
[27] Pedro V. Silva and Pascal Weil. Automorphic orbits in free groups: words versus
subgroups. Internat. J. Algebra Comput., 20(4):561–590, 2010.
[28] John R. Stallings. Topology of finite graphs. Invent. Math., 71(3):551–565, 1983.
School of Mathematical and Computer Sciences, Heriot-Watt University,
Edinburgh EH14 4AS, Scotland
E-mail address: l.ciobanu@hw.ac.uk
University of Technology Sydney, Ultimo NSW 2007, Australia
E-mail address: murrayelder@gmail.com
University of Technology Sydney, Ultimo NSW 2007, Australia
E-mail address: michal.ferov@gmail.com

21

