Relative locations of subwords in free operated semigroups and Motzkin words

Shanghua ZHENG1, LI GUO1,2
1 Department of Mathematics, Lanzhou University, Lanzhou 730000, China
2 Department of Mathematics and Computer Science, Rutgers University, Newark,
NJ 07102, USA
c
Higher Education Press and Springer-Verlag Berlin Heidelberg 2014
Abstract Bracketed words are basic structures both in mathematics (such as
Rota-Baxter algebras) and mathematical physics (such as rooted trees) where
the locations of the substructures are important. In this paper, we give the
classification of the relative locations of two bracketed subwords of a bracketed
word in an operated semigroup into the separated, nested, and intersecting
cases. We achieve this by establishing a correspondence between relative
locations of bracketed words and those of words by applying the concept of
Motzkin words which are the algebraic forms of Motzkin paths.
Keywords Bracketed word, relative location, operated semigroup, Motzkin
word, Motzkin path, rooted tree
MSC 20M05, 20M99, 05E15, 16S15, 08B20
1 Introduction
As a basic property of sets, there are three relative locations of any two subsets
of a given set: separated (disjoint), nested (including), and intersecting
(overlapping). See the proof of Theorem 2.11 below for example. Similarly,
there are three relative locations of two subwords in a given word, a property
that is essential in rewriting systems (critical pairs) and Gr¨obner bases [2,8,19].
Analogous classification of relative locations of combinatorial objects, such as
Feynman graphs, plays an important role in combinatorics and physics, for
example, in the renormalization of quantum field theory [3,10,16,17].
The classification of relative locations can be quite subtle in some
structures, especially when a non-identity operator is present, such as in
differential algebras, Rota-Baxter algebras [14] and, more generally, operated
algebras [5,7,15,20]. Further by [13], free operated semigroups have natural
Received December 12, 2013; accepted April 11, 2014
Corresponding author: Li GUO, E-mail: liguo@rutgers.edu
1244 Shanghua ZHENG, Li GUO
combinatorial presentation as rooted trees which serve as the baby models for
Feynman graphs [9,17]. Considering the importance of such classification in the
study of these mathematics and physics structures, especially their Gr¨obner-
Shirshov bases (compositions and diamond lemma) [4,6], it is crucial to establish
such a classification. In this paper, we give an explicit correspondence between
relative locations of two bracketed subwords and those of Motzkin words and
subwords. As a direct consequence, we obtain the classification of the relative
locations of bracketed subwords.
We take two steps in our treatment to deal with two subtle points of
bracketed words. In Section 2, we deal with the first subtle point which is
already present in studying relative locations of two subwords in comparison
with two subsets, namely that one subword can appear at multiple locations
in a given word. The concept of a -word [7] allows us to give a unique label
to each appearance of a subword, called a placement. We then show that each
placement corresponds uniquely to a substring of the string corresponding to
the given word, converting the problem of studying subwords to that of subsets
which can be solved easily as mentioned above. The second subtle point
arise when we deal with bracketed words in Section 3 since the action of the
bracket together with the product of the word gives the bracketed words a quite
complicated structure. To resolve this difficulty, we make use of a bijection
introduced in [13] between bracketed words and a class of words called Motzkin
words on a larger set. We then show in Section 4 that this bijection preserves
the relative locations of the (bracketed) word, reducing the study of relative
locations of bracketed words to the one of words for which we can apply
Section 2.
2 Relative locations of subwords
In this section, we consider the relative locations of two subwords of a fixed
word. This serves as both the prototype and preparation for our study of the
relative locations of two bracketed subwords in later sections.
2.1 Subwords
Definition 2.1 Let Z be a set. Let M(Z) be the free monoid on Z consisting
of words in the alphabet set Z. Thus, a word is either the empty word 1 or of
the form
w = z1 · · · zn, zi ∈ Z, 1 i n.
A subword of w is defined to be a word u = 1 that is a part of w. Let S(Z) :=
M(Z)\{1} be the free semigroup on Z.
We emphasize that the empty word 1 is not taken to be a subword in this
paper.
Note that a subword u of w ∈ M(Z) may appear in w at multiple locations.
For example, for z ∈ Z, u := z appears in w := zzz at three different locations.
Relative locations of subwords in free operated semigroups and Motzkin words 1245
It is often important to be precise about the location of a subword. This is the
case, for example, in the study of rewriting systems and Gr¨obner-Shirshov bases
[2,7,15,20]. For this purpose, we need additional information for the location of
the subword u. Such information is provided by the concept of -words [7].
Definition 2.2 Let Z be a set.
(a) Let be an element not in Z. A -word on Z is a word in M(Z ∪{ }) in
which appears exactly once. The set of -words on Z is denoted by M (Z).
(b) More generally, for 1, . . . , k not in Z, denote = ( 1, . . . , k). A
-word on Z is a word in M(Z ∪{ 1, . . . , k}) in which i appears exactly once
for each i = 1, . . . , k. The set of -words is denoted by M (Z). When k = 2, it
is denoted by M 1, 2(Z).
(c) For p ∈ M (Z) and u1, . . . , uk ∈ M(Z), let
p|u1,...,uk = p| 1 →u1,..., k →uk
denote the word in M(Z) when the i in p is replaced by ui, where i = 1, . . . , k.
Now, we can be more precise on a particular appearance of a subword.
Definition 2.3 Let u,w ∈ M(Z) be words on Z. A placement of u in w (by
p) is a pair (u, p), where p is in M (Z) such that p|u = w.
Thus, (u1, p1) = (u2, p2) means u1 = u2 and p1 = p2.
Of course, u is a subword of w if there is p ∈ M (Z) such that (u, p) is
a placement of u in w. However, the usefulness of the placement notion is its
role in distinguishing different appearances of u in w. For example, the three
appearances of u = z in w = zzz are identified by the three placements (u, p1),
(u, p2), and (u, p3), where
p1 = zz, p2 = z z, p3 = zz .
The concept of a placement is also essential in determining the relative
locations of two subwords of a given word.
Example 2.4 Let Z = {x, y}, and let w = xyxyxy. Then u := xyx appears
at two locations in w and v := xy appears at three locations, as shown in the
following equation:
w = x y x
(u,p)
yxy =
(v,q1)
xy
(v,q2)
xy
(v,q3)
xy .
Take (u, p) to be the first appearance (from the left) of u in w. Thus, p = yxy.
Then the three placements of v = xy in w, given by (v, qi), i = 1, 2, 3, with
q1 = xyxy, q2 = xy xy, q3 = xyxy .
These three placements of v are in three different kinds of relative locations
with respect to u: the left v (in (v, q1)) is a subword of u, the middle v (in
1246 Shanghua ZHENG, Li GUO
(v, q2)) is not a subword of u but has a nonempty intersection with u, and the
right v (in (v, q3)) is disjoint with u.
This situation can again be made precise by -words.
Definition 2.5 Let w be a word in M(Z). Two placements (u1, p1) and
(u2, p2) are called
(a) separated if there exists an element p in M 1, 2(Z) such that
w = p|u1,u2, p1| 1 = p| 1,u2, p2| 2 = p|u1, 2 ;
(b) nested if there exists an element p in M (Z) such that p1 = p2|p or
p2 = p1|p;
(c) intersecting if there exist an element p in M (Z) and elements a, b, and
c in S(Z) such that
(i) either w = p|abc, p1 = p| c, p2 = p|a ;
(ii) or w = p|abc, p1 = p|a , p2 = p| c.
Example 2.6 With the w, u and the three appearances of v in Example
2.4, we have the corresponding placements (u, p) with p = yxy, and (v, q1),
(v, q2), and (v, q3). Then (u, p) and (v, q1) (resp. (v, q2), (v, q3)) are nested (resp.
intersecting, separated).
2.2 Substrings
We now give another description of a placement of a subword that makes it
easier to classify the relative locations of two subwords. Denote
[n] := {1, . . . , n}, [i, k] := {i, . . . , k}, n,i 1, k i.
Let Z be a set. Let
w = z1 · · · zn, zi ∈ Z, 1 i n,
be a word in M(Z). Let p := (u, p) be a placement of u in w. Then p is of the
form
p = x1 · · · xj xj+1 · · · xm, xi ∈ Z, 1 i m,
and
u = y1 · · · yt, yj ∈ Z, 1 j t.
Comparing
x1 · · · xjy1 · · · ytxj+1 · · · xm = p|u = w = z1 · · · zn
in the free monoid M(Z), we obtain
p = z1 · · · zj−1 zk+1 · · · zn
for unique j = jp and k = kp. Thus,
u = zj · · · zk.
Relative locations of subwords in free operated semigroups and Motzkin words 1247
Definition 2.7 With notations as above, the set Ip := [jp, kp] is called the
location of the placement p = (u, p) in w. Denote
LO(w) := {[j, k] | 1 j k n}. (1)
Also denote
PL(w) := {(u, p) | (u, p) is a placement in w}. (2)
Proposition 2.8 Let 1 = w ∈ M(Z). The map
η : PL(w) → LO(w),
p = (u, p) → [jp, kp],
is a bijection.
Proof Let w = z1 · · · zn. Given a placement (u, p) in w. Then
p = z1 · · · zj−1 zk+1 · · · zn ∈ M (Z), u= zj · · · zk, 1 j k n.
Thus, if p1 = (u1, p1) and p2 = (u2, p2) are in PL(w) and p1 = p2, then we
have p1 = p2. Hence, either jp1
= jp2 or kp1
= kp2 . Then
η(u1, p1) = η(u2, p2).
Hence, η is injective.
Furthermore, for any [j, k] ∈ LO(w), define
u = zj · · · zk, p= z1 · · · zj−1 zk+1 · · · zn.
Then we have p|u = w and η(u, p) = [j, k]. Hence, η is surjective.
Definition 2.9 Two nonempty subsets I and J of [n] are called
(a) separated, if I ∩ J = ∅;
(b) nested, if I ⊆ J or J ⊆ I;
(c) intersecting, if I ∩ J = ∅, I ⊆ J and J ⊆ I.
Consider the w, u, and v in Example 2.4 and their corresponding placements
(u, p), (v, q1), (v, q2), and (v, q3) in Example 2.6. The locations of the placements
are
η(u, p) = [1, 3], η(v, q1) = [1, 2], η(v, q2) = [3, 4], η(v, q3) = [5, 6].
Then we see that, as subsets of [6], [1, 3] and [1, 2] (resp. [3, 4], [5, 6]) are
also nested (resp. intersecting, separated). The next theorem shows that this
equivalence holds in general.
Theorem 2.10 Let Z be a set. Let 1 = w = z1 · · · zn be in M(Z), where
zi ∈ Z, 1 i n. Then placements p1 = (u1, p1) and p2 = (u2, p2) in w are
1248 Shanghua ZHENG, Li GUO
separated (resp. nested, intersecting) if and only if the corresponding subsets Ip1
and Ip2 of [n] are separated (resp. nested, intersecting).
Proof First, suppose that the placements (u1, p1) and (u2, p2) in w are
separated. Then there exists an element p in M 1, 2(Z) such that
w = p|u1,u2, p1| 1 = p| 1,u2, p2| 2 = p|u1, 2 .
From p|u1,u2 = z1 · · · zn, there are 1 j1 k1 < j2 k2 n such that
p = z1 · · · zj1−1 1 zk1+1 · · · zj2−1 2 zk2+1 · · · zn,
or
p = z1 · · · zj1−1 2 zk1+1 · · · zj2−1 1 zk2+1 · · · zn.
Thus, we have
{Ip1, Ip2
} = {[j1, k1], [j2, k2]},
and hence,
Ip1
∩ Ip2 = ∅.
Conversely, suppose Ip1
∩ Ip2 = ∅. Let
Ip1 = [j1, k1], Ip2 = [j2, k2].
Then we have k1 < j2 or k2 < j1. Without loss of generality, assume k1 < j2.
Then take
u1 = zj1
· · · zk1, u2 = zj2
· · · zk2.
Define
p = z1 · · · zj1−1 1 zk1+1 · · · zj2−1 2 zk2+1 · · · zn.
Then we have
w = p|u1,u2, p1| 1 = p| 1,u2, p2| 2 = p|u1, 2 ,
as needed.
Next, suppose that (u1, p1) and (u2, p2) are nested. Then there exists an
element p in M (Z) such that p1 = p2|p or p2 = p1|p. Without loss of generality,
we can assume p1 = p2|p. From w = p1|u1 and w = p2|u2 , we obtain
z1 · · · zj1−1 zk1+1 · · · zn = p1 = p2|p = z1 · · · zj2−1 |pzk2+1 · · · zn.
Thus, j2 j1 k1 k2, and hence, Ip1
⊆ Ip2 . Conversely, suppose that Ip1
and Ip2 are nested. We may assume that
Ip1 = [j1, k1] ⊆ Ip2 = [j2, k2].
Then define
p = zj2
· · · zj1−1 zk1+1 · · · zk2 ,
Relative locations of subwords in free operated semigroups and Motzkin words 1249
with the convention that
p =

