Relative locations of subwords in free operated semigroups and Motzkin words

Front. Math. China 2015, 10(5): 1243–1261
DOI 10.1007/s11464-014-0379-1

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