arXiv:1702.02926v2 [cs.FL] 1 Sep 2017

THE WORD PROBLEM OF Zn IS A MULTIPLE
CONTEXT-FREE LANGUAGE
MENG-CHE “TURBO” HO
Abstract. The word problem of a group G = hΣi can be defined as the set of
formal words in Σ∗ that represent the identity in G. When viewed as formal
languages, this gives a strong connection between classes of groups and classes
of formal languages. For example, Anisimov showed that a group is finite if and
only if its word problem is a regular language, and Muller and Schupp showed
that a group is virtually-free if and only if its word problem is a context-free
language. Above this, not much was known, until Salvati showed recently that
the word problem of Z2 is a multiple context-free language, giving first such
example. We generalize Salvati’s result to show that the word problem of Zn
is a multiple context-free language for any n.

1. Introduction
Fixing an alphabet set Σ, the set of finite strings in Σ is denoted by Σ∗ =
{a1 a2 · · · an | n ∈ N, ai ∈ Σ}. Any subset of Σ∗ is called a formal language.
As an attempt to analyze natural languages, Chomsky [Cho56] introduced the
Chomsky-Schützenberger hierarchy, which includes regular, context-free, contextsensitive, and recursively enumerable languages, each one a larger class than the
former. In this paper, we will be focusing on multiple context-free languages, another
generalization of context-free languages introduced by Seki et al [SMFK91].
There are many ways to associate formal languages to a group. Indeed, for a
group G generated by a finite set Σ = Σ−1 , we define its word problem W (G) to
be the subset of Σ∗ consisting of all strings that represent the identity element of
G. Note that the language (and even the set of alphabets) depends on the choice
of generating set. However, we will see that this dependence is negligible for the
languages we are interested in here.
There had been various work associating classes of languages and classes of
groups via word problems. Anı̄sı̄mov [Anı̄71] showed that G is finite if and only if
W (G) is regular. Muller and Schupp showed that G is virtually free if and only if
W (G) is context-free. Indeed, they showed the following stronger theorem:
Theorem 1 (Muller, Schupp [MS83]). For a finitely generated group G, the following are equivalent:
(1) G is virtually free.
(2) W (G) is context-free.
Date: September 5, 2017.
The material is based upon work supported by the National Science Foundation under Grant
No. DMS-1440140 while the author was in residence at the Mathematical Sciences Research
Institute in Berkeley, California, during the Fall 2016 semester.
1

2

MENG-CHE “TURBO” HO

(3) There exists a constant K such that every closed path in the Cayley graph
of G can be triangulated by chords with length ≤ K.
Recently, Salvati [Sal15] showed that the word problem of Z2 is a 2-multiple
context-free language, giving first such example. In the proof, he used some geometric methods that seems to be specific to the two-dimensional case. Naderhof
[Ned16] gave a shorter proof of Salvati’s result, avoiding some of the pieces that are
two-dimensional specific. In this paper, by using a topological lemma from Burago
[Bur92], we also avoid the geometric pieces and are able to generalize Silvati’s theorem and show that the word problem of Zn is multiple context-free:


Theorem 2. The word problem W (Zn ) is an (8 n+1
− 2)-multiple context-free
2
language for every n.
However, this yields that W (Z2 ) is a 6-multiple context-free language, which is
slightly weaker than Salvati’s result which says that W (Z2 ) is a 2-multiple contextfree language. Thus, one natural question will be improving our result to get the
following conjecture proposed by Nederhof:
Conjecture 3 (Nederhof [Ned17]). For any n, the language W (Zn ) is n-multiple
context-free.
In the same paper, Nederhof also showed that W (Zn ) is not a K-multiple contextfree language for any K < n, so this conjecture is indeed sharp.
To end the introduction, we propose the following open problem that may be
interesting to group theorists. For more recent progress on this topic, the reader
may also want to see [GKS] and [KS].
Question 4. For which finitely-generated groups G is W (G) multiple context-free?
This paper is organized as follows: We give the necessary definition and background in section 2. We then set up our notation and introduce the main lemma
in section 3. Finally we show the main Theorem in section 4.
2. Definition and background
We follow [SMFK91] and [Ned17] to give the definition of multiple context-free
grammars:
Definition 5. A K-multiple context-free grammar is a tuple (Σ, N, S, P ), where Σ
is the set of terminals, N is the set of non-terminals, S ∈ N is the start symbol,
and P is the set of production rules, such that:
• Each non-terminal I(x1 , x2 , . . . , xm ) has an associated natural number m ≤
K, its arity.
• The arity of S is 1.
• Each of the production rule is of the following form for some p ≥ 0:
p
2
1
)
), · · · , Ip (y1p , . . . , ym
), I2 (y12 , . . . , ym
I0 (x1 , x2 , . . . , xm0 ) ← I1 (y11 , y21 , . . . , ym
p
2
1

where Ii has arity mi , each xi is a word in the variables yjl and the terminals
Σ, and each of yjl shows up at most once in all of x1 , x2 , . . . , xn .
An instance of a production rule or non-terminal is obtained by replacing the
occurance(s) of each variable by a string in Σ∗ . A sequence of rule instances is valid
if every non-terminal instances on the right hand side of some rule instances in the

THE WORD PROBLEM OF Zn IS A MULTIPLE CONTEXT-FREE LANGUAGE

3

sequence already appears on the left hand side of some rule instances earlier in the
sequence. We say a sequence ends in a non-terminal instance if it is the left hand
side of the last rule instance in the sequence.
We say a grammar admits a string s in Σ∗ if there is a valid sequence of rule
instances, called a derivation, ending in S(s). We say a grammar produces the
language which is the collection of all strings in Σ∗ that it admits.
Definition 6. A language is called K-multiple context-free if it can be produced by
some K-multiple context-free grammar. A language is called multiple context-free
if it is K-multiple context-free for some K.
Example 7. Consider the 2-multiple context-free grammar with terminals a, b, c, d,
a binary non-terminal I = I(x, y), the start symbol S = S(x), and production rules
I(ǫ, ǫ) ←
I(axb, cyd) ← I(x, y)
S(xy) ← I(x, y).
Then the following is a derivation for an bn cn dn :
I(ǫ, ǫ) ←
I(ab, cd) ← I(ǫ, ǫ)
I(a2 b2 , c2 d2 ) ← I(ab, cd)
..
.
I(an bn , cn dn ) ← I(an−1 bn−1 , cn−1 dn−1 )
S(an bn cn dn ) ← I(an bn , cn dn )
Indeed, this is the only kind of strings this grammar admits, so the language
produced by this grammar is {an bn cn dn | n ≥ 0}.
The class of multiple context-free languages is a cone [SMFK91] in the sense of
[GKS]. A well-known consequence of being a cone is the following theorem from
[GKS], which we only state in the case of multiple context-free languages:
Theorem 8. Let W (G) be the word problem of G with respect to a fixed generating
set Σ. Suppose W (G) is multiple context-free. Then
(1) The word problem of G is multiple context-free with respect to any generating set of G.
(2) The word problem of any finitely-generated subgroup of G is multiple contextfree.
(3) The word problem of any supergroup of G of finite index is multiple contextfree.

4

MENG-CHE “TURBO” HO

3. Notations and main lemma
For any curve α in Rn , we will write α to be the displacement vector of α, and
|α| to be the length of α. Note that when α is the curve on the Cayley graph of
Zn corresponding to a word w, α is just the image of the word w in Zn and |α| is
just the length of the word. We also write αβ to mean the concatenation of the
two curves α and β.
We will need the following lemma by Burago to prove the main theorem. We
include the proof here for completeness.
Lemma 9 (Burago [Bur92]). Let α(t) : [0, 1] → Rn be a continuous curve. Then
there exist [t1 , s1 ], [t2 , s2 ], . . . , [tk , sk ] such that 0 ≤ t1 ≤ s1 ≤ t2 ≤ s2 ≤ · · · ≤ tk ≤
sk ≤ 1 with k = [ n+1
2 ] and
k
X

(α(si ) − α(ti )) =

i=1

1
(α(1) − α(0)).
2

Proof. We will construct an odd map f : S n → Rn . For x = (x1 , x2 , . . . , xn+1 ) ∈
S n ⊂ Rn , we write y0 = 0, y1 = x21 , y2 = x21 + x22 , . . . , yn+1 = x21 + · · · + x2n+1 = 1.
We define
n+1
X
f (x) =
sign(xi )(α(yi ) − α(yi−1 )).
i=1

One checks that f is indeed an odd map, and since every odd map from S n → Rn
has a zero, we can pick some x ∈ S n such that f (x) = 0. Then one of {[yi−1 , yi ] |
xi > 0} and {[yi−1 , yi ] | xi < 0} satisfies the condition, by possibly attaching some
empty intervals in the end.

Remark 10. One sees that k = [ n+1
2 ] is sharp by considering the curve along the
edges of an n-cube.
4. Proof of the main Theorem
We restate and prove the main Theorem. To make the proof clearer, we shall
suppress the embedding when talking about curves.


Theorem 2. The word problem W (Zn ) is an (8 n+1
− 2)-multiple context-free
2
language for every n.
Proof. We will denote the standard generators of Zn by a1 , a2 , . . . , an , and their
inverses by A
1 , A2 , .. . , An .
n+1
and m = 8k − 2. We consider the m-multiple context-free
Let k =
2
grammar with terminals Σ = {a1 , A1 , a2 , A2 , . . . , An }, an m-ary non-terminals I =
I(x1 , x2 , . . . , xm ), start symbol S = S(x), and production rules
S(x1 x2 · · · xm ) ← I(x1 , x2 , . . . , xm )
I(ǫ, ǫ, . . . , ǫ) ←
I(a1 , A1 , ǫ, ǫ, . . . , ǫ) ←
I(a2 , A2 , ǫ, ǫ, . . . , ǫ) ←
..
.
I(an , An , ǫ, ǫ, . . . , ǫ) ←

THE WORD PROBLEM OF Zn IS A MULTIPLE CONTEXT-FREE LANGUAGE

5

I(z1 , z2 , . . . , zm ) ← I(x1 , x2 , . . . , xm ), I(xm+1 , xm+2 , . . . , x2m )
for every σ ∈ Sym(2m) and z1 z2 · · · zm = xσ(1) xσ(2) · · · xσ(2m) .
By the very first production rule, it suffices to show that x1 x2 · · · xm ∈ W (Zn )
if and only if there is a valid sequence ending in I(x1 , x2 , . . . , xm ). The if direction follows immediately from the definition of the production rules and commutativity of Zn . To show the only if direction, we will induct on the length
of x1 x2 · · · xm ∈ W (Zn ). The base cases where |x1 · · · xm | ≤ m are straight forward. Now suppose |x1 · · · xm | > m. We may assume that x1 x2 · · · xm/2 6= 0
and xm/2+1 xm/2+2 · · · xm 6= 0, otherwise we may apply induction hypothesis on
x1 x2 · · · xm/2 = 0 and xm/2+1 xm/2+2 · · · xm = 0.
Now for every i, we write vi to be the curve in Rn that represents xi , which is
contained in the Cayley graph of Zn . Applying Lemma 9 to the curve v1 · · · vm/2 ,
we get 2k points on the curve, breaking the curve into 2k + 1 pieces u0 , u1 , . . . , u2k ,
with

(1)

i=k
X

u2i−1

i=1

i=2k
i=k
X
1 X
=
ui =
u2i .
2 i=0
i=0

Applying Lemma 9 to the curve vm/2+1 · · · vm in the same way, we get
(2)

i=k
X

u′2i−1 =

i=1

i=k
i=2k
1 X ′ X ′
ui =
u2i .
2 i=0
i=0

Claim. We may choose the endpoints of all the ui ’s and u′i ’s to be either on lattice
points, or mid-lattice points, i.e. the midpoints of two adjacent lattice points.
Proof. Fix ui ’s and u′i ’s that has the fewest number of endpoints not being a lattice
point or a mid-lattice point. Suppose the claim is false, then there is some endpoint
x that is not a lattice point or a mid-lattice point. Without loss, say this is an
endpoint of ui , and its first coordinate is not a multiple of 21 . This forces all its
other coordinates to be integral, as u1 u2 · · · um is a curve contained in the lattice
Zn .
But each coordinate of the middle term of (1) is a multiple of 12 , thus there must
be another endpoint y of some uj (possibly with i = j) whose first coordinate is
also not a multiple of 12 . Now depending on how x and y appear in (1), either we
may replace x by x + δe1 and y by y + δe1 and still keep (1), or we may replace x
by x + δe1 and y by y − δe1 and still keep (1). Say we are in the first case, then
choose the smallest positive δ that makes x + δe1 or y + δe1 a multiple of 21 , and
replace x and y correspondingly. This gives another choice of ui ’s and u′i ’s which
has at least one fewer endpoint not being a lattice point or a mid-lattice point, a
contradiction.

Now, the 2k points together with the endpoints of vi ’s, which are lattices points
′
by definition, give a refinement w1 , w2 , . . . , wm/2+2k and w1′ , w2′ , . . . , wm/2+2k
of the
′
ui ’s and ui ’s. Notice that some of these may be empty curves if some of these points
coincide. Now rewriting (1) and (2) in terms of wi ’s and wi′ ’s, we get
X
i∈S

wi =

i=m/2
X
1 X
xi =
wi
2 i=1
i∈S

6

MENG-CHE “TURBO” HO

X

wi′ =

i∈T

1
2

i=m
X

xi =

i=m/2+1

X

wi′

i∈T

for some S, T ⊂ {1, 2, . . . , m/2 + 2k}, and S = {1, 2, . . . , m/2 + 2k} \ S, T =
{1, 2, . . . , m/2 + 2k} \ T . Notice that since wi ’s and wi′ ’s are refinements of ui ’s and
u′i ’s, so we have |S|, |T |, |S|, |T | ≥ k. Without loss, we will assume that |S| ≥ |S|,
and |T | ≤ |T |. Thus |S|, |T | ≤ m/2 + 2k − k = 5k − 1, and |S|, |T | ≤ (m/2 +
2k)/2 = 3k − 1/2, so |S|, |T | ≤ 3k − 1. Hence |S| + |T | ≤ 8k − 2 = m, and
|S| + |T | ≤ 8k − 2 = m.
i=m
P
Now observe that
xi = 0 by the assumption that x1 x2 · · · xm ∈ W (Zn ). Thus

we have
(3)

i=1

X
i∈S

wi +

X
i∈T

wi′ =

X
i∈S

wi +

X

wi′ = 0.

i∈T

Claim. There is a partition {wi | 1 ≤ i ≤ m/2 + 2k} of v1 v2 · · · vm/2 and {wi′ | 1 ≤
i ≤ m/2 + 2k} of vm/2+1 · · · vm which is a refinement of xi ’s such that:
(a) This partition satisfies (3).
(b) Not all curves in the first part of (3) are empty. Also, not all curves in the
second part of (3) are empty.
(c) All endpoints are lattice points.
Proof. The previous construction gives a partition satisfying (a) with every endpoint being either a lattice point or a mid-lattice point. It also satisfies (b) by (1)
and (2) and the assumption that x1 x2 · · · xm/2 6= 0.Thus, we may choose a partition
satisfying (a) and (b) whose endpoints are either a lattice point or a mid-lattice
point, with fewest number of endpoints being a mid-lattice point. Supposing the
claim is false, let x be an endpoint that is a mid-lattice point. If both of the curves
adjacent to it are in the same sum, we may simply replace x to one of the closest
lattice point, which reduces the number of endpoints being a mid-lattice point in
our partition while still satisfying (a) and (b), a contradiction.
Now without loss, we may assume x is adjacent to w1 and w2 , with 1 ∈ S and
2∈
/ S, and assume x is not integral in the first coordinate, with all other coordinates
being integral. Note that in this case x contributes positively to the first part of
(3), and negatively to the second part of (3). As the sums equal to 0, there must
be another endpoint y which is also not integral in the first coordinate. By the
argument in the previous paragraph, the two curves adjacent to y cannot be in the
same sum. Thus, similar to the case of x, y must contribute to either the first or
second part of (3) positively, and the other part negatively.
We now replace x with x + 21 e1 and y with y ± 12 e1 , depending on whether y
contributes positively or negatively to the second part of (3). This new partition
still satisfies (a). If this replacement breaks (b), say all curves in the first part of
(3) are empty, then this replacement must have reduced the total length of curves
in the first part of (3) by 1. So, we may instead replace x with x − 21 e1 and y with
y ∓ 21 e1 , and increase the the total length of curves in the first part of (3) by 1, while
reducing the total length of the second part by 1. However, as the total length of
all curves are > m, this second replacement will satisfy (b).
Either case, this will replace the mid-lattice points x and y by lattice points,
thus reducing the number of mid-lattice points of the partition. So we have a new

THE WORD PROBLEM OF Zn IS A MULTIPLE CONTEXT-FREE LANGUAGE

7

partition satisfying (a) and (b) but has fewer endpoints being a mid-lattice point,
a contradiction.

Now we finally get a partition on which (3) holds and all its endpoints are lattice
points. Thus, each part of the partition actually represent a word in Zn . We shall
write y1 , y2 , . . . , ym to be the words given by {wi | i ∈ S} and {wi′ | i ∈ T }, and
z1 , z2 , . . . , zm to be the words given by {wi | i ∈
/ S} and {wi′ | i ∈
/ T }.PWe let
m
yP
j = ǫ for j > |T | + |S|, and zk = ǫ for k > |T | + |S|. Then, (3) says that
0 yi =
m
0 zi = 0 and condition (b) ensures that |y1 · · · ym |, |z1 · · · zm | < |x1 · · · xm |. Thus
by induction hypothesis we have two valid sequences ending in I(y1 , y2 , . . . , ym )
and I(z1 , z2 , . . . , zm ), respectively. Since yi ’s and zi ’s is a refinement of xi ’s, there
is also an instance of one of the last production rules that combines the yi ’s and
zi ’s back to xi ’s. Concatenating the two sequences with this production rule will
give a valid sequence ending in I(x1 , x2 , . . . , xm ). This completes the proof.

We finish with the following corollary by combining our main Theorem with
Theorem 8 to get a more general statement.
Corollary 11. The word problem of any finitely-generated virtually-abelian group
is multiple context-free.
References
[Anı̄71]

A. V. Anı̄sı̄mov, The group languages, Kibernetika (Kiev) (1971), no. 4, 18–24.
MR 0301981
[Bur92]
D. Yu. Burago, Periodic metrics, Representation theory and dynamical systems,
Adv. Soviet Math., vol. 9, Amer. Math. Soc., Providence, RI, 1992, pp. 205–210.
MR 1166203
[Cho56]
Noam Chomsky, Three models for the description of language, IRE Transactions on
information theory 2 (1956), no. 3, 113–124.
[GKS]
Robert H. Gilman, Robert P. Kropholler, and Saul Schleimer, Groups whose word
problems are not semilinear, in preperation.
[KS]
Robert P. Kropholler and Davide Spiriano, The class of groups with mcf word problem
is closed under free products, in preparation.
[MS83]
David E. Muller and Paul E. Schupp, Groups, the theory of ends, and context-free
languages, J. Comput. System Sci. 26 (1983), no. 3, 295–310. MR 710250
[Ned16]
M.-J. Nederhof, A short proof that o2 is a mcfl, Proceedings of the 54th Annual Meeting of the Annual Meeting of the Association for Computational Linguistics (2016),
no. 1117-1126.
, Free word order and mcfls, From Semantics to Dialectometry: Festschrift for
[Ned17]
John Nerbonne (2017), 273–282.
[Sal15]
Sylvain Salvati, MIX is a 2-MCFL and the word problem in Z2 is captured by the
IO and the OI hierarchies, J. Comput. System Sci. 81 (2015), no. 7, 1252–1277.
MR 3354791
[SMFK91] Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami, On multiple
context-free grammars, Theoretical Computer Science 88 (1991), no. 2, 191–229.