zk1+1 · · · zk2, j1 = j2,
zj2
· · · zj1−1 , k1 = k2.
We have p2|p = p1. Hence, (u1, p1) and (u2, p2) are nested.
Finally, suppose that (u1, p1) and (u2, p2) are intersecting. Then there exist
p in M (Z) and a, b, c in S(Z) such that
w = p|abc, p1 = p| c, p2 = p|a ,
or
w = p|abc, p1 = p|a , p2 = p| c.
We just need to consider the first case since the proof of the second case is
similar. Denote
p = z1 · · · zj−1 zk+1 · · · zn.
From
z1 · · · zj1−1 zk1+1 · · · zn = p1 = p| c = z1 · · · zj−1 czk+1 · · · zn,
we obtain
j1 =j c= zk1+1 · · · zk.
Since c = 1, we have k1 < k. Similarly, from
z1 · · · zj2−1 zk2+1 · · · zn = p2 = p|a = z1 · · · zj−1a zk+1 · · · zn,
we obtain
k2 = k, a = zj · · · zj2−1.
Since a = 1, we have j < j2. Consequently,
w = p|abc = z1 · · · zj−1abczk+1 · · · zn = z1 · · · zj2−1bzk1+1 · · · zn.
Since b = 1, we have j2 k1. Then
j1 = j < j2 k1 < k = k2.
Thus,
Ip1
∩ Ip2 = [j2, k1] = ∅, Ip1
\Ip2 = [j1, j2 − 1] = ∅, Ip2
\Ip1 = [k1 + 1, k2] = ∅.
Hence,
Ip1 Ip2, Ip2 Ip1 .
Thus, Ip1 and Ip2 are intersecting.
Conversely, suppose that
Ip1
∩ Ip2
= ∅, Ip1
⊆ Ip2, Ip2
⊆ Ip1.
1250 Shanghua ZHENG, Li GUO
From Ip1
∩ Ip2
= ∅, we have j1 k2 and j2 k1. Then from Ip1
⊆ Ip2
and Ip2
⊆ Ip1, we have k1 > k2 and j1 > j2, or k1 < k2 and j1 < j2. We
just consider the first case with the second case being similar. Then we have
j2 < j1 k2 < k1. Define
p = z1 · · · zj2−1 zk1+1 · · · zn,
a = zj2
· · · zj1−1, b= zj1
· · · zk2, c= zk2+1 · · · zk1.
Then we have
a, b, c = 1, w= p|abc, p2 = p| c, p1 = p|a .
This shows that (u1, p1) and (u2, p2) are intersecting.
The following result is the classification of the relative locations of two
placements in the free monoid M(Z). Its generalization to operated monoids
will be treated in the subsequent sections.
Theorem 2.11 Let w = 1 be a word in M(Z). For any two placements p1 =
(u1, p1) and p2 = (u2, p2) in w, exactly one of the following is true:
(a) (u1, p1) and (u2, p2) are separated;
(b) (u1, p1) and (u2, p2) are nested;
(c) (u1, p1) and (u2, p2) are intersecting.
Proof Let
w = z1 · · · zn, z1, . . . , zn ∈ Z, n 1.
By Theorem 2.10, we only need to prove that the same conclusion holds for Ip1
and Ip2. But this follows from the simple fact that, for the two subsets Ip1 and
Ip2 of [n], exactly one of the following is true:
(a) Ip1 and Ip2 have empty intersection (⇐⇒ Ip1 and Ip2 are separated);
(b) Ip1 and Ip2 have nonempty intersection, and Ip1
⊆ Ip2 or Ip2
⊆ Ip1 (⇐⇒
Ip1 and Ip2 are nested); or
(c) Ip1 and Ip2 have nonempty intersection, and Ip1
⊆ Ip2 and Ip2
⊆ Ip1
(⇐⇒ Ip1 and Ip2 are intersecting).
3 Bracketed words and Motzkin words
We recall the concepts of bracketed words and Motzkin words [1,13,15,18] before
generalizing Theorem 2.11 to this context.
3.1 Bracketed words
We first recall the concept and construction of free operated monoids, following
[13,15].
Definition 3.1 An operated monoid is a monoid U together with a map
P : U → U. A morphism from an operated monoid U with a map P : U → U
Relative locations of subwords in free operated semigroups and Motzkin words 1251
to an operated monoid V with a map Q: V → V is a monoid homomorphism
f : U → V such that f ◦ P = Q ◦ f.
Definition 3.2 A free operated monoid on a set Y is an operated monoid
(UY , PY ) together with a map jY : Y → UY with the property that, for any
operated monoid (V,Q) and any map f : Y → V, there is a unique morphism
f : (UY , PY ) → (V,Q) of operated monoids such that f = f ◦ jY .
For any set Y, let
Y := {
y | y ∈ Y } denote a set indexed by, but disjoint
from Y. Let X be a given set. We will construct a direct system {Mn :=
Mn(X)}n 0 of monoids with natural embeddings in−1 : Mn−1 → Mn for n 1
by induction on n. The free operated monoid M(X) on X is the direct limit of
the system, after we equip it with a natural operator.
First, let M0 := M(X). Then define the monoid
M1 := M(X ∪
M0 ) = M(X ∪
M(X) )
and denote the natural embedding of monoids induced by the inclusion X →
X ∪
M0 by
i
0 : M0 = M(X) → M(X ∪
M0 ) = M1.
Inductively assuming that Mn and in−1 : Mn−1 → Mn have been defined
for n 1, we define the monoid
Mn+1 := M(X ∪
Mn ). (3)
From the embedding of monoids in−1 : Mn−1 → Mn, we have an embedding

Mn−1 →
Mn . By the freeness of Mn = M(X ∪
Mn−1 ), we obtain a
natural embedding of monoids:
i
n : Mn = M(X ∪
Mn−1 ) → M(X ∪
Mn ) = Mn+1.
This completes our inductive definition of the direct system. Let
M(X) :=

n 0
Mn = lim −→
Mn
be the direct limit of the system. We note that M(X) is a monoid. By taking
direct limit on both sides of Mn = M(X ∪
Mn−1 ), we obtain
M(X) = M(X ∪
M(X) ), (4)
whose elements are called bracketed words.
The depth of f ∈ M(X) is defined to be
depth(f) := min

n



f ∈ Mn

. (5)
The following result shows that M(X) is the equivalence of free monoids in the
category of operated monoids.
1252 Shanghua ZHENG, Li GUO
Lemma 3.3 [13] Define the map
  : M(X) → M(X) by taking w ∈ M(X) to

w . Let jX : X → M(X) be the natural embedding. Then the triple (M(X),
  ,
jX) is the free operated monoid on X.
By [13, Theorem 4.2], another representation of free operated semigroups is
given by rooted trees. See [9,17] for the application of rooted trees in quantum
field theory.
3.2 Motzkin words
We now recall the definition of Motzkin words [1,12,18], which acquired its name
since it encodes Motzkin paths [11]. Motzkin words give another construction
of free operated monoids [13] and in this paper serve as the bridge between
bracketed words and the usual words.
Let X be a set. Let

 and be symbols not in X.
Definition 3.4 An element of the free monoid M(X ∪ {

, }) is called a
Motzkin word on X if it has the properties that
(a) the number of

 in the word equals the number of in the word;
(b) counting from the left, the number of occurrence of

 is always greater
or equal to the number of occurrence of .
The set of all Motzkin words is denoted by W (X).
Example 3.5 Let x, y, z be elements in X.
(a) The word



x

y z is a Motzkin word.
(b) The word

x

yz is not a Motzkin word since it does not satisfy the
first property.
(c) The word x

y

z is not a Motzkin word since it does not satisfy the
second property.
Define
P : W (X) → W (X),
m →

m .
Then W (X) is an operated monoid.
Theorem 3.6 [13, Theorem 3.4] Let Y be a set. Let
φ := φY : M(Y ) → W (Y ), φ(u) = u, u ∈ Y,
be the homomorphism of operated monoid defined by the universal property of
the free operated monoid M(Y ). Then φ is an isomorphism.
3.3 -bracketed words and -Motzkin words
Let X be a set. For k 1, let 1, . . . , k be distinct symbols not in X, and let
= ( 1, . . . , k).
Denote
X = X ∪ { 1, . . . , k}.
Relative locations of subwords in free operated semigroups and Motzkin words 1253
Definition 3.7 A -bracketed word on X is defined to be a bracketed word
in the operated monoid M(X ) with exactly one occurrence of i for each
i = 1, . . . , k. The set of all -bracketed words on X is denoted by M (X).
When k = 1 and 2, we denote M (X) by M (X) and M 1, 2(X), respectively.
Definition 3.8 For q ∈ M (X) and s1, . . . , sk ∈ M(X), we define
q| s := q|s1,...,sk (6)
to be the bracketed word in M(X) obtained by replacing the letter i in q by
si for 1 i k. An (s1, . . . , sk)-bracketed word on X is a bracketed word of
the form Eq. (6) for some q ∈ M (X).
We next introduce the concept of a -Motzkin word on X.
Definition 3.9 A word in M(X ∪ {

, }) is called a -Motzkin word on X
if it is in the intersection M (X ∪{

, }) ∩W (X ) or, more precisely, if it has
the properties that
(a) the number of

 in the word equals the number of in the word;
(b) counting from the left, the number of occurrence of

 is always greater
or equal to the number of occurrence of ;
(c) for each 1 i k, the letter i appears exactly once in the word.
The set of all -Motzkin words is denoted by W (X).
Taking Y = X in Theorem 3.6, we obtain
Corollary 3.10 There is a unique isomorphism
φX : M(X ) → W (X )
of operated monoids such that
φX (a) = a, ∀ a ∈ X .
In particular, φX ( i) = i for 1 i k.
Proposition 3.11 The isomorphism φX restricts to a bijection
φ : M (X) → W (X).
Proof Since the bijection φX sends i to i, 1 i k, an element w ∈ M(X )
is in M (X) if and only if φX (w) ∈ W (X ) is in W (X).
4 Relative locations in bracketed words and Motzkin words
In this section, we first define the relative locations of bracketed words and
Motzkin words by using -bracketed words and -Motzkin words in Section 4.1.
1254 Shanghua ZHENG, Li GUO
The relationship between the two kinds of relative locations is established in
Section 4.2 and is used to prove the main theorem in Section 4.3.
4.1 Placements in bracketed words and Motzkin words
Definition 4.1 Let X be a set. Let f, s be in M(X). A placement of s in f
(by q) is a pair p := (s, q) with q ∈ M (X) such that f = q|s. We then call s a
bracketed subword of f.
The relative locations between two placements in a bracketed word can now
be defined in the same way as those in an ordinary word.
Definition 4.2 Two placements (s1, q1) and (s2, q2) in f ∈ M(X) are called
(a) separated, if there exists an element q in M 1, 2(X) such that
q1| 1 = q| 1,s2, q2| 2 = q|s1, 2, f= q|s1,s2;
(b) nested, if there exists an element q in M (X) such that q1 = q2|q or
q2 = q1|q;
(c) intersecting, if there exist an element q in M (X) and elements a, b, c
in M(X)\{1} such that either
(i) f = q|abc, q1 = q| c, q2 = q|a ; or
(ii) f = q|abc, q1 = q|a , q2 = q| c.
A bracketed word s might appear in a bracketed word f with multiple
placements with different relative locations with respect to another bracketed
subword.
Example 4.3 Let
f =

abc ab ∈ M(X).
Let s1 =
abc and let s2 = ab. Then we obtain the placements (s1, q1), (s2, q21),
and (s2, q22), where
q1 =
ab , q21 =

c ab , q22 =

abc .
Then the placements (s1, q1) and (s2, q21) are nested since q21 = q1|q, where
q =
c . However, the placements (s1, q1) and (s2, q22) are separated.
We next describe the relative locations of two placements of bracketed words
in terms of Motzkin words. By Definition 3.4, we obtain the following result.
Lemma 4.4 Let u be in W (X), and let p be in W (X). Then p|u is in W (X).
Taking Z = X ∪ {

, } in Definition 2.3, we have the following definition.
Definition 4.5 Let w and u be Motzkin words in W (X). A placement of u
in w (by p) is a pair (u, p) with p ∈ W (X) such that p|u = w. We then call u
a Motzkin subword of w.
By Definition 3.4, the set W 1, 2(X) of ( 1, 2)-Motzkin words is a subset
of M 1, 2(X ∪ {

, }). Thus, as a special case of Definition 2.5, we obtain the
Relative locations of subwords in free operated semigroups and Motzkin words 1255
definition of two placements (u1, p1) and (u2, p2) in w being separated or nested
or intersecting.
4.2 Relationship between relative locations
We now establish the relationship between placements in bracketed words and
placements in Motzkin words.
Proposition 4.6 Let X be a set, and let { 1, . . . , k} be symbols not in X.
Let φ: M(X) → W (X) be the isomorphism of operated monoids in Theorem
3.6, and let φ : M (X) → W (X) be the bijection in Proposition 3.11.
(a) Let q ∈ M (X) and s1, . . . , sk ∈ M(X). Then
φ(q|s1,...,sk) = φ (q)|
φ(s1),...,φ(sk).
(b) Let p ∈ W (X) and u1, . . . , uk ∈ W (X). Then
φ
−1(p|u1,...,uk) = φ
−1
(p)|
φ−1(u1),...,φ−1(uk).
Proof (a) We prove a more general result. Define
M
(X) := {q ∈ M(X ) | for each 1 i k, i appears at most once in q}
⊆ M(X ).
For q ∈ M
(X) and s1, . . . , sk ∈ M(X), define q|s1,...,sk to be the bracketed word
by replacing the i in q, if there is any, by si, 1 i k. Thus, in particular,
q|s1,...,sk =

q|s1, q∈ M 1 (X),
q, q ∈ M(X).
In general, q|s1,...,sk = q|si1 ,...,sim if only i1, . . . , im from { 1, . . . , k} appear in
q.
Similarly, define
W
(X) := {p ∈ W (X ) | for each 1 i k, i appears at most once in p}
⊆ W (X ),
and define p|u1,...,uk for p ∈ W
(X) and u1, . . . , uk ∈ W (X).
With these notations, if q is in M
(X) and q = q1q2 with q1, q2 ∈ M
(X),
then we have
q| s = q1| s q2| s.
Furthermore, the bijection φX in Corollary 3.10 restricts to a bijection
φ : M
(X) → W
(X)
by the same argument as Proposition 3.11.
1256 Shanghua ZHENG, Li GUO
Claim 4.7 Let q ∈ M
(X) and s1, . . . , sk ∈ M(X). Then
φ(q|s1,...,sk) = φ (q)|
φ(s1),...,φ(sk).
Proof We prove the claim by induction on the depth of q ∈ M
(X) defined in
Equation (5).
If the depth of q is 0, then q ∈ M
(X), and hence,
q = z1 i1 z2 i2
· · · zm im zm+1
with z1, . . . , zm+1 ∈ M(X) and i1, . . . , im
∈ { 1, . . . , k}. Then we have
φ(q| s) = φ(z1si1
· · · zmsimzm+1)
= φ(z1)φ(si1) · · · φ(zm)φ(sim)φ(zm+1)
= φ (q)|
φ( s),
as needed. Here, we have used the abbreviations
s = (s1, . . . , sk), φ( s) = (φ(s1), . . . , φ(sk)).
Assume that the claim has been proved for q ∈ M
(X) with depth less or
equal to n 0 and consider a q with depth n + 1.
Note that φ and φX (and hence φ ) are multiplicative. Thus, for q = q1q2
with q, q1, q2 ∈ M
(X), if we can prove that
φ(qi| s) = φ (qi)|
φ( s), i= 1, 2,
then we also have
φ(q|
s) = φ(q1|
s)φ(q2|
s)
= φ (q1)|
φ( s) φ (q2)|
φ( s)
= (φ (q1)φ (q2))|
φ( s)
= φ (q)|
φ( s).
Therefore, we only need to complete the induction when q is of depth n+1 and
is indecomposable in M
(X), that is, q is not the product of two elements in
M
(X) ⊆ M(X ) = M(X ∪
M(X ) )
(see Eq. (4)). Then q is either in X ∪ { 1, . . . , k} or is of the form
q with
q ∈ M
(X). In the first case, q is of depth 0 and has been proved above. In the
second case, q has depth n. Note that φ and φ (and hence φ ) are compatible
Relative locations of subwords in free operated semigroups and Motzkin words 1257
with the brackets. Therefore, together with the induction hypothesis, we have
φ(q| s) = φ(
q | s)
= φ(
q| s )
=
φ( q| s)
=
φ ( q)|
φ( s)

= (
φ ( q) )|
φ( s)
= (φ (
q ))|
φ( s)
= φ (q)|
φ( s).
This completes the inductive proof of the claim.
Then (a) is a special case of Claim 4.7 since the restriction of φ to M (X)
is φ .
(b) Denote
u = (u1, . . . , uk), φ
−1( u) = (φ
−1(u1), . . . , φ
−1(uk)).
By (a) and the bijectivity of φ and φ , we have
φ
−1(p| u) = φ
−1(φ (φ
−1
(p))|
φ(φ−1( u)))
= φ
−1(φ(φ
−1
(p)|
φ−1( u)))
= φ
−1
(p)|
φ−1( u).
This is what we need.
By Proposition 4.6, we immediately have the following results.
Corollary 4.8 Let f be in M(X). Then (s, q) is a placement of s in f if and
only if (φ(s), φ (q)) is a placement of φ(s) in φ(f) ∈ W (X).
Proof The pair (s, q) is a placement of s in f if and only if f = q|s, which
holds if and only if φ(f) = φ (q)|
φ(s), which holds if and only if (φ(s), φ (q)) is
a placement of φ(s) in φ(f).
Corollary 4.9 Let q1, q2, and q be -bracketed words in M (X). Then q1 =
q2|q if and only if φ (q1) = φ (q2)|
φ (q) in W (X).
Proof To be precise, denote the isomorphism and the bijection in Proposition
4.6, in the case of k = 1, by
φ := φX : M(X) → W (X), φ 1 := φX, 1 : M 1(X) → W 1(X).
Also denote X := X ∪ { }, where is a symbol not in X ∪ { 1}. Then
φX |
M (X) = φX, .
1258 Shanghua ZHENG, Li GUO
Let q1, q2, q ∈ M (X) be given. Define
q

2 := q2| → 1
∈ M 1(X) ⊆ M 1(X
).
We also have
q1, q ∈ M (X) ⊆ M(X
).
Then q1 = q2|q means q1 = q
2
|q in M(X ). Then applying Proposition 4.6 (a)
to the set X with k = 1, we have
φ (q1) = φX, (q1) = φX (q1) = φX (q

2
|q) = φX , 1(q

2)|
φX
(q) = φ 1(q

2)|
φ (q).
But q
2
| = q2, so
φ 1(q

2)|
φ (q) = φ (q2)|
φ (q).
Hence,
φ (q1) = φ (q2)|
φ (q).
Conversely, if φ (q1) = φ (q2)|
φ (q), then we have
φ (q1) = φ 1(q

2)|
φ (q),
where q
2 = q2| 1 . Then with the notations as above, applying Proposition 4.6
(b), we have
q1 = φ
−1
(φ (q1)) = φ
−1
(φ 1(q

2)|
φ (q)) = φ
−1
1 (φ 1 (q

2))|
φ
−1
(φ (q)) = q

2
|q = q2|q.

Theorem 4.10 Let f be a bracketed word in M(X). Let (s1, q1) and (s2, q2)
be placements in f. Then
(a) the pairs (s1, q1) and (s2, q2) are separated in f if and only if the pairs
(φ(s1), φ (q1)) and (φ(s2), φ (q2)) are separated in φ(f);
(b) the pairs (s1, q1) and (s2, q2) are nested in f if and only if the pairs
(φ(s1), φ (q1)) and (φ(s2), φ (q2)) are nested in φ(f);
(c) the pairs (s1, q1) and (s2, q2) are intersecting in f if and only if the
pairs (φ(s1), φ (q1)) and (φ(s2), φ (q2)) are intersecting in φ(f).
Proof Let (s1, q1) and (s2, q2) be placements in f. Then by Corollary 4.8,
(φ(s1), φ (q1)) and (φ(s2), φ (q2)) are placements in φ(f).
(a) The placements (s1, q1) and (s2, q2) in f are separated if and only if
there exists an element q in M 1, 2(X) such that
q1| 1 = q| 1,s2, q2| 2 = q|s1, 2, f= q|s1,s2.
By Proposition 4.6, this is so if and only if
φ (q1)| 1 = φ 1, 2(q)|
1,φ(s2), φ (q2)| 2 = φ 1, 2(q)|
φ(s1), 2 ,
φ(f) = φ 1, 2(q)|
φ(s1),φ(s2).
(7)
Relative locations of subwords in free operated semigroups and Motzkin words 1259
If this is true, then (φ(s1), φ (q1)) and (φ(s2), φ (q2)) are separated in φ(f).
Conversely, if the placements (φ(s1), φ (q1)) and (φ(s2), φ (q2)) are separated
in φ(f), then there exists an element p in W 1, 2(X) such that
φ (q1)| 1 = p|
1,φ(s2), φ (q2)| 2 = p|
φ(s1), 2, φ(f) = p|
φ(s1),φ(s2).
Since
φ 1, 2 : M 1, 2(X) → W 1, 2(X)
is bijective, there is q ∈ M 1, 2(X) such that φ 1, 2(q) = p. Thus, Eq. (7) holds,
and hence, (s1, q1) and (s2, q2) are separated in f.
(b) The placements (s1, q1) and (s2, q2) are nested in f if and only if there
exists an element q in M (X) such that q1 = q2|q or q2 = q1|q. By Corollary
4.9, this holds if and only if
φ (q1) = φ (q2)|
φ (q) or φ (q2) = φ (q1)|
φ (q). (8)
If this is true, then (φ(s1), φ (q1)) and (φ(s2), φ (q2)) are nested. Conversely,
if (φ(s1), φ (q1)) and (φ(s2), φ (q2)) are nested, then there is p ∈ W (X) such
that
φ (q1) = φ (q2)|p or φ (q2) = φ (q1)|p.
Since φ : M (X) → W (X) is bijective, there is q ∈ M (X) such that φ (q) =
p. Thus, Eq. (8) holds, and hence, (s1, q1) and (s2, q2) are nested in f.
(c) The placements (s1, q1) and (s2, q2) are intersecting in f if and only if
there exist q in M (X) and a, b, c in M(X)\{1} such that
f = q|abc, q1 = q| c, q2 = q|a ,
or
f = q|abc, q1 = q|a , q2 = q| c.
By Theorem 3.6, Proposition 4.6, and Corollary 4.9, this is so if and only if
φ(f) = φ (q)|
φ(a)φ(b)φ(c), φ (q1) = φ (q)|
φ(a) , φ (q2) = φ (q)|
φ(c), (9)
or
φ(f) = φ (q)|
φ(a)φ(b)φ(c), φ (q1) = φ (q)|
φ(c), φ (q2) = φ (q)|
φ(a) . (10)
If this is true, then (φ(s1), φ (q1)) and (φ(s2), φ (q2)) are intersecting since
φ(a), φ(b), φ(c) = 1.
Conversely, if (φ(s1), φ (q1)) and (φ(s2), φ (q2)) are intersecting in φ(f),
then there exist p in W (X) and α, β, γ in W (X)\{1} such that
φ(f) = p|αβγ, φ (q1) = φ (q)|α , φ (q2) = φ (q)| γ ,
or
φ(f) = p|αβγ, φ (q1) = φ (q)| γ, φ (q2) = φ (q)|α .
1260 Shanghua ZHENG, Li GUO
By the bijectivity of φ and φ , there are q ∈ M (X) and a, b, c ∈ M(X)\{1}
such that
p = φ (q), α= φ(a), β= φ(b), γ= φ(c).
Then Eq. (9) or (10) hold. This shows that (s1, q1) and (s2, q2) are intersecting
in f.
4.3 Relative locations of bracketed subwords
Now, we are ready to prove our main theorem on the classification of relative
locations of two bracketed subwords (placements) in a bracketed word.
Theorem 4.11 (Main Theorem) Let f be a bracketed word in M(X). For any
two placements (s1, q1) and (s2, q2) in f, exactly one of the following is true:
(a) (s1, q1) and (s2, q2) are separated;
(b) (s1, q1) and (s2, q2) are nested;
(c) (s1, q1) and (s2, q2) are intersecting.
Proof By Theorem 2.11, the statement of the theorem holds when (s1, q1) and
(s2, q2) are replaced by the two placements (φ(s1), φ (q1)) and (φ(s2), φ (q2))
in the word
φ(f) ∈ W (X) ⊆ M(X ∪ {

, }).
Then by Theorem 4.10, the statement holds for (s1, q1) and (s2, q2).
Acknowledgements The authors thank the Kavli Institute for Theoretical Physics China
and the Morningside Center for Mathematics in Beijing for their hospitality and support.
This work was supported by the National Natural Science Foundation of China (Grant
Nos. 11201201, 11371178), the Fundamental Research Funds for the Central Universities
(lzujbky-2013-8), and the National Science Foundation of US (Grant No. DMS 1001855).
References
1. Alonso L. Uniform generation of a Motzkin word. Theoret Comput Sci, 1994, 134:
529–536
2. Baader F, Nipkow T. Term Rewriting and All That. Cambridge: Cambridge Univ
Press, 1998
3. Bogner C, Weinzierl S. Blowing up Feynman integrals. Nucl Phys B Proc Suppl, 2008,
183: 256–261
4. Bokut L A, Chen Y Q, Chen Y S. Composition-Diamond lemma for tensor product of
free algebras. J Algebra, 2010, 323: 2520–2537
5. Bokut L A, Chen Y Q, Deng X, Gr¨obner-Shirshov bases for Rota-Baxter algebras. Sib
Math J, 2010, 51: 978–988
6. Bokut L A, Chen Y Q, Li Y. Gr¨obner-Shirshov bases for categories. In: Operads and
Universal Algebra. Singapore: World Scientific Press, 2012, 1–23
7. Bokut L A, Chen Y Q, Qiu J. Greobner-Shirshov bases for associative algebras with
multiple operators and free Rota-Baxter algebras. J Pure Appl Algebra, 2010, 214:
89–110
8. Buchberger B. An algorithm for finding a basis for the residue class ring of a zerodimensional
polynomial ideal. Ph D Thesis, University of Innsbruck, Austria, 1965 (in
German)
Relative locations of subwords in free operated semigroups and Motzkin words 1261
9. Connes A, Kreimer D. Hopf algebras, renormalization and concommutative geometry.
Comm Math Phys, 1998, 199: 203–242
10. Connes A, Kreimer D. Renormalization in quantum field theory and the Riemann-
Hilbert problem. I. The Hopf algebra structure of graphs and the main theorem.
Comm Math Phys, 2000, 210: 249–273
11. Donaghey R, Shapiro L W. Motzkin numbers. J Combin Theory Ser A, 1977, 23: 291–
301
12. Flajolet P. Mathematical methods in the analysis of algorithms and data structures.
In: Trends in Theoretical Computer Science (Udine, 1984). Principles Comput Sci Ser
12. Rockville: Computer Sci Press, 1988, 225–304
13. Guo L. Operated semigroups, Motzkin paths and rooted trees. J Algebraic Combin,
2009, 29: 35–62
14. Guo L. An Introduction to Rota-Baxter Algebra. Beijing/Boston: Higher Education
Press/International Press, 2012
15. Guo L, Sit W, Zhang R. Differential type operators and Gr¨obner-Shirshov bases.
J Symbolic Comput, 2013, 52: 97–123
16. Krajewski T, Wulkenhaar R. On Kreimer’s Hopf algebra structure of Feynman graphs.
Eur Phys J C, 1999, 7: 697–708
17. Kreimer D. On overlapping divergences. Comm Math Phys, 1999, 204: 669–689
18. Sapounakis A, Tsikouras P. On k-colored Motzkin words. J Integer Seq, 2004, 7:
Article 04. 2.5.
19. Shirshov A I. Some algorithmic problem for ˚A-algebras. Sibirsk Mat Zh, 1962, 3: 132–
137
20. Zheng S, Gao X, Guo L, Sit W. Rota-Baxter type operators, rewriting systems and
Gr¨obner-Shirshov bases. Preprint