The Word Problem for Omega-Terms
over the Trotter-Weil Hierarchy∗

arXiv:1509.05364v2 [cs.FL] 16 May 2017

Manfred Kufleitner† and Jan Philipp Wächter
Institut für Formale Methoden der Informatik
University of Stuttgart, Germany
{kufleitner,jan-philipp.waechter}@fmi.uni-stuttgart.de

May 17, 2017

Abstract. For two given ω-terms α and β, the word problem for ω-terms
over a variety V asks whether α = β in all monoids in V. We show that the
word problem for ω-terms over each level of the Trotter-Weil Hierarchy is decidable. More precisely, for every fixed variety in the Trotter-Weil Hierarchy,
our approach yields an algorithm in nondeterministic logarithmic space (NL).
In addition, we provide deterministic polynomial time algorithms which are
more efficient than straightforward translations of the NL-algorithms. As
an application of our results, we show that separability by the so-called corners of the Trotter-Weil Hierarchy is witnessed by ω-terms (this property is
also known as ω-reducibility). In particular, the separation problem for the
corners of the Trotter-Weil Hierarchy is decidable.

1 Introduction
Algebraic characterizations of classes of regular languages are interesting as they often allow to decide the class’s membership problem. For example, by Schützenberger’s famous
theorem [22], one can decide whether a given regular language is star-free by computing
its syntactic monoid M and checking its aperiodicity. The latter can be achieved by
verifying x|M |! = x|M |! x for all x ∈ M . This equation is also stated as xω = xω x since
this notation is independent of the monoid’s size. More formally, we can see the equation
as a pair of ω-terms: these are finite words built using letters, which are interpreted as
variables, concatenation and an additional formal ω-power. Checking an equation α = β
∗
†

The final publication is available at Springer via http://dx.doi.org/10.1007/s00224-017-9763-z.
The first author was supported by the German Research Foundation (DFG) under grants DI 435/5-2
and KU 2716/1-1.

1

in a finite monoid is easy: one can simply substitute each variable by all elements of the
monoid. For each substitution, this yields a monoid element on the left hand side and
one on the right hand side. The equation holds if and only if they are always equal.
Often, the question whether an equation holds is not only interesting for a single finite
monoid but for a (possibly infinite) class of such monoids. For example, one may ask
whether all monoids in a certain class are aperiodic. This is trivially decidable if the
class is finite. But what if it is infinite? If the class forms a variety (of finite monoids,
sometimes also referred to as a pseudo-variety), i. e. a class of finite monoids closed
under (possibly empty) direct products, submonoids and homomorphic images, then this
problem is called the variety’s word problem for ω-terms. Usually, the study of a variety’s
word problem for ω-terms also gives more insight into the variety’s structure, which is
interesting in its own right. McCammond showed that the word problem for ω-terms of
the variety A of aperiodic finite monoids is decidable [17]. The problem was shown to be
decidable in linear time for J, the class of J -trivial finite monoids, by Almeida [3] and
for R, the class of R-trivial monoids, by Almeida and Zeitoun [4]. For the variety DA,
Moura adapted and expanded those ideas to show decidability in time O((nk)5 ) where
n is the length of the input ω-terms and k is the maximal nesting depth of the ω-power
(which can be linear in n) [18]. Remember that DA is the class of finite monoids whose
regular D-classes form aperiodic semigroups. This variety received a lot of attention due
to its many different characterizations; see e.g. [5, 26]. Most notably is its connection to
two-variable first-order logic [27]. This logic is a natural restriction of first-order logic
over finite words, which in turn is the logic characterization of A.
In this paper, we consider the word problem for ω-terms over the varieties in the
Trotter-Weil Hierarchy. It was introduced by Trotter and Weil [28] with the idea of
using the good understanding of the band varieties (cf. [7]) for studying the lattice of
sub-varieties of DA; bands are semigroups satisfying x2 = x. The levels of this hierarchy
exhaust DA. As it turns out, the Trotter-Weil Hierarchy has tight connections to the
quantifier alternation hierarchy inside two-variable first-order logic [14]. In addition,
many characterizations of DA admit natural restrictions which allow climbing up this
hiearchy (see [12]).
Please note that, in spite of this paper’s title, we will refer to ω-terms as π-terms
for most parts of the paper, the only exception being this introduction. We follow this
notation introduced by Perrin and Pin [19] to avoid notational conflicts. Accordingly, we
use π for the formal power in π-terms and speak of the word problem for π-terms.
Results. In this paper, we present the following results.
• Our main tool for studying a variety V of the Trotter-Weil Hierarchy is a family
of finite index congruences ≡V,n for n ∈ N. These congruences have the property
that a monoid M is in V if and only if there exists n for which M divides a
quotient by ≡V,n . The congruences are not new but they differ in some details
from the ones usually found in the literature, where they are introduced in terms
of rankers [12, 14, 15]. Unfortunately, these differences necessitate new proofs.
• We lift the combinatorics from finite words to ω-terms using the “linear order
approach” introduced by Huschenbett and the first author [10]. They showed that,
2

over varieties of aperiodic monoids, one can use the order N + Z · Q + (−N) for the
formal ω-power. In this paper, we use the simpler order N + (−N). We show that
two ω-terms α and β are equal in some variety V of the Trotter-Weil Hierarchy
if and only if JαKN+(−N) ≡V,n JβKN+(−N) for all n ∈ N. Here, JαKN+(−N) denotes
the generalized word (i. e. the labeled linear order) obtained from replacing every
occurrence of the formal ω-power by the linear order N + (−N). Note that this
order is tailor-made for the Trotter-Weil Hierarchy and does not result from simple
arguments which work in any variety.
• We show that one can effectively check whether JαKN+(−N) ≡V,n JβKN+(−N) for all
n ∈ N.
• We further improve the algorithms and show that, for every variety V of the
Trotter-Weil Hierarchy, the word problem for ω-terms over V is decidable in nondeterministic logarithmic space. The main difficulty is to avoid some blow-up which
(naively) is caused by the nesting depth of the ω-power. For R, which appears
in the hierarchy, this result is incomparable to Almeida and Zeitoun’s linear time
algorithm [4].
• We also introduce polynomial time algorithms, which are more efficient than the
direct translation of these NL algorithms.
• As an application, we prove that the separation problems for the so-called corners
of the Trotter-Weil Hierarchy are decidable by showing ω-reducibility. For J, we
adapt the proof of van Rooijen and Zeitoun [29].
• With little additional effort, we also obtain all of the above results for DA, the
limit of the Trotter-Weil Hierarchy. The decidability of the separation problem
re-proves a result of Place, van Rooijen and Zeitoun [21]. The algorithms for the
word problem for ω-terms are more efficient than those of Moura [18].
Separability of the join levels and the intersection levels is still open. We conjecture
that these problems can be solved with similar but more technical reductions.

2 Preliminaries
Natural Numbers and Finite Words. Let N = {1, 2, . . . }, N0 = {0, 1, . . . } and −N =
{−1, −2, . . . }. For the rest of this paper, we fix a finite alphabet Σ. By Σ∗ , we denote
the set of all finite words over the alphabet Σ, including the empty word ε; Σ+ denotes
Σ∗ \ {ε}.
Order Types. A linearly ordered set (P, ≤P ) consists of a (possibly infinite) set P and
a linear ordering relation ≤P of P , i. e. a reflexive, anti-symmetric, transitive and total
binary relation ≤P ⊆ P × P . To simplify notation we define two special objects −∞ and
+∞. The former is always smaller with regard to ≤P than any element in P while the

3

latter is always larger. We call two linearly ordered sets (P, ≤P ) and (Q, ≤Q ) isomorphic
if there is an order-preserving bijection ϕ : P → Q. Isomorphism between linearly order
sets is an equivalence relation; its classes are called (linear) order types.
The sum of two linearly ordered sets (P, ≤P ) and (Q, ≤Q ) is (P ⊎ Q, ≤P +Q ) where
P ⊎ Q is the disjoint union of P and Q and ≤P +Q orders all elements of P to be smaller
than those of Q while it behaves as ≤P and ≤Q on elements from their respective sets.
Similarly, the product of (P, ≤P ) and (Q, ≤Q ) is (P × Q, ≤P ∗Q ) where (p, q) ≤P ∗Q (p̃, q̃)
holds if and only if either q ≤Q q̃ and q 6= q̃ or q = q̃ and p ≤P p̃ holds. Sum and
product of linearly ordered sets are compatible with taking the order type. This allows
for writing µ + ν and µ ∗ ν for order types µ and ν.
We re-use n ∈ N0 to denote the order type of ({1, 2, . . . , n}, ≤). One should note
that this use of natural numbers to denote order types does not result in contradictions
with sums and products: the usual calculation rules apply. Besides finite linear order
types, we need ω, the order type of (N, ≤), and its dual ω ∗ the order type of (−N, ≤).
Another important order type in the scope of this paper is ω + ω ∗ , whose underlying set
is N ⊎ (−N). Note that, here, natural numbers and the (strictly) negative numbers are
ordered as 1, 2, 3, . . . , . . . , −3, −2, −1; therefore, in this order type, we have for example
−1 ≥ω+ω∗ 1.
Generalized Words. Any finite word w = a1 a2 . . . an of length n ∈ N0 with ai ∈ Σ can
be seen as a function which maps a position i ∈ {1, 2, . . . , n} to the corresponding letter
ai (or, possibly, the empty map). Therefore, it is natural to denote the positions in a
word w by dom(w). By relaxing the requirement of dom(w) to be finite, one obtains the
notion of generalized words: a (generalized) word w over the alphabet Σ of order type µ
is a function w : dom(w) → Σ, where dom(w) is a linearly ordered set in µ. For dom(w),
we usually choose (N, ≤), (−N, ≤) and (N ⊎ (−N), ≤ω+ω∗ ) as representative of ω, ω ∗ and
ω + ω ∗ , respectively. The order type of a finite word of length n is n.
Like finite words, generalized words can be concatenated, i. e. we write u to the left
of v and obtain uv. In that case, the order type of uv is the sum of the order types of
u and v. Beside concatenation, we can also take powers of generalized words. Let w be
a generalized word of order type µ which belongs to (Pµ , ≤µ ) and let ν be an arbitrary
order type belonging to (Pν , ≤ν ). Then, wν is a generalized word of order type µ ∗ ν
which determines the ordering of its letters; w maps (p1 , p2 ) ∈ Pµ × Pν to w(p1 ). If ν = n
for some n ∈ N, then wν = wn is equal to the n-fold concatenation of w.
In this paper, the term word refers to a generalized word. If it is important for a word
to be finite, it is referred to explicitly as a finite word. As a counterpart to the positions
dom(w) in w, we define the set of letters appearing in a word alph(w) as the image of w
seen as a function. For example, for a finite word w = a1 a2 . . . an of length n ∈ N0 (with
a1 , a2 , . . . , an ∈ Σ), we have alph(w) = {a1 , a2 , . . . , an }.
We also introduce notation for factors of words. For a pair (l, r) ∈ ({−∞}⊎ dom(w))×
(dom(w) ⊎ {+∞}), define w(l,r) as the restriction of the word w (seen as a mapping) to
the set of positions (strictly) larger than l and (strictly) smaller than r. Note that
w = w(−∞,+∞) and w(l,r) = ε for any pair (l, r) with no position between l and r.

4

Monoids, Divisors, Congruences and Recognition. In this paper, the term monoid
refers to a finite monoid (except when stated otherwise). It is well known that, for any
monoid M , there is a smallest number n ∈ N such that mn is idempotent (i. e. m2n = mn )
for every element m ∈ M ; this number is called the exponent of M and shall be denoted
by M ! = n.1 A monoid N is a divisor of (another) monoid M , written as N ≺ M , if N
is a homomorphic image of a submonoid of M .
A congruence (relation) in a (not necessarily finite) monoid M is an equivalence relation
C ⊆ M × M such that x1 C x2 and y1 C y2 implies x1 y1 C x2 y2 for all x1 , x2 , y1 , y2 ∈ M .
If M is a (possibly infinite) monoid and C ⊆ M × M is a congruence, then the set of
equivalence classes of C, denoted by M/C, is a well-defined monoid (which might still be
infinite), whose size is called the index of C. For any two congruences C1 and C2 , one can
define their join C1 ∨ C2 as the smallest congruence which includes C1 and C2 ; its index
is at most as large as the index of C1 and the index of C2 .
A (possibly infinite) monoid M recognizes a language (of finite words) L ⊆ Σ∗ if there
is a homomorphism ϕ : Σ∗ → M with L = ϕ−1 (ϕ(L)). A language is regular if and only
if it is recognized by a finite monoid. It is well known that there is a unique smallest
monoid which recognizes a given regular language: the syntactic monoid.
Green’s Relations. Among the most important tools for studying monoids are Green’s
Relations. Let x and y be elements of a monoid M . Define
x R y ⇔ xM = yM,
x L y ⇔ Mx = My

and

x J y ⇔ M xM = M yM
where xM = {xm | m ∈ M } is the right-ideal of x, M x = {mx | m ∈ M } its left-ideal
and M xM = {m1 xm2 | m1 , m2 ∈ M } its (two-sided) ideal.
By simple calculation, one can see that x R y holds if and only if there are z, z ′ ∈ M
such that xz = y and yz ′ = x and, symmetrically, that x L y holds if and only if there
are z, z ′ ∈ M such that zx = y and z ′ y = x.
Varieties, π-Terms, Equations and Word Problem for π-terms. A variety (of finite
monoids) – sometimes also referred to as a pseudo-variety – is a class of monoids which
is closed under submonoids, homomorphic images and – possibly empty – finite direct
products. For example, the class R of R-trivial monoids and the class L of L-trivial
monoids both form a variety, see e.g. [20]. Clearly, if V and W are varieties, then so is
V ∩ W. For example, the class J = R ∩ L is a variety; in fact, it is the variety of all
J -trivial monoids. For two varieties V and W, the smallest variety containing V ∪ W,
the so called join, is denoted by V ∨ W.
Many varieties can be defined in terms of equations (or identities). Because it will
be useful later, we take a more formal approach towards equations by using π-terms 2 .
1
2

Note that all statements remain valid if one assumes that M ! is used to denote |M |!.
As mentioned in the introduction, π-terms are usually referred to as ω-terms. In this paper, however,

5

A π-term is a finite word, built using letters, concatenation and an additional formal
π-power (and appropriate parentheses), whose π-exponents act as a placeholder for a
substitution value. Formally, every letter a ∈ Σ is a π-term (over Σ). As a special case,
also ε is a π-term. For two π-terms α and β, their concatenation αβ is a π-term as well
and, if γ is a π-term, then so is (γ)π , where π is a formal exponent.
To state equations using π-terms, one needs to substitute the formal π-exponents by
actual values resulting in a word. We define JγKµ as the result of substituting the πexponents in γ by an order type µ, i. e. we have JεKµ = ε, JaKµ = a for all a ∈ Σ,
JαβKµ = JαKµ JβKµ and J(γ)π Kµ = (JγKµ )µ . For example3 , we have
Ja ((b)π c)π K3 = a ((bbb)c) ((bbb)c) ((bbb)c) .
An equation α = β consists of two π-terms α and β over the same alphabet Σ, which,
here, can be seen as a set of variables. A homomorphism σ : Σ∗ → M is called an
assignment of variables in this context. An equation α = β holds in a monoid M if for
every assignment of variables σ (JαKM ! ) = σ (JβKM ! ) is satisfied. It holds in a variety V
if it holds in all monoids in V. The word problem for π-terms over a variety V is the
problem to decide whether α = β holds in V for the input π-terms α and β.
Mal’cev Products. Besides intersection and join, we need one more constructions for
varieties: the Mal’cev product, which is often defined using relational morphisms. In this
paper, we use a different, yet equivalent, approach based on the congruences ∼K and ∼D ,
see [11] or [8, Corollary 4.3]. For their definition, let x and y be elements of a monoid M
and define
x ∼K y ⇔ ∀e ∈ E(S) : ex R e or ey R e ⇒ ex = ey
and x ∼D y ⇔ ∀e ∈ E(S) : xe L e or ye L e ⇒ xe = ye,
where E(S) denotes the set of idempotents in S.
Obviously, ∼K and ∼D are of finite index in any (finite) monoid M . Thus, we have
that M/∼K and M/∼D are (finite) monoids and can define Mal’cev products of varieties.
Let V be a variety. The varieties K m V and D m V are defined by
M ∈ K m V ⇔ M/∼K ∈ V and
M ∈ D m V ⇔ M/∼D ∈ V,
where M is a monoid. Note that, indeed, K m V and D m V are varieties for any variety
V and that, furthermore, we have V ⊆ K m V and V ⊆ D m V.

3 The Trotter-Weil Hierarchy
The main object of study in this paper, is the so-called Trotter-Weil Hierarchy. We will
approach it primarily using certain combinatorial congruence. We will show that this
we use ω to denote the order type of the natural numbers. Therefore, we follow the approach of
Perrin and Pin [19] and use π instead of ω.
3
For a more elaborate example (involving ω + ω ∗ ) see Example 1 on page 35.

6

R3

L3
R3 ∩ L3
R2 ∨ L2

R = R2

L2 = L

m∈N

R1 = L1 = J,

..
.

[

The Trotter-Weil Hierarchy. As the name implies, this hierarchy was first studied by Trotter and
Weil [28]. We will define it using Mal’cev products.
Though this approach is different to the original
one used by Trotter and Weil, both are equivalent
[15]. We define:

Rm ∨ Lm = DA

approach is equivalent to the more common algebraic approach, which we will use as the
definition of the hierarchy.

R2 ∩ L2 = J = R1 = L1

Rm+1 = K m Lm and

Figure 1: Trotter-Weil Hierarchy

Lm+1 = D m Rm .

These varieties form the so-called corners of the hierarchy. Additionally, it contains the
join levels Rm ∨ Lm and the intersection levels Rm ∩ Lm . The term “hierarchy” is
justified by the following inclusions: we have Rm ∩ Lm ⊆ Rm , Lm ⊆ Rm ∨ Lm and
Rm ∨ Lm ⊆ Rm+1 ∩ Lm+1 ; the latter can be seen by induction.
Among the corners of the Trotter-Weil Hierarchy are some well known varieties: we
have R1 = L1 = J, R2 = R and L2 = L (for the last two, see [20]; the others are
straightforward).
By taking the union of all varieties in the hierarchy, one gets the variety DA [13],
which is usually defined as the class of monoids whose regular D-classes form aperiodic
semigroups4 :
[
[
[
Fact 1.
DA =
Rm ∨ Lm =
Rm =
Lm
m∈N

m∈N

m∈N

These considerations yield the graphic representation given in Figure 1.
Connections to Two-Variable Logic. The variety DA is closely connected to twovariable first-order logic. By FO2 [<], denote the set of all first-order sentences over finite
words which may only use the < predicate (and equality) and no more than two variables.
A language L ⊆ Σ∗ of finite words is definable by a sentence ϕ ∈ FO2 [<] if and only if its
syntactic monoid is in DA [27], which it is if and only if it is in one of the Trotter-Weil
Hierarchy’s varieties.
The intersection levels corresponds to the quantifier alternation hierarchy within FO2 [<
] [14]: a first-order sentence using at most two variables belongs to FO2m [<] if, on any
path in its syntax tree, there is no quantifier after the first negation and there are at
most m blocks of quantifiers. A language is definable by a sentence in FO2m [<] if and
only if its syntactic monoid is in Rm+1 ∩ Lm+1 .
4

In finite monoids, D-classes coincide with J -classes; a D-class is called regular if it contains an idempotent. A semigroup is called aperiodic (or group-free) if it has no divisor which is a nontrivial
group.

7

Equational Characterization. Besides its definition using Mal’cev products and its connections to logic, the Trotter-Weil Hierarchy can also be characterized in terms of equations. For our proofs, we only need the direction of this characterization stated in the
lemma below. The other direction does hold as well; we will see later on in Lemma 5
that it is an easy consequence of the hierarchy’s combinatorial characterization which we
state below.
Lemma 1. Define the π-terms
U1 = (sx1 )π s(y1 t)π

and

V1 = (sx1 )π t(y1 t)π

over the alphabet Σ1 = {s, t, x1 }. For m ∈ N, let xm+1 and ym+1 be new characters not
in the alphabet Σm and define the π-terms
Um+1 = (Um xm+1 )π Um (ym+1 Um )π

and

Vm+1 = (Um xm+1 )π Vm (ym+1 Um )π

over the alphabet Σm+1 = Σm ⊎ {xm+1 , ym+1 }.
Then we have
M ∈ R1 = L1 = J ⇐ U1 = V1 holds in M ,
M ∈ Rm+1 ⇐ (Um xm+1 )π Um = (Um xm+1 )π Vm holds in M ,
M ∈ Lm+1 ⇐ Um (ym+1 Um )π = Vm (ym+1 Um )π holds in M and
M ∈ Rm+1 ∩ Lm+1 ⇐ Um = Vm holds in M
for all m ∈ N.
Proof. The first implication is a well-known characterization of J [20]. We show the next
two implications by induction over m (see also [12]).
First, assume m = 1 and consider a monoid M in which (U1 x2 )π U1 = (U1 x2 )π V1 holds.
We need to show M ∈ R2 , which is equivalent to showing M/∼K ∈ L1 = J. For this,
we show u1 = σ (JU1 KM ! ) ∼K σ (JV1 KM ! ) = v1 for an arbitrary assignment of variables
σ : Σ∗1 → M . Afterwards, we are done by the first implication since the exponent of
M/∼K is a divisor of M !. Let e be an arbitrary idempotent of M and assume eu1 R e
(the other case from the definition of ∼K is symmetrical). Thus, there is an element
x2 ∈ M such that eu1 x2 = e holds. We can extend σ by mapping the letter x2 ∈ Σ2 to
the just defined monoid element x2 . We then have
eu1 = e(u1 x2 )u1 = . . . = e(u1 x2 )M ! u1
= e(u1 x2 )M ! v1 = · · · = e(u1 x2 )v1 = ev1 .
The equality in the middle holds because (U1 x2 )π U1 = (U1 x2 )π V1 holds in M by assumption. This concludes the m = 1 case because the third implication is symmetrical.
Now, assume m > 1 and consider a monoid M in which (Um xm+1 )π Um = (Um xm+1 )π Vm
holds. We need to show M ∈ Rm+1 and we do this by showing M/∼K ∈ Lm . By induction, we only have to show that Um−1 (ym Um−1 )π = Vm−1 (ym Um−1 )π holds in M/∼K . As

8

before, let σ : (Σm−1 ⊎ {ym })∗ → M be an arbitrary assignment of variables. For convenience, let um−1 = σ (JUm−1 KM ! ) and vm−1 = σ (JVm−1 KM ! ) and identify ym with σ(ym ).
Let e be an arbitrary idempotent in M such that eum−1 (ym um−1 )M ! R e holds. Clearly,
this implies eum−1 R e and there are elements xm , xm+1 ∈ M such that e = eum−1 xm
and e = eum−1 (ym um−1 )M ! xm+1 holds. Extend σ to map the letters xm and xm+1 to
the respective monoid elements. Then, we have
eum−1 (ym um−1 )M ! = e(um−1 xm )um−1 (ym um−1 )M !
= · · · = e(um−1 xm )M ! um−1 (ym um−1 )M ! = eum
with um = σ (JUm KM ! ). This yields
e = eum−1 (ym um−1 )M ! xm+1 = e (um xm+1 ) = · · · = e (um xm+1 )M ! .
{z
}
|
eum

Using the fact that (Um xm+1 )π Um = (Um xm+1 )π Vm holds in M (by assumption), we get
eum = e (um xm+1 )M ! um = e (um xm+1 )M ! vm = evm
where vm = σ (JVm KM ! ). In combination, we have
eum−1 (ym um−1 )M ! = eum = evm = e(um−1 xm )M ! vm−1 (ym um−1 )M !
where the last equality holds due to the definition of Vm . Finally, we get
eum−1 (ym um−1 )M ! = e(um−1 xm )M ! vm−1 (ym um−1 )M !
= · · · = e(um−1 xm )vm−1 (ym um−1 )M !
= evm−1 (ym um−1 )M !
Thus, we have shown um−1 (ym um−1 )M ! ∼K vm−1 (ym um−1 )M ! (the other case from the
definition of ∼K is symmetrical) and are done. The implication for Lm+1 in the case
m > 1 follows by symmetry again.
Finally, for the intersection levels, suppose that Um = Vm holds in a monoid M . By
the identities for the corners, we directly have M ∈ Rm+1 ∩ Lm+1 .
Besides the equational characterization of the individual varieties in the hierarchy, one
can also characterize their union DA in terms of an equation:
Fact 2. Let M be a monoid. Then, we have
M ∈ DA ⇔ (xyz)π y(xyz)π = (xyz)π holds in M .
A proof of this fact can be found in [26].

9

4 Relations for the Trotter-Weil Hierarchy
Although we define the Trotter-Weil Hierarchy algebraically using Mal’cev products, we
will primarily use a different characterization which is based on certain combinatorial
congruences. Before we can finally introduce these congruences, however, we need to
give some definitions for factorizations of words at the first or last a-position (i. e. an
a-labeled position).
Factorizations and accessible words. For a word w, a position p ∈ dom(w) ⊎ {−∞}
and a letter a ∈ alph(w), let Xa (w; p) denote the first a-position (strictly) larger than
p (or the first a-position in w if p = −∞). It is undefined if there is no such position
(i. e. there is no a to the right of p in w) or if the position is not well-defined. Define
Ya (w; p) symmetrically as the first a-position from the right which is (strictly) smaller
than p. Notice that, with generalized words, the first a-position to the right of a position
p is not necessarily well-defined even if there is an a-position larger than p. For example,
∗
aω = . . . aa does not have a first a-position. We call words for which this situation does
not occur accessible; i. e. a word w is accessible if, for every position p in w (including
the special cases p ∈ {±∞}), Xa (w; p) is defined if and only if there is an a-position in
w(p,+∞) and Ya (w; p) is defined if and only if there is an a-position in w(−∞,p). Note that
all finite words are accessible and that so are all words of the form JγKω+ω∗ for a π-term
γ.
Let w be an accessible word, define
w · XaL = w(−∞,Xa (w;−∞)) ,

w · XaR = w(Xa (w;−∞),+∞),

w · YaL = w(−∞,Ya (w;+∞)) and

w · YaR = w(Ya (w;+∞),+∞)

for all a ∈ alph(w). Additionally, define Ca,b as a special form of applying XaL first
and then YbR which is only defined if Xa (w; −∞) is strictly larger than Yb (w; +∞).
For an example of XaL and XaR acting on a word see Figure 2. Note that we have
w = (w · XaL )a(w · XaR ) = (w · YaL )a(w · YaR ) = (w · YbL )b(w · Ca,b )a(w · XaR ) (whenever
these factors are defined). For example, we have cbbcdcaca · Ca,b = cdc; see the upper
part of Figure 4 for a graphical representation of this example. If we apply a sequence of
factorizations, we omit the · between them, e. g. we write w·XaL YbR = w·XaL ·YbR = w·Ca,b .
l
w=

Xa (w; l)

r

abbabbbbbabbbababbab
w(l,r) · XaL

w(l,r) · XaR

Figure 2: Application of XaL and XaR to an example word.
Relations for the Trotter-Weil Hierarchy. With these definitions in place, we define
Y
WI
5
for m, n ∈ N the relations ≡X
m,n , ≡m,n and ≡m,n of accessible words. The idea is that
5

The presented relations could also be defined by (condensed) rankers (as it is done in [14] and [15]).
Rankers were introduced by Weis and Immerman [30] (thus, the WI exponent in ≡WI
m,n ) who reused

10

these relations hold on two words u and v if both words allow for the same sequence of
factorizations at the first or last occurrence of a letter. For this, we use the following
recursive definition.
Definition 1. Let m, n ∈ N and let u and v be accessible words. Define recursively:
Z
Z
1. u ≡Z
0,0 v, u ≡m,0 v and u ≡0,n v for Z ∈ {X, Y, WI} always hold.
Y
2. u ≡X
m,n v ⇔ alph(u) = alph(v), u ≡m−1,n−1 v and

∀a ∈ alph (u) : u · XaL ≡Ym−1,n−1 v · XaL and
R
u · XaR ≡X
m,n−1 v · Xa

u ≡Ym,n v ⇔ alph(u) = alph(v), u ≡X
m−1,n−1 v and
∀a ∈ alph (u) : u · YaL ≡Ym,n−1 v · YaL and
R
u · YaR ≡X
m−1,n−1 v · Ya

u ≡WI
m,n v ⇔ alph(u) = alph(v),
L
∀a ∈ alph (u) : u · XaL ≡WI
m−1,n−1 v · Xa and
R
u · XaR ≡WI
m,n−1 v · Xa ,
L
∀a ∈ alph (u) : u · YaL ≡WI
m,n−1 v · Ya and
R
u · YaR ≡WI
m−1,n−1 v · Ya and

∀a, b ∈ alph (u) : u·Ca,b and v·Ca,b are either both undefined
or both defined and u · Ca,b ≡WI
m−1,n−1 v ·
Ca,b holds.
X
Y
Additionally, define u ≡XY
m,n v ⇔ u ≡m,n v and u ≡m,n v for all m, n ∈ N0 .

X
≡m,n−1

Y
≡m−1,n−1

As this definition is vital for the understanding of the rest
X
of this paper, we try to give an intuitive understanding of
Y
X
how the relations work. In the parameter m, we rememu= b b ca a b c a
ber the remaining number of direction changes (which are
R
L
caused by an Xa or Ya factorizations) in a factorization
sequence and the parameter n is the number of remaining
factorization moves (independent of their direction). Thus,
if m or n is zero, then the relations shall be satisfied on all
accessible word pairs. For m and n larger than zero, our first
v= bcbabcaa
assertion is that both words have the same alphabet; othY
X
erwise, one of them would admit a factorization at a letter
X
while the other would not, as the letter is not in its alphaX
bet. For the letters of the common alphabet, we want to be Figure 3: ≡m,n illustrated.
able to perform further factorization (until we reach n = 0). The X or Y exponent of
the turtle programs by Schwentick, Thérien and Vollmer [23]. Another concept related to condensed
rankers is the unambiguous interval temporal logic by Lodaya, Pandya and Shah [16].

11

WI
≡m−1,n−1

the relation indicates whether we start at the beginnings or at the ends of the two words;
the WI exponent is a special case, which we will discuss below. So, if we want u ≡X
m,n v
to hold and the alphabets of u and v coincide, then we can continue factorizing at the
first a in u and in v. In the next step, we continue either in the two left parts or in
the two right parts. If we continue in the right parts (i. e. we do an XaR factorization),
R
then we require u · XaR ≡X
m,n−1 v · Xa . The X in the exponent indicates that the last
factorization position (the first a in u and v, respectively) was at the beginning of the
words. We have made one additional factorization – thus, we only have n − 1 remaining
factorizations in this part – but we did not change the direction because we were at the
beginnings of the words before and still are for the new word pair – thus, we still have
m such changes of direction. If, instead of taking the right parts after the first a, we had
taken the left parts, then we would still have made a single factorization; thus we have
n − 1 remaining factorizations. However, we would also have a direction change: the
factorization position (i. e. the first a) is to the right of the new words u · XaL and v · XaL .
Therefore, we have m − 1 remaining direction changes and we change the X exponent
into a Y exponent. This is summed up by requiring u · XaL ≡Ym−1,n−1 v · XaL . Both
situations are illustrated in Figure 3. Additionally, we also have the choice to switch
from the beginning to the end at the cost of one direction change and one factorization.
This is reflected in the fact that we require u ≡Ym−1,n−1 v for u ≡X
m,n v.
Y
The relation ≡m,n works symmetrically to ≡X
m,n . HowY
X
WI
ever, ≡m,n is a bit different. Here, we still lose one diu= c b b c d ca c a
rection change after an XaL or YaR factorization while the
number keeps the same for XaR and YaL factorizations but
we also have the special Ca,b factorizations, which start simultaneously at the beginning and the end. Consider the
situation given in Figure 4. We go to the first a and the
last b; the former is to the right of the latter in both words
v= bcbdccaac
(or the ≡WI
m,n relation does not hold). For the pair of parts
X
Y
in the middle, we require u · Ca,b ≡WI
m−1,n−1 v · Ca,b , i. e.
we count this as a single factorization move which loses a
Figure 4: ≡WI
single direction change. Finally, there is ≡XY
m,n illustrated.
m,n where we
can start factorizing at the beginning or at the end.
By simple inductions, one can see that the relations are congruences of finite index
Z
Z
over Σ∗ . Also note that u ≡Z
m,n v implies u ≡m,k v and, if m > 0, also u ≡m−1,k v for all
k ≤ n and Z ∈ {X, Y, XY, WI}.
The importance of the just defined relations for this paper yields from their connection
to the Trotter-Weil Hierarchy (and, thus, to DA), which we state in the next theorem.
Theorem 1. Let M be a monoid and m ∈ N. Then
• M ≺ Σ∗ /≡X
m,n for some n ∈ N0 ⇔ M ∈ Rm ,
• M ≺ Σ∗ /≡Ym,n for some n ∈ N0 ⇔ M ∈ Lm ,
• M ≺ Σ∗ /≡XY
m,n for some n ∈ N0 ⇔ M ∈ Rm ∨ Lm and
• M ≺ Σ∗ /≡WI
m,n for some n ∈ N0 ⇔ M ∈ Rm ∩ Lm hold.

12

The combinatorial nature of the relations will turn out to be useful in the remainder of
this paper since it allow us, for example, to obtain efficient algorithms for the problems we
consider. Unfortunately, on the other hand, it makes proving Theorem 1 quite technical.
In fact, we will dedicate the next section to this proof.

5 A Proof for Theorem 1
We will prove both directions of Theorem 1 individually. Before we can do this, however,
we need to introduce some more concepts.
R- and L-factorizations. Let ϕ : Σ∗ → M be a (monoid) homomorphism into a monoid
M . The R-factorization of a finite word w is the (unique) factorization w = w0 a1 w1 a2 w2
. . . ak wk with w0 , w1 . . . , wk ∈ Σ∗ and a1 , a2 , . . . , ak ∈ Σ such that, on the one hand,
ϕ(ε) R ϕ(w0 ) and
ϕ(w0 a1 w1 a2 w2 . . . ai ) R ϕ(w0 a1 w1 a2 w2 . . . ai wi )
hold for i = 1, 2, . . . , k and, on the other hand,
ϕ(w0 a1 w1 a2 w2 . . . ai wi ) 6R ϕ(w0 a1 w1 a2 w2 . . . ai wi ai+1 )
holds for i = 0, 1, . . . , k − 1. Symmetrically, the L-factorization of w is the factorization
w = w0 a1 w1 a2 w2 . . . ak wk with w0 , w1 . . . , wk ∈ Σ∗ and a1 , a2 , . . . , ak ∈ Σ such that, on
the one hand,
ϕ(wk ) L ϕ(ε) and
ϕ(wi−1 ai wi ai+1 wi+1 . . . ak wk ) L ϕ(ai wi ai+1 wi+1 . . . ak wk )
hold for i = 1, 2, . . . , k and, on the other hand,
ϕ(ai wi ai+1 wi+1 ai+2 wi+2 . . . ak wk ) 6L ϕ(wi ai+1 wi+1 ai+2 wi+2 . . . ak wk )
holds for i = 1, 2, . . . , k.
DA and R-classes. In DA, getting into a new R-class is strictly coupled to an element’s
alphabet, as the following lemma shows6 , where a can be seen as one of the monoids
generators (i. e. a letter in its alphabet).
Lemma 2. Let M ∈ DA be a monoid and let s, t ∈ M such that s R t. Then
s R sa ⇒ t R ta
holds for all a ∈ M .
6

The curious reader might be interested in the fact that the lemma’s assertion also holds for monoids
in DS, the variety of monoids whose regular D-classes form (arbitrary, but finite) semigroups. More
on DS can, for example, be found in [2].

13

Proof. Since we have t R s R sa, there are x, y ∈ M with s = tx and t = say. We then
have
t = txay = t(xay)2 = · · · = t(xay)M ! ,
which yields
ta(xay)M ! = t(xay)M ! a(xay)M ! = t(xay)M ! = t.
using the equation from Fact 2. Thus, we have ta R t.
One of the main applications of the previous lemma is the following. If we have
a monoid M ∈ DA, a homomorphism ϕ : Σ∗ → M and the R-factorization w =
w0 a1 w1 a2 w2 . . . ak wk of a finite word w ∈ Σ∗ , then we know that ai 6∈ alph(wi−1 ) for
i = 1, 2, . . . , k. If we had ai ∈ alph(wi−1 ), we could factorize wi−1 = uai v and would
have
ϕ(w0 a1 w1 a2 w2 . . . ai−1 u) R ϕ(w0 a1 w1 a2 w2 . . . ai−1 uai )
and, by the previous lemma, also
ϕ(w0 a1 w1 a2 w2 . . . ai−1 uai v) R ϕ(w0 a1 w1 a2 w2 . . . ai−1 uai vai ),
which results in a contradiction to the definition of R-factorizations. Of course, we can
apply a left-right dual of the lemma to get an analogue statement for L-factorizations.
Another application of Lemma 2 is stated in the following lemma.
Lemma 3. Let M ∈ DA be a monoid, s ∈ M and let ϕ : Σ∗ → M be a homomorphism.
Then, for all finite words u, v ∈ Σ∗ with alph(u) = alph(v), we have
s R sϕ(u) ⇒ s R sϕ(v).
Proof. The case u = v = ε is trivial. Therefore, assume s R sϕ(u) but s 6R sϕ(v ′ a)
for some prefix v ′ a of v with a ∈ Σ. Without loss of generality, let v ′ a be the shortest
such prefix; thus, we have s R sϕ(v ′ ). Since we have alph(u) = alph(v), the is a
prefix u′ a of u. Because of s R sϕ(u), we have s R sϕ(u′ ) R sϕ(u′ a). Thus, we have
sϕ(v ′ ) R s R sϕ(u′ ) R sϕ(u′ )ϕ(a). Now, Lemma 2 yields sϕ(v ′ ) R sϕ(v ′ )ϕ(a), which is
a contradiction to our assumption.
Now, we are prepared to prove the characterization of the Trotter-Weil Hierarchy stated
in Theorem 1. This is done in the following two theorems (see also [15] for the corners
and [14] for the intersection levels). We use the notations XΣD = {XaL , XaR | a ∈ Σ},
YΣD = {YaL , YaR | a ∈ Σ} and some natural variations of it.
Theorem 2. Let M be a finite monoid, ϕ : Σ∗ → M a homomorphism and m ∈ N.
Then:

• M ∈ Rm ⇒ ∃n ∈ N ∀u, v ∈ Σ∗ : u ≡X
m,n v ⇒ ϕ(u) = ϕ(v)

• M ∈ Lm ⇒ ∃n ∈ N ∀u, v ∈ Σ∗ : u ≡Ym,n v ⇒ ϕ(u) = ϕ(v)

• M ∈ Rm ∨ Lm ⇒ ∃n ∈ N ∀u, v ∈ Σ∗ : u ≡XY
m,n v ⇒ ϕ(u) = ϕ(v)

• M ∈ Rm+1 ∩ Lm+1 ⇒ ∃n ∈ N ∀u, v ∈ Σ∗ : u ≡WI
m,n v ⇒ ϕ(u) = ϕ(v)
14

Proof. We fix a homomorphism ϕ : Σ∗ → M and proceed by induction over m. For
m = 1, we have R1 = L1 = R1 ∨ L1 = R2 ∩ L2 = J. Thus, the assertion follows
from a result of Simon [24]. However, we also include a full proof for completeness. Let
M ∈ J and n = |M |, which is the number of J -classes in M (and equal to the number
of R-classes and the number of L-classes). Assume that u ≡X
1,n v for two finite words
u, v ∈ Σ∗ and let u = u0 a1 u1 a2 u2 . . . ak uk be the R-factorization of u. We have k + 1 ≤ n
and, because M is R-trivial, ϕ(u0 ) = ϕ(u1 ) = · · · = ϕ(uk ) = 1 or, more precisely, that
no letter in u0 u1 . . . uk can be mapped by ϕ to a value different from 1. Notice that this
implies ϕ(u) = ϕ(a1 a2 . . . ak ). Furthermore, we have ϕ(a1 ), ϕ(a2 ), . . . , ϕ(ak ) 6= 1 due to
the definition of an R-factorization.
R
X
By definition of ≡X
m,n , we have a1 ∈ alph(v) and u · Xa1 = a2 u2 a3 u3 . . . ak uk ≡1,n−1 v ·
XaR1 . Therefore, we can find a2 in v·XaR1 and have u·XaR1 ·XaR2 = a3 u3 a4 u4 . . . ak uk ≡X
m,n−2
v·XaR1 ·XaR2 . Iterating this approach yields that a1 a2 . . . ak is a subword7 of v. Now, let v =
v0 b1 v1 b2 v2 . . . bl vl be the R-factorization of v. By symmetry, we get ϕ(b1 ), ϕ(b2 ), . . . , ϕ(bl ) 6=
1 and that b1 b2 . . . bl is a subword of u. However, for no j ∈ {1, 2, . . . , l}, the letter bj
can occur in u0 u1 . . . uk since all letters in that word must be mapped to 1. Thus,
b1 b2 . . . bl must in fact be a subword of a1 a2 . . . ak . Again by symmetry, a1 a2 . . . ak
must be a subword of b1 b2 . . . bl and, thus, the two words must be equal. This implies ϕ(u) = ϕ(a1 a2 . . . ak ) = ϕ(b1 b2 . . . bl ) = ϕ(v) where the last equality follows from
ϕ(v0 ) = ϕ(v1 ) = · · · = ϕ(vl ) = 1, which holds due to the R-triviality of M .
The argumentation for u ≡Y1,n v is symmetric using the L-factorization, the case for
WI
u ≡XY
1,n v follows trivially and the case for u ≡1,n v uses the same argumentation.
Now, let M ∈ Rm for an m > 1. This implies M/∼K ∈ Lm−1 and there is an
n′ ∈ N such that u′ ≡Ym−1,n′ v ′ ⇒ ϕ(u′ ) ∼K ϕ(v ′ ) holds for all u′ , v ′ ∈ Σ∗ . Let
r be the number of R-classes in M and let n = n′ + r. Consider the R-factorization
u = u0 a1 u1 a2 u2 . . . ak uk of a finite word u ∈ Σ∗ ; note that k + 1 ≤ r must hold. We have
ui = u · XaR1 XaR2 . . . XaRi−1 XaLi for i = 0, 1, . . . , k − 1 and
uk = u · XaR1 XaR2 . . . XaRk .
For a second finite word v ∈ Σ∗ with u ≡X
m,n v, we know that alph(u) = alph(v). Thus,
L
R
we can apply Xa1 and Xa1 to v and obtain
v0 = v · XaL1

and

v ′ = v · XaR1 .

Y
′
X
By definition of ≡X
m,n , we have v0 ≡m−1,n−1 u0 and v ≡m,n−1 u1 a2 u2 a3 u3 . . . ak uk .
′
Because of k ≤ r < n, we can apply the same argument on v and, by iteration, get

vi = v · XaR1 XaR2 . . . XaRi−1 XaLi for i = 0, 1, . . . , k − 1 and
vk = v · XaR1 XaR2 . . . XaRk
with ui ≡Ym−1,n−i−1 vi for i = 0, 1, . . . , k − 1 and uk ≡X
m,n−k vk . Because of i ≤ k ≤ r − 1,
′
′
we have n − i − 1 = n + r − i − 1 ≥ n + r − (r − 1) − 1 = n′ and ui ≡Ym−1,n′ vi for
7

A finite word c1 c2 . . . cs with ci ∈ Σ is a subword of a (not necessarily finite) word w if we can write
w = w0 c1 w1 c2 w2 . . . cs ws for some words w0 , w1 , . . . , ws .

15

i = 0, 1, . . . , k − 1. For uk and vk , we have uk ≡Ym−1,n−k−1 vk by the definition of the
congruences and, therefore, uk ≡Ym−1,n′ vk because of n−k −1 ≥ n−i−1 ≥ n′ . Summing
this up, we have ui ≡Ym−1,n′ vi and, thus, ϕ(ui ) ∼K ϕ(vi ) for all i = 0, 1, . . . , k.
Since we have defined ui by the R-factorization of u, there is an si ∈ M for any
i ∈ {0, 1, . . . , k} such that ϕ(u0 a1 u1 a2 u2 . . . ai ui )si = ϕ(u0 a1 u1 a2 u2 . . . ai ) holds. For
these, we have
(ϕ(ui )si )M ! ϕ(ui ) R (ϕ(ui )si )M !
because of (ϕ(ui )si )M ! ϕ(ui )si (ϕ(ui )si )M !−1 = (ϕ(ui )si )M ! , which yields
(ϕ(ui )si )M ! ϕ(ui ) = (ϕ(ui )si )M ! ϕ(vi )
by ϕ(ui ) ∼K ϕ(vi ). Thus, we have
ϕ(u0 a1 u1 a2 u2 . . . ak uk ) = ϕ(u0 a1 u1 a2 u2 . . . ak uk ) (sk ϕ(uk ))M !
= ϕ(u0 a1 u1 a2 u2 . . . ak ) (ϕ(uk )sk )M ! ϕ(uk )
= ϕ(u0 a1 u1 a2 u2 . . . ak ) (ϕ(uk )sk )M ! ϕ(vk )
= ϕ(u0 a1 u1 a2 u2 . . . ak )ϕ(vk )
= ϕ(u0 a1 u1 a2 u2 . . . ak−1 uk−1 )ϕ(ak vk )
= ϕ(u0 a1 u1 a2 u2 . . . ak−1 ) (ϕ(uk−1 )sk−1 )M ! ϕ(uk−1 )ϕ(ak vk )
= ϕ(u0 a1 u1 a2 u2 . . . ak−1 ) (ϕ(uk−1 )sk−1 )M ! ϕ(vk−1 )ϕ(ak vk )
= ϕ(u0 a1 u1 a2 u2 . . . ak−2 uk−2 )ϕ(ak−1 vk−1 ak vk )
= ...
= ϕ(v0 a1 v1 a2 v2 . . . ak vk ),
which concludes the proof for Rm .
The proof for Lm is symmetrical. For Rm ∨ Lm , we observe that a monoid is in the
join V ∨ W of two varieties V and W if and only if it is a divisor (i. e. the homomorphic
image of a submonoid) of a direct product M1 × M2 such that M1 ∈ V and M2 ∈ W
[6, Exercise 1.1]. Therefore, if we have a monoid M ∈ Rm ∨ Lm , there are monoids
M1 ∈ Rm and M2 ∈ Lm such that M is a divisor of M1 × M2 ; i. e. there is a submonoid
N of M1 × M2 and a surjective monoid homomorphism ψ : N ։ M . For every a ∈ Σ,
we can find elements ma,1 ∈ M1 and ma,2 ∈ M2 with (ma,1 , ma,2 ) ∈ N such that
ϕ(a) = ψ(ma,1 , ma,2 ). Indeed, we can define the maps ϕ1 : Σ → M1 and ϕ2 : Σ → M2 by
setting ϕ1 (a) := ma,1 and ϕ2 (a) := ma,2 . These maps can be lifted into homomorphisms
ϕ1 : Σ∗ → M1 and ϕ2 : Σ∗ → M2 . By induction, there are n1 and n2 such that u ≡X
m,n1 v
Y
implies ϕ1 (u) = ϕ2 (v) and u ≡m,n2 v implies ϕ2 (u) = ϕ2 (v) for any two finite words
u, v ∈ Σ∗ . By setting n = max{n1 , n2 }, we have
u ≡XY
m,n v ⇒ ϕ1 (u) = ϕ1 (v) and ϕ2 (u) = ϕ2 (v)

16

for all u, v ∈ Σ∗ . For all u, v ∈ Σ∗ with u ≡XY
m,n v, this yields
ϕ(a1 a2 . . . ak ) = ϕ(a1 )ϕ(a2 ) . . . ϕ(ak )
= ψ(ma1 ,1 , ma1 ,2 )ψ(ma2 ,1 , ma2 ,2 ) . . . ψ(mak ,1 , mak ,2 )
= ψ((ma1 ,1 , ma1 ,2 )(ma2 ,1 , ma2 ,2 ) . . . (mak ,1 , mak ,2 ))
= ψ(ma1 ,1 ma2 ,1 . . . mak ,1 , ma1 ,2 ma2 ,2 . . . mak ,2 )
= ψ (ϕ1 (u), ϕ2 (u))
= ψ (ϕ1 (v), ϕ2 (v))
= ϕ(b1 b2 . . . bl )
where u = a1 a2 . . . ak , v = b1 b2 . . . bl and a1 , a2 , . . . , ak , b1 , b2 , . . . , bl ∈ Σ.
Finally, let M ∈ Rm+1 ∩ Lm+1 with m > 1. Denote by 2Σ the monoid of subsets
of Σ whose binary operation is the union of sets. It is easy to see that 2Σ is J -trivial.
Therefore, we have M × 2Σ ∈ Rm+1 ∩ Lm+1 . Next, we lift ϕ : Σ∗ → M into a
homomorphism ϕ̂ : Σ∗ → M × 2Σ by taking the word’s alphabet as the entry in the
second component. If we show u ≡WI
m,n v ⇒ ϕ̂(u) = ϕ̂(v) for a suitable n ∈ N, we have,
v
⇒
ϕ(u)
=
ϕ(v).
The advantage of this approach is that we have
in particular, u ≡WI
m,n
ϕ̂(u) = ϕ̂(v) ⇒ alph(u) = alph(v) for all u, v ∈ Σ∗ by the construction of ϕ̂. Instead of
continuing to write ϕ̂, we simply substitute M by M × 2Σ and ϕ by ϕ̂.
We have M/∼K ∈ Lm and M/∼D ∈ Rm . By ≈, denote the join of ∼K and ∼D .
Since it is a homomorphic image of both, M/∼K and M/∼D , the monoid M/≈ is in
Rm ∩ Lm and we can apply induction, which yields an n′ ∈ N such that u ≡WI
m−1,n′ v
∗
implies ϕ(u) ≈ ϕ(v) for all finite words u, v ∈ Σ . Let c be the sum of the number of Rclasses and the number of L-classes in M and set n = n′ + c. Suppose we have u ≡WI
m,n v
for two finite words u, v ∈ Σ∗ . Consider the R-factorization u = u′0 a1 u′1 a2 u′2 . . . ar u′r of
u and the L-factorization v = v0′ b1 v1′ b2 v2′ . . . bl vl′ of v. Clearly, we have r + 1 + l + 1 ≤ c.
w
w
w
Define the positions pw
0 = −∞, pr+1 = +∞ and pi = Xai (w; pi−1 ) for i = 1, 2, . . . , r
and w = u, v. By Lemma 2, we know that pui denotes the position of ai in the Rw = +∞, q w = −∞ and
factorization for i = 1, 2, . . . , r. Symmetrically, we can define ql+1
0
w
w
qj = Yaj (w; qj+1 ) for j = l, l − 1, . . . , 1 and w = u, v. Again, we know that qjv is the
position of bj in the L-factorization of v for j = 1, 2, . . . , l. Additionally, we have
w
w
w
pw
0 < p1 < · · · < pr < pr+1 and
w
q0w < q1w < · · · < qlw < ql+1

for w = u and w = v by their definition. We are going to show that we have pui ▽ qju ⇔
pvi ▽ qjv for ▽ ∈ {<, =, >} and all i = 1, 2, . . . , r and j = 1, 2, . . . , l. Together, these
results yield that the sequence which is obtained by ordering the pi and qj positions in u
is equal to the corresponding sequence in v. To prove this assertion, assume that we have
qju ≤ pui but qjv > pvi for an i ∈ {1, 2, . . . , r} and a j ∈ {1, 2, . . . , l} (all other cases are
symmetric or analogous). Without loss of generality, we may assume that pui−1 < qju ≤ pui
holds since, otherwise, we can substitute i by a smaller i for which the former holds. Note
that this substitution does not violate the condition qjv > pvi as pvi gets strictly smaller if

17

pui−1

qju

pui

u
qj+1

u=

ai−1

bj

ai

bj+1

v=

ai−1

ai

bj

bj+1

pvi−1

pvi

qjv

v
qj+1

Figure 5: Contradiction: pi is to the right of qj in u but to its left in v.
u
i decreases. Equally without loss of generality, we may assume qju ≤ pui < qj+1
by a dual
argumentation. The situation is presented in Figure 5. We have
R R
R
L L
L
u ) = u ·X
u(pui−1 ,qj+1
a1 Xa2 . . . Xai−1 Ybl Ybl−1 . . . Ybj+1 and
L
R R
R
L L
v
v(pvi−1 ,qj+1
) = v · Xa1 Xa2 . . . Xai−1 Ybl Ybl−1 . . . Ybj+1
WI
WI
v
v
u ) ≡
v
v
u
u
and u(pui−1 ,qj+1
m,n−(i−1)−(l−(j+1)+1) v(pi−1 ,qj+1 ) , which yields u(pi−1 ,qj+1 ) ≡m,2 v(pi−1 ,qj+1 )
because of

n − (i − 1) − (l − (j + 1) + 1) = n′ + c − i + 1 − l + j + 1 − 1
= n′ + c − i − l + j + 1
≥ n′ + c − (r + l) + 1
≥ n′ + c − (c − 2) + 1 = n′ + 3
> 2.
L
v
u )·Y
If qju = pui , we have a contradiction since u(pui−1 ,qj+1
)·
bj contains no ai while v(pvi−1 ,qj+1
u ) while we cannot apply it to
YbLj does. For qju < pui , we can apply Cai ,bj to u(pui−1 ,qj+1
v
v(pvi−1 ,qj+1
) by its definition. Both situations constitute a contradiction.
We have proved that if we order the set {pui , qju | i = 1, 2, . . . , r, j = 1, 2, . . . , l} =
{P1u , P2u , . . . , Ptu } (with t ∈ N0 ) such that

P1u < P2u < · · · < Ptu
holds, then we can set
Psv

=

(

pvi
qjv

Psu = pui for some i ∈ {1, 2, . . . , r}
Psu = qju for some j ∈ {1, 2, . . . , l}

for s = 1, 2, . . . , t and get
P1v < P2v < · · · < Ptv .

18

These positions yield factorizations u = u0 c1 u1 c2 u2 . . . ct ut and v = v0 c1 v1 c2 v2 . . . ct vt
such that cs ∈ {ai , bj | i = 1, 2, . . . , r, j = 1, 2, . . . , l} and Psw denotes the position of cs
in w ∈ {u, v} for s = 1, 2, . . . , t. To apply induction, we are going to show us ≡WI
m−1,n′ vs
for all s = 1, 2, . . . , t next.
To simplify notation, we say “Ps is an R-position” for any s ∈ {1, 2, . . . , t} if Psu = pui
for some i ∈ {1, 2, . . . , r} (or, equivalently, if Psv = pvi for some i) and we say “Ps is an
L-position” if Psu = qju for some j ∈ {1, 2, . . . , l} (or, equivalently again, if Psv = qjv for
some j). Note that this definition is not exclusive, i. e. there can be a position which is
both, an R-position and an L-position.
Next, we consider the corner cases of u0 /v0 and ut /vt . If P1 is an R-position, we have
c1 = a1 and
u0 = u · XaL1

as well as

v0 = v · XaL1 ,

WI
which yields u0 ≡WI
m−1,n′ v0 by definition of ≡m,n and because of c > 0. If P1 is an
L-position, we have c1 = b1 and

u0 = u · YbLl YbLl−1 . . . YbL1 as well as
v0 = v · YbLl YbLl−1 . . . YbL1 .
Because l < c, u0 ≡WI
m−1,n′ v0 holds also in this case. For ut and vt , we can apply a
symmetric argumentation.
Finally, we distinguish four cases for a fixed s ∈ {1, 2, . . . , t − 1}. If Ps and Ps+1 are
both R-positions, then we have cs = ai and cs+1 = ai+1 for some i ∈ {1, 2, . . . , r} and
also
us = u · XaR1 XaR2 . . . XaRi XaLi+1 as well as
vs = v · XaR1 XaR2 . . . XaRi XaLi+1 .
WI
By definition of ≡WI
m,n , because of i + 1 ≤ c, we thus have us ≡m−1,n′ vs . A symmetric
argument applies if both, Ps and Ps+1 , are L-positions. If Ps is an R-position but
Ps+1 is an L-position, then cs = ai for some i ∈ {1, 2, . . . , r} and cs+1 = bj for some
j ∈ {1, 2, . . . , l}, which yields

us = u · XaR1 XaR2 . . . XaRi YbLl YbLl−1 . . . YbLj as well as
vs = v · XaR1 XaR2 . . . XaRi YbLl YbLl−1 . . . YbLj .
WI
Therefore, we have us ≡WI
m−1,n′ vs because of the definition of ≡m,n and n−i−(l−j +1) =
n′ + c − (i + 1 + l) + j ≥ n′ + c − c + 0 = n′ . The fourth case is the most interesting: if
Ps is an L but not an R-position while Ps+1 is an R but not an L-position, then cs = bj
for some j ∈ {1, 2, . . . , l} and cs+1 = ai for some i ∈ {1, 2, . . . , r}. Additionally, we have
w
w
w
w
pw
i−1 < Ps = qj < Ps+1 = pi < qj+1 for w = u and for w = v. We define

ũ = u · XaR1 XaR2 . . . XaRi−1 YbLl YbLl−1 . . . YbLj+1 as well as
ṽ = v · XaR1 XaR2 . . . XaRi−1 YbLl YbLl−1 . . . YbLj+1

19

(we consider the X-blocks as empty – meaning that we do not factorize – if i = 1 and the
Y -blocks as empty if j = l). We have ũ ≡WI
m,n−(i−1)−(l−j) ṽ. Because of n−(i−1)−(l−j) =
n′ + c − (i + l) + j + 1 ≥ n′ + c − (r + l) + 1 ≥ n′ + 1, us = ũ · Cai ,bj , vs = ṽ · Cai ,bj and
WI
the definition of ≡WI
m,n , we have us ≡m−1,n′ vs .
We have shown us ≡WI
m−1,n′ vs for all s = 1, 2, . . . , t and, by induction, therefore, know
that ϕ(us ) ≈ ϕ(vs ), i. e. for a fixed s ∈ {1, 2, . . . , t}, there are w1 , w2 , . . . , wk ∈ Σ∗ such
that
ϕ(us ) = ϕ(w1 ) ∼K ϕ(w2 ) ∼D · · · ∼K ϕ(wk−1 ) ∼D ϕ(wk ) = ϕ(vs )
holds.
Remember that we substituted M by M × 2Σ so that we can assume ϕ(u) = ϕ(v) ⇒
alph(u) = alph(v) for all u, v ∈ Σ∗ . We can extend this implication: if we have ϕ(u) ∼K
ϕ(v) for two u, v ∈ Σ∗ , then, by definition of ∼K , we also have ϕ(u)M ! ϕ(u) = ϕ(u)M ! ϕ(v)
because of ϕ(u)M ! ϕ(u) R ϕ(u)M ! . Therefore, we have alph(u) = alph(u) ∪ alph(v) by
the implication stated above. By symmetry, we, thus, have alph(u) = alph(v). Since we
can apply a similar argumentation for ∼D , we have ϕ(u) ∼K ϕ(v) or ϕ(u) ∼D ϕ(v) ⇒
alph(u) = alph(v) for all u, v ∈ Σ∗ . This yields alph(us ) = alph(w1 ) = alph(w2 ) = · · · =
alph(wk ) = alph(vs ).
Since the factorizations u = u0 c1 u1 c2 u2 . . . ct ut and v = v0 c1 v1 c2 v2 . . . ct vt are subfactorizations from the R-factorization of u and the L-factorization of v, there are xs , ys ∈ M
with
ϕ(u0 c1 u1 c2 u2 . . . cs ) = ϕ(u0 c1 u1 c2 u2 . . . cs us )xs and
ϕ(cs+1 vs+1 cs+2 vs+2 . . . ct vt ) = ys ϕ(vs cs+1 vs+1 cs+2 vs+2 . . . ct vt ).
Because of alph(us ) = alph(wi ) for all i ∈ {1, 2, . . . , k} and by Lemma 3,
(ϕ(us )xs )M ! R (ϕ(us )xs )M ! ϕ(us ) implies (ϕ(us )xs )M ! R (ϕ(us )xs )M ! ϕ(wi ).
Similarly, we have

(ys ϕ(vs ))M ! L ϕ(wi ) (ys ϕ(vs ))M !

for all i ∈ {1, 2, . . . , k}. For ϕ(wi ) ∼K ϕ(wi+1 ), this implies
(ϕ(us )xs )M ! ϕ(wi ) = (ϕ(us )xs )M ! ϕ(wi+1 )
and

ϕ(wi ) (ys ϕ(vs ))M ! = ϕ(wi+1 ) (ys ϕ(vs ))M !

for ϕ(wi ) ∼D ϕ(wi+1 ). In either case, we have
(ϕ(us )xs )M ! ϕ(wi ) (ys ϕ(vs ))M ! = (ϕ(us )xs )M ! ϕ(wi+1 ) (ys ϕ(vs ))M ! ,
which yields for any i ∈ {1, 2, . . . , k − 1}:
ϕ(u0 c1 u1 c2 u2 . . . cs wi cs+1 vs+1 cs+2 vs+2 . . . ct vt )
= ϕ(u0 c1 u1 c2 u2 . . . cs ) (ϕ(us )xs )M ! ϕ(wi ) (ys ϕ(vs ))M ! ϕ(cs+1 vs+1 cs+2 vs+2 . . . ct vt )
= ϕ(u0 c1 u1 c2 u2 . . . cs ) (ϕ(us )xs )M ! ϕ(wi+1 ) (ys ϕ(vs ))M ! ϕ(cs+1 vs+1 cs+2 vs+2 . . . ct vt )
= ϕ(u0 c1 u1 c2 u2 . . . cs wi+1 cs+1 vs+1 cs+2 vs+2 . . . ct vt )

20

So, we can substitute wi by wi+1 and, therefore, also us by vs , i. e. we have
ϕ(u0 c1 u1 c2 u2 . . . cs us cs+1 vs+1 cs+2 vs+2 . . . ct ut )
= ϕ(u0 c1 u1 c2 u2 . . . cs vs cs+1 vs+1 cs+2 vs+2 . . . ct vt ).
Consecutively applying the former equation for s = t, then for s = t − 1 and so on yields
ϕ(u) = ϕ(u0 c1 u1 c2 u2 . . . ct−1 ut−1 ct ut )
= ϕ(u0 c1 u1 c2 u2 . . . ct−1 ut−1 ct vt )
= ϕ(u0 c1 u1 c2 u2 . . . ct−1 vt−1 ct vt )
..
.
= ϕ(v0 c1 v1 c2 v2 . . . ct−1 vt−1 ct vt )
= ϕ(v),
which concludes the proof.
It remains to show the other direction of Theorem 1 (i. e. the converse of Theorem 2).
We will do this by using the equations from Lemma 1. Therefore, we begin with the
following lemma.
Lemma 4. Let Σm , Um and Vm be as in Lemma 1 and let k ∈ N and n ∈ N0 . Then,
for every assignment of variables σ : Σ∗m → Σ∗ and all Z ∈ {X, Y, XY, WI}, we have
σ (JUm Knk ) ≡Z
m,n σ (JV1 Knk )
π
σ (J(Um xm+1 )π Um Knk ) ≡X
m+1,n σ (J(Um xm+1 ) Vm Knk )

σ (JUm (Um xm+1 )π Knk ) ≡Ym+1,n σ (JVm (Um xm+1 )π Knk )
for all m ∈ N.
Proof. We only show the first assertion by induction over m. The other assertions follow
by similar arguments. For m = 1, we may assume n > 0 since, otherwise, there is nothing
to show. We have
U1 = (sx1 )π s(y1 t)π

and

V1 = (sx1 )π t(y1 t)π .

Let u1 = σ (JU1 Knk ) and v1 = σ (JV1 Knk ). First, assume Z = X. We are only interested
in at most n consecutive simultaneous XΣR factorizations of u1 and v1 because, as soon
as we apply at least one XΣL factorization, we know that ≡X
0,n holds. As long as we
R
apply only factorizations Xa with a ∈ alph(σ(sx1 )), the factorization position stays in
the (sx1 )π part of u1 and v1 . Since the number of remaining factorizations decreases,
R
the right parts will eventually be in relation under ≡X
m,0 . If there is at least one Xa
factorization in the sequence where a is in alph(σ(y1 t)) \ alph(σ(sx1 )), the right-hand
side of u1 belongs to the (y1 t)π part and the right-hand side of v1 belongs to the t(y1 t)π
part; but in both words, there are still at least n − 1 instances of σ(y1 t), which implies

21

part containing the difference
um+1 =

(um xm+1 ) (um xm+1 ) . . . (um xm+1 ) um (ym+1 um ) (ym+1 um ) . . . (ym+1 um )

vm+1 =

(um xm+1 ) (um xm+1 ) . . . (um xm+1 ) vm (ym+1 um ) (ym+1 um ) . . . (ym+1 um )
Repetition of the same word
for nk ≥ n times.

Repetition of the same word
for nk ≥ n times.

Figure 6: Schematic representation of um+1 and vm+1 . Note that xm+1 and ym+1 are
identified with σ(xm+1 ) and σ(ym+1 ), respectively.
that the right-hand sides are equal under ≡X
m,n−1 . For Z = Y , the argumentation is
symmetric, which also handles the Z = XY case. The additional Ca,b of Z = WI needs
no special handling since it decreases the first index of ≡WI
m,n to m − 1 = 0 anyway.
To conclude the induction, we show
um+1 = σ (JUm+1 Knk ) ≡Z
m+1,n σ (JVm+1 Knk ) = vm+1
next. For a schematic representation of um+1 and vm+1 , the reader is advised to refer
to Figure 6. For convenience, we identify xm+1 with σ(xm+1 ) and ym+1 with σ(ym+1 ).
We will only show the case Z = WI since this is the most difficult one and the other
ones are similar. In fact, we will proof the following claim by an inner induction on l for
0 ≤ l ≤ n:
l
l
(um xm+1 )l um (ym+1 um )l ≡WI
m+1,l (um xm+1 ) vm (ym+1 um )
The actual assertion then follows for the case l = n. For l = 0, there is nothing to
show. So, let l > 0. First, consider an XaL or XaR factorizations. Only two cases can
emerge: the factorization happens in the (um xm+1 )l part or the factorization happens in
the (ym+1 um )l part (in both words simultaneously). The factorization cannot happen in
the central um or vm part because we have alph(vm ) = alph(um ) ⊆ alph(um xm+1 ).
First, consider the case in which the factorization happens at the beginning. Clearly,
if this is the case, then the factorization must occur in the first (um xm+1 ) factor of both
words at the same position:
Xa
(um xm+1 ) (um xm+1 )l−1 um (ym+1 um )l−1 (ym+1 um )
=

WI
≡m+1,l−1

=

=

(um xm+1 ) (um xm+1 )l−1 vm (ym+1 um )l−1 (ym+1 um )
Xa

22

l
l
L
So, we have (um xm+1 )l um (ym+1 um )l ·XaL ≡WI
m,l−1 (um xm+1 ) vm (ym+1 um ) ·Xa because
the two words are equal. For an XaR factorization, we have to apply induction on l and
get
l−1
vm (ym+1 um )l−1
(um xm+1 )l−1 um (ym+1 um )l−1 ≡WI
m+1,l−1 (um xm+1 )
l
l
in the middle. Thus, we also get (um xm+1 )l um (ym+1 um )l ·XaR ≡WI
m+1,l−1 (um xm+1 ) vm (ym+1 um ) ·
XaR (because the other word parts are equal and because ≡WI
m+1,l−1 is a congruence).
If the factorization happens at the end, the situation is similar. Clearly, the factorization can only happen at the same position in the first (ym+1 um ) factor of each word,
respectively (in fact, it can only happen within the first ym+1 ):

Xa
(um xm+1 ) (um xm+1 )l−1 um (ym+1 um ) (ym+1 um )l−1
=

=

WI
≡m,l−1

=

(um xm+1 ) (um xm+1 )l−1 vm (ym+1 um ) (ym+1 um )l−1
Xa
WI
We have um ≡WI
m,n vm by induction on m and (because l ≤ n) also um ≡m,l−1 vm .
Because the other parts of the words are equal, respectively, and because ≡WI
m,l−1 is a
l v (y
l
L
(u
x
)
u
congruence, we get (um xm+1 )l um (ym+1 um )l · XaL ≡WI
m m+1
m m+1 m ) · Xa .
m,l−1
l
l
R
We have (um xm+1 )l um (ym+1 um )l · XaR ≡WI
m+1,l−1 (um xm+1 ) vm (ym+1 um ) · Xa directly
because the word parts on the right coincide.
Because YaL and YaR factorizations are symmetrical, the only remaining case is a Ca,b
factorization. It is not possible that Ca,b is defined on one of the words but not on
the other because in each respective part the same letters appear. If Ca,b is defined on
(um xm+1 )l um (ym+1 um )l and on (um xm+1 )l vm (ym+1 um )l , then the only possible situation
is that the XaL factorization happens at the same position of the first (ym+1 um ) part in
each word and the YbR factorization happens at the same position of the last (um xm+1 )
factor in each word:

23

Xa

Yb

(um xm+1 )l−1 (um xm+1 ) um (ym+1 um ) (ym+1 um )l−1
=

=

WI
≡m,l−1

(um xm+1 )l−1 (um xm+1 ) vm (ym+1 um ) (ym+1 um )l−1
Yb

Xa

As in the previous case, we have um ≡WI
m,l−1 vm and, because the other parts of the words
l
l
l
coincide respectively, also (um xm+1 ) um (ym+1 um )l ·Ca,b ≡WI
m,l−1 (um xm+1 ) vm (ym+1 um ) ·
Ca,b .
Theorem 3. Let m, n ∈ N. Then:
• Σ∗ /≡X
m,n ∈ Rm

• Σ∗ /≡XY
m,n ∈ Rm ∨ Lm

• Σ∗ /≡Ym,n ∈ Lm

• Σ∗ /≡WI
m,n ∈ Rm+1 ∩ Lm+1

Proof. To prove the theorem, one needs to show that the equations from Lemma 1 hold
in the respective monoid. To do this, it is worthwhile to make an observation: choose
m, n ∈ N and Z ∈ {X, Y, XY, WI} arbitrarily and let M = Σ∗ /≡Z
m,n . The observation is
Z
that an equation α = β holds in M if and only if σ (JαKn·M ! ) ≡m,n σ (JβKn·M ! ) holds for
all assignments σ : Γ → Σ∗ where Γ is the alphabet of α and β (i. e. the set of variables
appearing in α and β).
WI
So, to show Σ∗ /≡WI
m,n ∈ Rm+1 ∩ Lm+1 , it suffices to show that σ (JUm Kn·M ! ) ≡m,n
σ (JVm Kn·M ! ) holds for all assignments of variables σ : Σ∗m → Σ∗ . However, this follows from the first assertion of Lemma 4. The same is true for R1 and L1 . To show
Σ∗ /≡X
m+1,n ∈ Rm+1 for m ∈ N0 , we use the second assertion of Lemma 4 and, for
∗
Y
Σ /≡m+1,n ∈ Lm+1 , we use the third one.
To prove that M/≡XY
m,n is in Rm ∨Lm , one can recycle an observation from the proof of
Theorem 2: a monoid is in the join V ∨ W of two varieties V and W if and only if it is a
divisor of a direct product M1 × M2 such that M1 ∈ V and M2 ∈ W. Indeed, for any two
congruences C1 and C2 over a monoid N , N/ (C1 ∩ C2 ) is a divisor of N/C1 × N/C2 (as can
X
be shown easily). Therefore, M/≡XY
m,n is a divisor of the direct product of M/≡m,n ∈ Rm
and M/≡Ym,n ∈ Lm .
To conclude this section, we finally state and prove the converse of Lemma 1. This
gives us a full characterization of the Trotter-Weil Hierarchy in terms of equations (see

24

also [12]). Note that we include this proof only for the sake of completeness. Strictly
speaking, it is not necessary for the remainder of this paper.
Lemma 5. Define the π-terms
U1 = (sx1 )π s(y1 t)π

and

V1 = (sx1 )π t(y1 t)π

over the alphabet Σ1 = {s, t, x1 }. For m ∈ N, let xm+1 and ym+1 be new characters not
in the alphabet Σm and define the π-terms
Um+1 = (Um xm+1 )π Um (ym+1 Um )π

and

Vm+1 = (Um xm+1 )π Vm (ym+1 Um )π

over the alphabet Σm+1 = Σm ⊎ {xm+1 , ym+1 }.
Then we have
M ∈ R1 = L1 = J ⇒ U1 = V1 holds in M ,
M ∈ Rm+1 ⇒ (Um xm+1 )π Um = (Um xm+1 )π Vm holds in M ,
M ∈ Lm+1 ⇒ Um (ym+1 Um )π = Vm (ym+1 Um )π holds in M and
M ∈ Rm+1 ∩ Lm+1 ⇒ Um = Vm holds in M
for all m ∈ N.
Proof. As stated in the proof of Lemma 1, the first implication is due to a well-known
characterization in terms of equations of J [20]. The other implications can be proved
by combining Lemma 4 and Theorem 2. For example, suppose M ∈ Rm+1 and let
σ : (Σm ⊎ {xm+1 })∗ → M be an arbitrary assignment of variables. We need to show
σ (J(Um xm+1 )π Um KM ! ) = σ (J(Um xm+1 )π Vm KM ! ). By Theorem 2, there is an n ∈ N such
∗
that u ≡X
m+1,n v implies σ(u) = σ(v) for all u, v ∈ (Σm ⊎ {xm+1 }) . Thus, for this n, we
have
σ (J(Um xm+1 )π Um KM ! ) = σ (J(Um xm+1 )π Um Kn·M ! )
= σ (J(Um xm+1 )π Vm Kn·M ! ) = σ (J(Um xm+1 )π Vm KM ! )
π
since we have J(Um xm+1 )π Um Kn·M ! ≡X
m+1,n J(Um xm+1 ) Vm Kn·M ! by Lemma 4.

6 Relations and Equations
Infinite Version of the Relations. So far, we have mainly considered finite words. In
this section, which connects the relational approach outlined above with equations, we
finally need to consider generalized words. Thus, we also define an infinite version of the
above relations. Here, we allow an arbitrary number of factorizations: for m ∈ N0 and
Z ∈ {X, Y, XY, WI}, define
Z
u ≡Z
m v ⇔ ∀n ∈ N : u ≡m,n v.

Notice that this definition is not useful for finite words as every one of them is in its own
class.

25

Connecting the Relations and Equations. In order to solve the word problem for
π-terms over the varieties in the Trotter-Weil Hierarchy, one can use the following connection between the relations defined above and equations in these varieties, which is
straightforward if one makes the transition from finite to infinite words. Besides its use
for the word problem for π-terms, this connection is also interesting in its own right as
it can be used to prove or disprove equations in any of the varieties. As the class of
monoids in which an equation α = β holds is a variety, one can see the assertion for the
join levels as an implication of the ones for the corners.
Theorem 4. Let α and β be two π-terms. For every m ∈ N, we have:
JαKω+ω∗ ≡X
m JβKω+ω ∗ ⇔ α = β holds in Rm
JαKω+ω∗ ≡Ym JβKω+ω∗ ⇔ α = β holds in Lm
JαKω+ω∗ ≡XY
m JβKω+ω ∗ ⇔ α = β holds in Rm ∨ Lm
JαKω+ω∗ ≡WI
m JβKω+ω ∗ ⇔ α = β holds in Rm+1 ∩ Lm+1
Using Fact 1, which states that DA is equal to the union of all varieties in the TrotterWeil Hierarchy, we immediately get the following corollary.

⇔ α = β holds in DA
Corollary 1. ∀m ∈ N : JαKω+ω∗ ≡XY
m JβKω+ω ∗

To prove Theorem 4, we need two technical lemmas. The first one basically says that
a sufficiently large finite power is as good as an ω + ω ∗ power.
Lemma 6. Let m ∈ N0 , Z ∈ {X, Y, XY, WI} and let u and v be accessible words. Then:
ω+ω
k+1
u ≡Z
≡Z
m,n v ⇒ ∀ 0 ≤ k ≤ n : u
m,k v

∗

Proof. The case m = 0 is trivial. Therefore, let m > 0 and continue by induction over
k. Again, the case k = 0 is trivial. To complete the induction, it remains to
 show that
ω+ω ∗ holds for k < n. Obviously, alph(uk+2 ) = alph v ω+ω ∗ is satisfied
uuk+1 ≡Z
v
m,k+1
Y
by assumption. Now assume Z = X. The assumption u ≡X
m,n v implies u ≡m−1,n−1 v.
∗
By induction on m, this yields uk+1 ≡Ym−1,k v ω+ω and u ≡Ym−1,k v. Because ≡Ym−1,k is
∗
∗
a congruence, this shows uuk+1 ≡Ym−1,k vv ω+ω = v ω+ω . Let a ∈ alph(u) = alph(v). It
∗
ω+ω ∗ · X R . For
remains to show uuk+1 · XaL ≡Ym−1,k v ω+ω · XaL and uuk+1 · XaR ≡X
a
m,k v
L , which in turn implies
L ≡Y
v
·
X
v
implies
u
·
X
the former, note that u ≡X
a
a
m,n
m−1,n−1
∗
∗
uuk+1 · XaL = u · XaL ≡Ym−1,k v · XaL = vv ω+ω · XaL = v ω+ω · XaL . For the latter, note that
R
R
R
X
R
X
u ≡X
m,n v implies u · Xa ≡m,n−1 v · Xa and, thus, u · Xa ≡m,k v · Xa . By induction on
∗
ω+ω . Together these yield uuk+1 · X R = (u · X R )uk+1 ≡X
k, we also have uk+1 ≡X
a
a
m,k
m,k v
∗
∗
(v · XaR )v ω+ω = v ω+ω · XaR .
The case for Z = Y is symmetric and the case for Z = XY follows directly. Finally,
for Z = WI the argumentation is analogous because, for k > 0, neither uuk+1 · Ca,b nor
∗
v ω+ω · Ca,b is defined for any pair (a, b) of letters.

26

The second technical lemma states that, for finitely many factorization steps, only
finitely many positions of ω + ω ∗ are relevant.
Lemma 7. Let m, n ∈ N0 , Z ∈ {X, Y, XY, WI} and let γ be a π-term. Then
JγKk ≡Z
m,n JγKω+ω ∗
holds for all k ∈ N0 with k > n.
Proof. The cases for m = 0 or n = 0 are trivial. Thus, assume m > 0 and n > 0. If
γ = ε or γ = a for an a ∈ Σ, then JγKk = γ = JγKω+ω∗ . If γ = αβ for two π-terms α
Z
Z
and β, then by induction JαKk ≡Z
m,n JαKω+ω ∗ and JβKk ≡m,n JβKω+ω ∗ hold. As ≡m,n is a
congruence, this implies JγKk ≡Z
m,n JγKω+ω ∗ .
ω+ω ∗
π
Finally, let γ = (α) for a π-term α. It remains to show that JαKkk ≡Z
m,n JαKω+ω ∗ .
Clearly, the alphabetic condition is satisfied and, by induction, JαKk ≡Z
m,n JαKω+ω ∗ holds.
k
For Z = X, let a ∈ alph(α). By induction on m and n, we have JαKk = JγKk ≡Ym−1,n−1
∗
L
k
L
L
Y
JγKω+ω∗ = JαKω+ω
ω+ω ∗ . We also have JαKk · Xa = JαKk · Xa ≡m−1,n−1 JαKω+ω ∗ · Xa =
∗
∗
ω+ω
R
X
R
k
X
L
JαKω+ω
ω+ω ∗ ·Xa by definition of JαKk ≡m,n JαKω+ω ∗ . To show JαKk ·Xa ≡m,n−1 JαKω+ω ∗ ·Xa ,
X
R
we use JαKk · XaR ≡X
m,n−1 JαKω+ω ∗ · Xa , which holds because of JαKk ≡m,n JαKω+ω ∗ , and
ω+ω ∗
k−1
X
X
show JαKk ≡m,n−1 JαKω+ω . This is sufficient because ≡m,n−1 is a congruence and we
∗
∗
ω+ω ∗
have uuω+ω = uω+ω for all words u. For showing JαKkk−1 ≡X
m,n−1 JαKω+ω , we write
k − 1 = k′ + n for a k′ ∈ N0 and
′

JαKkk−1 = JαKkk JαKnk and
∗

′

∗

ω+ω
k
JαKω+ω
ω+ω ∗ = JαKω+ω ∗ JαKω+ω ∗ .
∗

ω+ω
Setting k = n − 1 in Lemma 6 yields JαKnk ≡X
m,n−1 JαKω+ω ∗ , which concludes the proof
for Z = X since ≡X
m,n−1 is a congruence.
The case for Z = Y is symmetric, which also shows the case for Z = XY . For
∗
Z = WI, we note that JαKω+ω
ω+ω ∗ · Ca,b is defined for no pair a, b of letters. On the other
hand, JαKkk · Ca,b can only be defined for k = 1, in which case we are done because we
have n = 0.

Now, we are finally prepared to prove Theorem 4.
Proof for Theorem 4. The proof is structurally identical for all stated varieties. Therefore, we limit our discussion to Rm .
First, let JαKω+ω∗ ≡X
m JβKω+ω ∗ . Choose a monoid M ∈ Rm and an assignment of
∗
variables σ : Σ → M . Because M is in Rm , there is an n ∈ N such that u ≡X
m,n v
implies σ(u) = σ(v) for any two words u, v ∈ Σ∗ (see also Theorem 2). Now, choose
c ∈ N with M ! · c > n. Then by assumption and Lemma 7, we have
X
X
∗
Σ∗ ∋ JαKM !·c ≡X
m,n JαKω+ω ∗ ≡m,n JβKω+ω ∗ ≡m,n JβKM !·c ∈ Σ

and, therefore, σ(JαKM ! ) = σ(JαKM !·c ) = σ(JβKM !·c ) = σ(JβKM ! ), which is equivalent to
α = β holding in M .

27

Now, let JαKω+ω∗ 6≡X
m JβKω+ω ∗ , which implies that there is an n ∈ N such that
X
JαKω+ω∗ 6≡m,n JβKω+ω∗ . Define M := Σ∗ /≡X
m,n , which is in Rm (by Theorem 3), and
choose c ∈ N such that M ! · c > n. Then, by assumption and Lemma 7, we have
X
X
∗
Σ∗ ∋ JαKM !·c ≡X
m,n JαKω+ω ∗ 6≡m,n JβKω+ω ∗ ≡m,n JβKM !·c ∈ Σ .

As assignment of variables σ : Σ∗ → M choose the canonical projection. This yields
σ(JαKM ! ) = σ(JαKM !·c ) 6= σ(JβKM !·c ) = σ(JβKM ! ), which means that α = β does not hold
in M .

7 Decidability
In the previous section, we saw that checking whether α = β holds in a variety of the
Z
Trotter-Weil Hierarchy boils down to checking JαKω+ω∗ ≡Z
m JβKω+ω ∗ (where ≡m depends
on the variety in question). In this section, we give an introduction on how to do this.
The presented approach works uniformly for all varieties in the Trotter-Weil Hierarchy (in
particular, it also works for the intersection levels, which tend to be more complicated)
and is designed to yield efficient algorithms.
The definition of the relations which need to be tested is inherently recursive. One
would factorize JαKω+ω∗ and JβKω+ω∗ on the first a and/or last b (for a, b ∈ Σ) and test
the factors recursively. Therefore, the computation is based on working with factors of
words of the form JγKω+ω∗ where γ is a π-term.
What happens if we consecutively factorize at a
first/last a is best understood if one considers the
∗
ω+ω ∗ = w,
structure of J(α)π Kω+ω∗ = JαKω+ω
ω+ω ∗ = u
... u u u
u u u ...
which is schematically represented in Figure 7.
1 2 3
−3 −2 −1
Suppose u only contains a single a and we start
with the whole word w(−∞,+∞) . If we factorize
ω-part
ω ∗ -part
on the first a taking the part to the right, then
we end up with the factor w(Xa (w;−∞),+∞) with Figure 7: Representation of uω+ω∗
Xa (w; −∞) = (p, 1) where p is the single a-position in u. If we do this again, we obtain
w((p,2),+∞) . If we now factorize on the next a but take the part to the left, then we get
w((p,2),(p,3)) . Notice that the difference between 2 and 3 is 1 and that there is no way of
getting a (finite) difference larger than one by factorizing on the respective first a. On
the other hand, we can reach any number in N as long as the right position is not in the
ω-part.
Notice that there is also no way of reaching (p, −2) as left border without having
(q, −1) or (q, −2) as right border for a position q ∈ dom(u). These observations (and
their symmetrical duals) lead to the notion of normalizable pairs of positions.
Definition 2. Let γ be a π-term and let w = JγKω+ω∗ . A pair (l, r) of positions in w
such that l is strictly smaller than r is called normalizable (with respect to γ) based on
the following rules:
• Any pair is normalizable with respect to γ = ε or γ = a for an a ∈ Σ.

28

• (−∞, +∞) is normalizable with respect to any π-term.
• If γ = αβ for π-terms α and β, l ∈ dom(JαKω+ω∗ ) ⊎ {−∞} and r ∈ dom(JβKω+ω∗ ) ⊎
{+∞}, then (l, r) is normalizable with respect to γ if (l, +∞) is with respect to α
and (−∞, r) is with respect to β.
• If γ = αβ for π-terms α and β and l ∈ dom(JαKω+ω∗ ) ⊎ {−∞} as well as r ∈
dom(JαKω+ω∗ ) (or l ∈ dom(JβKω+ω∗ ) as well as r ∈ dom(JβKω+ω∗ ) ⊎ {+∞}), then
(l, r) is normalizable with respect to γ if it is with respect to α (or β, respectively).
• If γ = (α)π for a π-term α, l = (l′ , n) for l′ ∈ dom(JαKω+ω∗ ) and n ∈ N ⊎ −N and
r = +∞, then (l, r) is normalizable with respect to γ if (l′ , +∞) is with respect to
α and n is in N ⊎ {−1}.
• If γ = (α)π for a π-term α, l = −∞, and r = (r ′ , m) for r ′ ∈ dom(JαKω+ω∗ ) and
m ∈ N ⊎ −N, then (l, r) is normalizable with respect to γ if (−∞, r ′ ) is with respect
to α and m is in {1} ⊎ −N.
• If γ = (α)π for a π-term α, l = (l′ , n) for l′ ∈ dom(JαKω+ω∗ ) and n ∈ N ⊎ −N and
r = (r ′ , m) for r ′ ∈ dom(JαKω+ω∗ ) and m ∈ N ⊎ −N, then (l, r) is normalizable with
respect to γ if
– n ∈ N, m ∈ −N and (l′ , +∞) and (−∞, r ′ ) are normalizable with respect to
α,
– n, m ∈ N or n, m ∈ −N and in both cases m = n and (l′ , r ′ ) is normalizable
with respect to α, or
– n, m ∈ N or n, m ∈ −N and in both cases m = n+1 and (l′ , +∞) and (−∞, r ′ )
are normalizable with respect to α.
This definition looks cumbersome at first. All it does, however, is formalizing our previous observations. This allows us to give a formal inductive proof that these observations
hold for all positions reachable by iterated first/last a factorization. First, we need to extend our notation. For this, we consider (abstract) positions p ∈ {−∞, +∞} ⊎ dom(w) in
a word w to be implicitly linked to w. For a pair of positions (l, r) ∈ ({−∞} ⊎ dom(w))×
(dom(w) ⊎ {+∞}) in an accessible word w, we write
(l, r) · XaL = (l, Xa (w; l)),

(l, r) · XaR = (Xa (w; l), r),

(l, r) · YaL = (l, Ya (w; r)) and

(l, r) · YaR = (Ya (w; r), r)

for all a ∈ alph w(l,r) . Note that we now have w(l,r) · ZaD = w(l,r)·ZaD for all Z ∈ {X, Y }
and all D ∈ {L, R}. In fact, we could have used this as the definition previously. We also
write (l, r) · Ca,b for (l, r) · XaL · YbR if Xa (w; l) is strictly larger than Yb (w; r). Therefore,
we also have w(l,r) · Ca,b = w(l,r)·Ca,b . As with words, we omit the · if we apply a sequence
of steps longer than one, e. g. we simply write (l, r)·XaL YbR = (l, r)·XaL ·YbR = (l, r)·Ca,b .

29

Lemma 8. Let γ be a π-term and let w = JγKω+ω∗ . Additionally, let (l, r) be a normalizable (with respect to γ) pair of positions in w. Then the pairs
(l, r) · XaL , (l, r) · XaR , (l, r) · YaL and (l, r) · YaR
are normalizable with respect to γ for any a ∈ alph(w(l,r) ).
Therefore, (−∞, +∞)·F1 F2 . . . Fn is normalizable with respect to γ for any F1 , F2 , . . . ,
Fn ∈ {XaL , XaR , YaL , YaR , Ca,b | a, b ∈ Σ} (if it is defined).
Proof. As the cases for YaL and YaR are symmetrical, we only show those for XaL and XaR .
Let p = Xa (w; l) for an a ∈ alph(w(l,r) ). Clearly, we have l <µ p <µ r, where µ is the
order type of w, and we need to show that (l, p) and (p, r) are normalizable. For this, we
proceed by induction on the structure of γ. The base case γ = ε or γ ∈ Σ is trivial.
Case γ = αβ. Define u = JαKω+ω∗ and v = JβKω+ω∗ . For l ∈ dom(u) ⊎ {−∞} and
r ∈ dom(u) we have p ∈ dom(u) as well. Additionally, (l, r) needs to be normalizable
with respect to α by the definition of normalizability and we can apply induction. The
same argument, but on β, works for l ∈ dom(v) and r ∈ dom(v) ⊎ {+∞}. For l ∈
dom(u) ⊎ {−∞} and r ∈ dom(v) ⊎ {+∞} we know that (l, +∞) is normalizable with
respect to α and (−∞, r) is with respect to β by the definition of normalizablity. If
p ∈ dom(u), then (p, +∞) = (l, +∞) · XaR and (l, p) = (l, +∞) · XaL . Induction yields
normalizability with respect to α for both and, by the definition of normalizability, we
have that (p, r) and (l, p) are normalizable with respect to γ. For p ∈ dom(v), we can
apply a similar argument, as then (−∞, p) = (−∞, +∞) · XaL and (p, r) = (−∞, r) · XaR
are normalizable with respect to β.
Case γ = (α)π . Define u = JαKω+ω∗ and let p = (p′ , k). If l = (l′ , n) for an n ∈
N ⊎ −N and r = +∞, then, by the definition of normalizability, we have that (l′ , +∞)
is normalizable with respect to α and n ∈ N ⊎ {−1}. There are two cases: for k =
n ∈ N ⊎ {−1} we know that p′ = Xa (u; l′ ) and, by induction, that (l′ , p′ ), (p′ , +∞) are
normalizable with respect to α. This yields the normalizability with respect to γ of (l, p)
and (p, +∞). For k = n + 1 we know that n 6= −1 and, therefore, that n, k ∈ N. We
also have p′ = Xa (u; −∞) and, thus, that (−∞, p′ ) and (p′ , +∞) are normalizable with
respect to α by induction. By definition, (p, +∞) and (l, p) are normalizable with respect
to γ then. Note that k cannot have any other value than n or n + 1 since otherwise it
could not be the smallest a-position to the right of l.
If l = −∞ and r = (r ′ , m), then k = 1, and p′ = Xa (u; −∞), which yields (−∞, p′ ) =
(−∞, +∞) · XaL and (p′ , +∞) = (−∞, +∞) · XaR . By induction, both of these pairs
are normalizable with respect to α and, by definition of the normalizability, (−∞, p)
is normalizable with respect to γ. Furthermore in this case, we know that (−∞, r ′ ) is
normalizable with respect to α and that m is in {1} ⊎ −N. For m ∈ −N, this shows the
normalizability with respect to γ of (p, r). For m = 1, we have (p′ , r ′ ) = (−∞, r ′ )·XaR and,
by induction, its normalizability with respect to α. This yields that (p, r) is normalizable
with respect to γ.
If l = (l′ , n) and r = (r ′ , m) for n ∈ N and m ∈ −N, we know that (l′ , +∞) and
(−∞, r ′ ) are normalizable with respect to α. For k = n ∈ N, we also know that p′ =

30

Xa (u; l′ ) and, therefore, that (l′ , p′ ) = (l′ , +∞) · XaL and (p′ , +∞) = (l′ , +∞) · XaR are
normalizable with respect to α by induction. Then, by definition, (l, p) and (p, r) are
normalizable with respect to γ. For k = n + 1 ∈ N we have that p′ = Xa (u; −∞)
and, therefore, the normalizability with respect to α of (−∞, p′ ) = (−∞, +∞) · XaL and
(p′ , +∞) = (−∞, +∞) · XaR by induction. This yields the normalizability with respect
to γ of (l, p) and (p, r).
Finally, if l = (l′ , n) and r = (r ′ , m) for n, m ∈ N or n, m ∈ −N, we know that
0 ≤ m−n ≤ 1. Because p must be in between l and r, n = m also implies n = m = k and
that p′ is in between l′ and r ′ as well as p′ = Xa (u; l′ ). In that case, we have that (l′ , r ′ )
and, by induction, also (l′ , p′ ) = (l′ , r ′ ) · XaL and (p′ , r ′ ) = (l′ , r ′ ) · XaR are normalizable
with respect to α. This yields the normalizability with respect to γ of (l, p) and (p, r).
For m = n + 1, we know that (l′ , +∞) and (−∞, r ′ ) are normalizable with respect to
α. Moreover, there are only two cases: k = n and k = m. In the former case, we have
p′ = Xa (u; l′ ) and the normalizability with respect to α of (l′ , p′ ) = (l′ , +∞) · XaL and
(p′ , +∞) = (l′ , +∞)·XaR by induction, which yields the normalizability of (l, p) and (p, r)
with respect to γ. In the latter case, we have p′ = Xa (u; −∞) and the normalizability
with respect to α of (−∞, p′ ) = (−∞, +∞) · XaL and (p′ , r ′ ) = (−∞, r ′ ) · XaR , which
yields the normalizability with respect to γ of (l, p) and (p, r).
The choice of words indicates that normalizability of a pair (l, r) can be used to define
a normalization. Before we give a formal – unfortunately, quite technical – definition of
this, we describe its idea informally. Let us refer back to the schematic representation of
J(α)π Kω+ω∗ = w as given in Figure 7. Basically, there are three different cases for relative
positions of the left border l and the right border r which describe the factor w(l,r) :
1. l is in the ω-part and r is in the ω ∗ -part,
2. l and r are either both in the ω-part or both in the ω ∗ -part and have the same
value there, or
3. l and r are either both in the ω-part or both in the ω ∗ -part but r has a value
exactly larger by one than l.
This is ensured by the normalizability of (l, r). Now, in the first case, we can safely move
l to value 1 (the first position) and r to value −1 (the last position) without changing
the described factor. In the second and third case, we can move l and r to any value –
as long as we retain the difference between the values – without changing the described
factor. Here, we move them to the left-most values (which are 1, 1 or 1, 2). Afterwards,
we go on recursively.
Unfortunately, things get a bit more complicated because l might be −∞ and r might
be +∞. In these cases, we normalize to the left-most or right-most value without changing the factor.
For concatenations of π-terms, we have a similar situation: either l and r belong both
to the left or to the right factor, in which case we can continue by normalization with
respect to that, or l belongs to the left factor and r belongs to the right one. In this

31

case, we have to continue the normalization with (l, +∞) and (−∞, r) in the respective
concatenation parts, as this ensures that the described factor remains unchanged.
Formalizing these ideas results in the following inductive definition.
Definition 3. Let γ be a π-term, w = JγKω+ω∗ and (l, r) a normalizable pair of positions
γ
in w. The normalized pair (l, r) = (¯l, r̄) with respect to γ is defined recursively:
• For γ = ε or γ = a ∈ Σ define ¯l = l and r̄ = r.
• If γ = αβ for π-terms α and β, l ∈ dom(JαKω+ω∗ ) ⊎ {−∞} and r ∈ dom(JβKω+ω∗ ) ⊎
α
{+∞}, then define ¯l as the first component of (l, +∞) and r̄ as the second comβ

ponent of (−∞, r) .
• If γ = αβ for π-terms α and β and l ∈ dom(JαKω+ω∗ ) ⊎ {−∞} as well as r ∈
dom(JαKω+ω∗ ) (or l ∈ dom(JβKω+ω∗ ) as well as r ∈ dom(JβKω+ω∗ ) ⊎ {+∞}), then
α
β
define (¯l, r̄) = (l, r) (or (¯l, r̄) = (l, r) , respectively).
• If γ = (α)π for a π-term α, then:
– if l = −∞, define ¯
l = −∞,
– if r = +∞, define r̄ = +∞,
– if l = (l′ , n) and r = +∞, define ¯l = (l¯′ , n̄) with l¯′ given by the first component
α
of (l′ , +∞) and n̄ given by
(
1
if n ∈ N
n̄ =
−1 if n = −1,
– if l = −∞ and r = (r ′ , m), define r̄
α
component of (−∞, r ′ ) and m̄ given
(
1
m̄ =
−1

= (r¯′ , m̄) with r¯′ given by the second
by
if n = 1
if n ∈ −N,

– if l = (l′ , n) and r = (r ′ , m) with n ∈ N and m ∈ −N, define ¯l = (l¯′ , 1) with
α
l¯′ being by the first component of (l′ , +∞) and define r̄ = (r¯′ , −1) with r̄ ′
α
given by the second component of (−∞, r ′ ) ,
– if l = (l′ , n) and r = (r ′ , m) with n = m, define ¯l = (l¯′ , n̄) and r̄ = (r¯′ , m̄)
α
with (l¯′ , r¯′ ) = (l′ , r ′ ) and n̄ = m̄ = 1, and
– if l = (l′ , n) and r = (r ′ , m) with m = n + 1, define ¯l = (l¯′ , n̄) and r̄ = (r¯′ , m̄)
α
with l¯′ given by the first component of (l′ , +∞) , r¯′ given by the second
α
component of (−∞, r ′ ) , n̄ = 1 and m̄ = n̄ + 1 = 2.
One should note that if we normalize a normalizable pair (l, r), then the resulting pair
is normalizable itself. Indeed, if we normalize an already normalized pair again, we do
not change any values. Formally, this can be proved by an induction on the structure of
the π-term. As an example for such an induction, we prove the following lemma which
states that normalizing a pair of positions does not change the described factor.

32

Lemma 9. Let γ be a π-term and let (l, r) be a normalizable pair of positions in w =
JγKω+ω∗ . Then
w(l,r) = w(l,r)γ
holds.
γ
Proof. Define (l, r) = (¯l, r̄) and proceed by induction on the structure of γ. The base
cases for γ = ε and γ ∈ Σ are trivial.
If γ = αβ for π-terms α and β, then define u = JαKω+ω∗ and v = JβKω+ω∗ . If
l ∈ dom(u) ⊎ {−∞} and r ∈ dom(v) ⊎ {+∞}, then

w(l,r) = u(l,+∞) v(−∞,r) = u(l,+∞)α v

β

(−∞,r)

= w(l,r)γ .

If l ∈ dom(u) ⊎ {−∞} and r ∈ dom(u), then
w(l,r) = u(l,r) = u(l,r)α = w(l,r)γ .
The case l ∈ dom(v) and r ∈ dom(v) ⊎ {+∞} is symmetrical.
If γ = (α)π for a π-term α, then define u = JαKω+ω∗ . The case l = −∞ and r = +∞
α
is trivial. If l = (l′ , n) for an n ∈ N ⊎ −N and r = +∞, define l¯′ by (l′ , +∞) = (l¯′ , +∞).
For n ∈ N we then have




∗
ω+ω ∗
w(l,r) = w((l′ ,n),+∞) = uω+ω
=
u
′
′
((l ,n),+∞)

∗

((l ,1),+∞)

∗

because of uω+ω = uuω+ω and further
∗

∗

w(l,r) = u(l′ ,+∞)uω+ω = u(l′ ,+∞)α uω+ω = u(l¯′ ,+∞) uω+ω


∗
= uω+ω
= w((l′ ,n),+∞)γ = w(l,r)γ
¯′

∗

((l ,1),+∞)

and for n = −1 – the only remaining case – we have

w(l,r) = w((l′ ,−1),+∞) = u(l′ ,+∞) = u(l′ ,+∞)α = u(l¯′ ,+∞) = w((l¯′ ,−1),+∞) = w(l,r)γ .
The case for l = −∞ and r = (r ′ , m) is symmetrical.
Therefore, we can assume l = (l′ , n) and r = (r ′ , m). The case n ∈ N and m ∈ −N is
proved by a calculation similar to the one given above. For n = m we have
w(l,r) = w((l′ ,n),(r′ ,n)) = u(l′ ,r′ ) = u(l′ ,r′ )α = w(l,r)γ
and for m = n + 1 we have
w(l,r) = u(l′ ,+∞) u(−∞,r′ ) = u(l′ ,+∞)α u(−∞,r′ )α = w(l,r)γ .

33

Another observation is crucial for the proof of the decidability: after normalizing a pair
(l, r) the values belonging to the ω+ω ∗ parts for the two positions are all in {1, 2, −2, −1}.
But: there are only finitely many such positions in any word w = JγKω+ω∗ for a π-term
γ. Because the normalization preserves the described factor, this means that there are
only finitely many factors which can result from a sequence of first/last a factorizations.
Plugging all these ideas and observations together yields a proof for the next theorem.
Theorem 5. For two π-terms α and β over the same alphabet Σ, it is decidable for all
m ∈ N0 and all Z ∈ {X, Y, XY, WI} whether
JαKω+ω∗ ≡Z
m JβKω+ω ∗
holds. Furthermore, it is decidable whether
∀m ∈ N : JαKω+ω∗ ≡XY
m JβKω+ω ∗
holds.
Proof. We decide whether u = JαKω+ω∗ ≡Z
m JβKω+ω ∗ = v holds by trying to find a
factorization sequence F1 F2 . . . Fn with F1 , F2 , . . . , Fn ∈ {XaL , XaR , YaL , YaR , Ca,b | a, b ∈
Σ} that can be applied to u but not to v (or vice versa), i. e. we rather try to decide
u 6≡Z
m v instead.
Which sequences need to be tested depends on the actual relation. For example, for
R
L
≡X
m , we can start with arbitrary many Xa factorizations but, as soon as we apply an Xa ,
L
R
Ya or Ya factorization, we have changed the direction and we have to decrease m by one.
If we did this because of a YaD factorization (with D ∈ {R, L}), we also need to switch
to a ≡Ym−1 mode, in which case we can continue with arbitrary many YaL factorizations
while any other factorization decreases the remaining number of direction changes and
WI
might also switch back to a ≡X
m−2 mode. If we want to test ≡m , we also need to allow
Ca,b factorizations and we need to count the number of direction changes appropriately.
For testing ≡XY
m for all m ∈ N, the situation is simpler: here, we do not need to keep
track of the remaining direction changes as there always is an arbitrary number of them
left. Clearly, we can construct a deterministic finite automaton for any of the relations
which accepts exactly those sequences F1 F2 . . . Fn which need to be tested.
To test whether a factorization sequence can be applied on u, we construct an additional deterministic finite automaton. The states of this automaton are the normalized
pairs of positions in u (of which there only finitely many, as discussed above). The initial
state is (−∞, +∞) and all states are final. This does not result in a trivial automaton because it will not be complete in general. We have an F -labeled transition with
α
F ∈ {XaD , YaD , Ca,b | a, b ∈ Σ, D ∈ {L, R}} from (l, r) to (l, r) · F if (l, r) · F is defined.
Note that normalization does not change the implicitly stored factor of u by Lemma 9.
This automaton, by construction, accepts exactly those factorization sequences which
can be applied to u.
Using the same construction, we can also get such an automaton for v. We intersect
both automata with the one which accepts the relevant factorization sequences. For the

34

resulting pair of automata, we check the symmetric difference of the accepted languages
for emptiness. It is empty if any only if u and v are in relation.
Together with Theorem 4, this gives the following decidability result. Note that previous partial results exist: Almeida proved decidability for J [1, 3], Almeida and Zeitoun
proved it for R [4] and Moura for DA [18].
Corollary 2. The word problems for π-terms over Rm , Lm , Rm ∨ Lm and Rm ∩ Lm are
decidable for any m ∈ N. Moreover, the word problem for π-terms over DA is decidable.

8 Nondeterministic Logarithmic Space
In the presented algorithm, we construct for a π-term γ over the alphabet Σ a deterministic finite automaton which accepts exactly those factorization sequences which can be
applied to JγKω+ω∗ = w. For this, we had to store normalized pairs (l, r) of positions
γ
in w and we had to compute (l, r) · F for a factorization F ∈ {XaD , YaD , Ca,b | a, b ∈
Σ, D ∈ {L, R}}. In this section, we will show that both can be done by a deterministic
Turing machine in logarithmic space. Afterwards, we will show that this yields membership of the word problems for π-terms to the class of problems which can be solved by
nondeterministic Turing machines within logarithmic space.
Observations and Ideas. We will start by having a close look on how to store a position
p (and, therefore, a pair of positions) in the word w = JγKω+ω∗ on a Turing machine. To
do this, we first store the position in γ which corresponds to p in w; this, basically, is a
simple pointer. Additionally, we need to store to which value in N ⊎ −N the position p
belongs for all relevant π-exponents; this, we can do by storing a pointer to the π-position
in γ together with the corresponding value. If p is part of a normalized pair of positions,
the values can only be in {1, 2, −2, −1}, which is a finite set and, thus, needs only finite
information.
Example 1. Have a look at the π-term γ = a (b(c)π )π a(b)π c. The word JγKω+ω∗ can be
represented by the following tree:

a

a

b

c ...

...

... c

...

c

b ...

b

c c ...

35

... c

... b

The highlighted position can also be represented this way:
a(b(c)

π

)

π

a(b)

π

c

2 −1
Note that the last π-position does not have a value since it is not relevant for the position.
Also note that storing the values on a second tape directly under the π-position would
require linear space (for a position belonging to a normalized pair). We store them in a
position/value list which will turn out to be more efficient after some modifications.
Unfortunately, this approach still requires at least linear space. But for normalized
pairs, we can optimize it further if we look at the definition of the normalization. At
some point the two positions l and r in the normalized pair (l, r) branch since l is a
smaller position than r. This can either happen because l = −∞ or r = +∞, because
there are sub-π-terms α and β and l belongs to JαKω+ω∗ while r belongs to JβKω+ω∗ , or
because of a sub-π-term of the form (α)π where l has a different value compared to r. In
the former two cases, we call the pair c-branching 8 and in the latter case π-branching.
Whichever is the case, we know that the values of l and r belonging to hierarchically
higher π-positions are always equal and, by definition of the normalization, are equal to
1. Thus, we do not need to store these values explicitly; instead, we are going to store
the branching position.
If the branching position is a π-position (i. e. the pair is π-branching), then, for a
normalized pair, the values of l and r at this position can, by definition, only be 1 for
l and 2 for r or 1 for l and −1 for r. This information can be stored alongside the
branching position in constant space.
To store the values hierarchically below the branching position, we need to have an even
closer look at normalized position pairs. Before we do this, however, it is convenient to
define four position forms: a position is in +-form if all its values for relevant π-positions
are from N and it is in −-form if they are from −N. Positions in ∓-form may only have
values from N for π-positions which are hierarchically lower than the first π-position with
a value from N and positions in ±-form are defined symmetrically. More formally, we
define:
Definition 4. A position p ∈ dom(JγKω+ω∗ ) for a π-term γ is in
• +-form (with respect to γ) if
– γ = ε or γ ∈ Σ,
– γ = αβ for π-terms α and β and p is in +-form with respect to its respective
sub-π-term, or
– γ = (α)π for a π-term α, p = (p′ , n) with n ∈ N and p′ is in +-form with
respect to α,
8

The “c” is for concatenation.

36

• −-form (with respect to γ) if
– γ = ε or γ ∈ Σ,
– γ = αβ for π-terms α and β and p is in −-form with respect to its respective
sub-π-term, or
– γ = (α)π for a π-term α, p = (p′ , n) with n ∈ −N and p′ is in −-form with
respect to α,
• ∓-form (with respect to γ) if
– γ = ε or γ ∈ Σ,
– γ = αβ for π-terms α and β and p is in ∓-form with respect to its respective
sub-π-term,
– γ = (α)π for a π-term α, p = (p′ , n) with n ∈ N and p′ has +-form, or
– γ = (α)π for a π-term α, p = (p′ , n) with n ∈ −N and p′ has ∓-form, or
• ±-form (with respect to γ) if
– γ = ε or γ ∈ Σ,
– γ = αβ for π-terms α and β and p is in ±-form with respect to its respective
sub-π-term,
– γ = (α)π for a π-term α, p = (p′ , n) with n ∈ −N and p′ has −-form, or
– γ = (α)π for a π-term α, p = (p′ , n) with n ∈ N and p′ has ±-form.
Example 2. The position
a(b(c)

π

)

π

a(b)

π

c

2 −1
from the previous example is in ∓-form but not in any of the other three forms.
The similar position represented by
a(b(c)

π

)

2

π

a(b)

π

c

3

is in +-form, in ∓-form and in ±-form but it is not in −-form.
What use are these definitions for our goal of storing positions efficiently? If we know
that a position is in +-form or −-form, then we do not need to store whether a value is
from N or from −N. Similarly, if a position is in ∓-form or in ±-form, then we only need
to store one potential π-position at which the values switch form −N to N or vice versa.
While this does not seem to be a huge gain since we still need to store the actual value,
it will turn out to be crucial later on.

37

Next, we need to make some further observations. Consider a π-term γ and define
w = JγKω+ω∗ . If we start with a position p ∈ dom(w) in ∓-form and we go to the next
a on the right (i. e. we compute Xa (w; p)), then the follow-up position p′ is in ∓-form
as well because strictly after the branching of p and p′ all values for relevant π-position
have to be 1 (since otherwise there would already have been an a before). By symmetry,
if we start in ±-form and go to the previous a on the left, the resulting position will also
be in ±-form.
Example 3. Look again at the π-term γ = a (b(c)π )π a(b)π c. Suppose we are in the
position p in w = JγKω+ω∗ and advance to p′ = Xb (w; p):

a

b

a

...

...

c

b ...

b

... b

p′
c ...

... c

c c ...
p

... c

Clearly, p′ is in ∓-form.
If we advanced to p′′ = Xc (w; p) instead, the situation would be as follows:

a

b

c ...

a

...

... c

...

c

b ...

b

c c c ...
p p′′

... b

... c

Again, p′′ clearly has ∓-form.
More formally, we can prove the following lemma:
Lemma 10. Let γ be a π-term and w = JγKω+ω∗ . Then
• Xa (w; −∞) is in +-form for any a ∈ alph(w),
• if l ∈ dom(w) is in +-form, then so is Xa (w; l) for all a ∈ alph(w(l,+∞) ),

38

• if l ∈ dom(w) is in ∓-form, then so is Xa (w; l) for all a ∈ alph(w(l,+∞) ),
• Ya (w; +∞) is in −-form for any a ∈ alph(w),
• if r ∈ dom(w) is in −-form, then so is Ya (w; r) for all a ∈ alph(w(−∞,r) ), and
• if r ∈ dom(w) is in ∓-form, then so is Ya (w; r) for all a ∈ alph(w(−∞,r) ).
Proof. By symmetry, we only have to prove the first three assertions.
We start by proving the first one. The cases γ = ε and γ ∈ Σ are trivial. For the other
cases, let a ∈ alph(w) and define p = Xa (w; −∞). If γ = αβ for two π-terms α and β, we
define u = JαKω+ω∗ and v = JβKω+ω∗ . Now, we have p = Xa (u; −∞) or p = Xa (v; −∞).
In either case, we can apply induction, which yields that p is in +-form with respect
to its sub-π-term, and we are done. If γ = (α)π for a π-term α, define u = JαKω+ω∗ .
Clearly, p has to be equal to (p′ , 1) for p′ = Xa (u; −∞). By induction, we have that p′ is
in +-form and, since 1 ∈ N, we are done.
The second assertion can be proved similarly. Let l ∈ dom(w) be in +-form. If γ = ε
or γ ∈ Σ, we do not have any remaining positions in dom(w) for p = Xa (w; l). In
the other cases, let a ∈ alph(w(l,+∞) ). If γ = αβ for two π-terms α and β, we define
u = JαKω+ω∗ and v = JβKω+ω∗ . We have to distinguish: if l and p both are in dom(u)
(or, symmetrically, in dom(v)), then we have p = Xa (u; l) and we can apply induction.
Therefore, p is in +-form with respect to α, which yields that p is also in +-form with
respect to γ. If l ∈ dom(u) and p ∈ dom(v), then we know that p = Xa (v; −∞), which
is in +-form with respect to β by the first assertion and, therefore, also in +-form with
respect to γ.
If γ = (α)π for a π-term α, define u = JαKω+ω∗ . We can write l = (l′ , m) and p = (p′ , k)
for some m, k ∈ N ⊎ −N and l′ , p′ ∈ dom(u). By definition, l′ is in +-form because l is so.
For k, there are only two possible cases: k = m and k = m + 1. In the former case, we
know that p′ = Xa (u; l′ ) and can apply induction to get that p′ is in +-form with respect
to α. Since l is in +-form, we also know that k = m ∈ N. Together, this yields that p is
in +-form with respect to γ. In the latter case k = m + 1, we know that p′ = Xa (u; −∞)
is in +-form by the first assertion. Since l is in +-form, we have m ∈ N and, therefore,
also k = m + 1 ∈ N. Thus, p is in +-form with respect to γ.
Now, we prove the third assertion. Let l be in ∓-form with respect to γ. Again, for
γ = ε or γ ∈ Σ, there is nothing to show. The case for γ = αβ for two π-terms α
and β can be proved analogously to the corresponding case in the proof for the second
assertion.
If γ = (α)π for a π-term α, define u = JαKω+ω∗ and let p = Xa (w; l) for an a ∈
alph(w(l,+∞) ). We can write l = (l′ , m) and p = (p′ , k) for some m, k ∈ N ⊎ −N and
l′ , p′ ∈ dom(u). Again, there are only two possible cases: k = m and k = m + 1. In the
former case we have p′ = Xa (u; l′ ). If k = m ∈ N, we know that l′ is in +-form since
l has to be in ∓-form. By the second assertion, this yields that p′ is in +-form as well.
Therefore, we have that p is in ∓-form. If k = m ∈ −N, we can simply apply induction
and get that p′ is in ∓-form with respect to α. This yields that p is in ∓-form with
respect to γ. In the latter case k = m + 1, we know that p′ = Xa (u; −∞) is in +-form

39

by the first assertion and that m 6= −1. This yields ∓-form for p if k = m + 1 ∈ N or
k = m + 1 ∈ −N.
This observation is also important for pairs which arise by consecutive factorization
at the 
first/last a. If we start in (−∞, +∞) and apply a sequence X of elements from
XΣR = XaR a ∈ Σ , then l′ in the resulting pair (l′ , +∞) = (−∞, +∞) · X will be in
∓-form. Equally, for a sequence over YΣL = YaL a ∈ Σ , the right position will be in
±-form. Can we assume that the left position is always in ∓-form and the right one is
always in ±-form? Unfortunately, the answer to this question is “no”. Suppose we start
in the pair (l, r) where l is in ∓-form and r is in ±-form. If we apply XaL for some a ∈ Σ,
then, obviously, we end up in a pair (l, r ′ ) whose right position is in ∓-form. But: the
right position r ′ branches form l at some point and strictly below that point values for
relevant π-positions are equal to 1. So, we could say that for this lower part r ′ , indeed, is
in ±-form. In fact, we will prove that, strictly below the branching, l is always in ∓-form
and r is always in ±-form for any pair (l, r) = (−∞, +∞) · F where F is a sequence
of elements from FΣ = {XaD , YaD , Ca,b | a, b ∈ Σ, D ∈ {L, R}}. The situation at the
branching point itself depends on whether we have a c-branching or a π-branching pair.
For a π-branching pair, we cannot make an assumption on the value of l and r at the
actual branching π-position. We accommodate for this by having two definitions.
Definition 5. Let (l, r) be a pair of positions in JγKω+ω∗ for a π-term γ such that l is
strictly smaller than r.
The pair is called well-c-shaped (with respect to γ) if
• γ = ε or γ ∈ Σ,
• γ = αβ for π-terms α and β, l ∈ dom(JαKω+ω∗ ) ⊎ {−∞}, r ∈ dom(JαKω+ω∗ ) and
(l, r) is well-c-shaped with respect to α,
• γ = αβ for π-terms α and β, l ∈ dom(JβKω+ω∗ ), r ∈ dom(JβKω+ω∗ ) ⊎ {+∞} and
(l, r) is well-c-shaped with respect to β,
• γ = αβ for π-terms α and β, l ∈ dom(JαKω+ω∗ )⊎{−∞}, r ∈ dom(JβKω+ω∗ )⊎{+∞},
and
– l = −∞ or l is in ∓-form with respect to α, and
– r = +∞ or r is in ±-form with respect to β,
or
• γ = (α)π for a π-term α and
– l = −∞ and r = +∞,
– l = −∞ and r is in ±-form,
– l is in ∓-form and r = +∞, or
– l = (l′ , n) and r = (r ′ , n) for an n ∈ N ⊎ −N and (l′ , r ′ ) is well-c-shaped with
respect to α,

40

It is called well-π-shaped (with respect to γ) if γ 6= ε and γ 6∈ Σ as well as
• γ = αβ for π-terms α and β, l, r ∈ dom(JαKω+ω∗ ) and (l, r) is well-π-shaped with
respect to α,
• γ = αβ for π-terms α and β, l, r ∈ dom(JβKω+ω∗ ) and (l, r) is well-π-shaped with
respect to β, or
• γ = (α)π for a π-term α, l = (l′ , n), r = (r ′ , m) for n, m ∈ N ⊎ −N and l′ , r ′ ∈
dom(JαKω+ω∗ ) and
– n = m and (l′ , r ′ ) is well-π-shaped with respect to α, or
– n 6= m, l′ is in ∓-form and r ′ is in ±-form.
Finally, it is called well-shaped (with respect to γ) if it is well-c-shaped or well-π-shaped
(with respect to γ).
The definition of well-c-shapedness is related to c-branching pairs and the definition of
well-π-shapedness is related to π-branching pairs. Note that any pair (l, r) of positions
in JγKω+ω∗ for a π-term is well-c-shaped if l = −∞ or r = +∞. This results in some
asymmetry in the definition.
We proceed by showing that any pair (l, r) which arises by consecutive factorization
at the first/last a is well-c-shaped or well-π-shaped.
Lemma 11. Let (l, r) be a pair of positions in JγKω+ω∗ for a π-term γ. If (l, r) is
well-shaped, then so is (l, r) · F for any F ∈ FΣ (if it is defined).
Therefore, (−∞, +∞) · F1 F2 . . . Fn is well-shaped with respect to γ for any F1 , F2 , . . . ,
Fn ∈ FΣ (if it is defined).
Proof. The second part follows from the first since (−∞, +∞) is well-c-shaped by definition.
Let (l, r) be well-shaped and let p = Xa (w; l) be defined for an a ∈ Σ. Due to
symmetry, it remains to show that (l, p) and (p, r) are well-shaped. Note that this also
includes the Ca,b factorization.
First, consider (l, p). If l = −∞, then p is in +-form by Lemma 10 and, therefore,
also in ±-form. This yields that (−∞, p) is well-c-shaped. Thus, we may safely assume
that l 6= −∞ and proceed by induction on the structure of γ. With this assumption, the
cases γ = ε and γ ∈ Σ cannot occur.
If γ = αβ for two π-terms α and β, define u = JαKω+ω∗ and v = JβKω+ω∗ . If l and r are
both in dom(u), then we know, by definition of well-shapedness, that (l, r) is well-shaped
with respect to α. We also know that p = Xa (u; l) since p must be between l and r. By
induction, we have that (l, p) is well-shaped with respect to α, which yields that (l, p)
is also well-shaped with respect to γ. If l ∈ dom(v) and r ∈ dom(v) ⊎ {+∞}, we can
apply a similar argument. For l ∈ dom(u) and r ∈ dom(v) ⊎ {+∞}, we know that (l, r)
is well-c-shaped and that l is in ∓-form with respect to α. This yields that (l, +∞) is
well-c-shaped with respect to α. By induction, we then have that (l, p) = (l, Xa (u; l)) is
well-shaped with respect to α if p ∈ dom(u). Well-shapedness with respect to γ follows

41

in both cases, i. e. (l, p) is well-c-shaped or (l, p) is well-π-shaped, by definition of wellshapedness. If p ∈ dom(v), then we have p = Xa (v; −∞), which is in +-form (and, thus,
in ±-form) by Lemma 10. By definition, we have the well-c-shapedness of (l, p) with
respect to γ.
If γ = (α)π for a π-term α, then define u = JαKω+ω∗ . We can write l = (l′ , m) and
p = (p′ , k) for some m, k ∈ N⊎−N and l′ , p′ ∈ dom(u). For k = m, we have p′ = Xa (u; l′ ).
This yields well-shapedness with respect to α of (l′ , p′ ) by induction. By definition, we
also have well-shapedness with respect to γ. For k = m + 1 (the only other possible
case), we know p′ = Xa (u; −∞) which is in +-form with respect to α by Lemma 10 and,
therefore, also in ±-form. If r = +∞, then (l, r) had to be well-c-shaped and l has to be
in ∓-form. Then, (l, p) is well-π-shaped. If r = (r ′ , n) for a n ∈ N ⊎ −N and r ′ ∈ dom(u),
then n must be greater than m (with respect to ω + ω ∗ ), because it must be greater than
or equal to k. Therefore, (l, r) has to be well-π-shaped and l has to be in ∓-form. Again,
(l, p) is well-π-shaped then, which concludes the proof that (l, p) is always well-shaped.
Next, consider (p, r). If r = +∞, then (l, r) has to be well-c-shaped. This implies that
l = −∞ or l is in ∓-form. In either case, we have that p = Xa (w; l) is in ∓-form by
Lemma 10. Thus, (p, +∞) is well-c-shaped. Again, we can safely assume that r 6= +∞
and proceed by induction on the structure of γ where the cases γ = ε and γ ∈ Σ do not
occur.
If γ = αβ for two π-terms α and β, then define u = JαKω+ω∗ and v = JβKω+ω∗ . The
case l ∈ dom(u) ⊎ {−∞} and r ∈ dom(u) and the case l, r ∈ dom(v) are similar to
the argumentation for (l, p). For l ∈ dom(u) ⊎ {−∞} and r ∈ dom(v), (l, r) has to
be well-c-shaped. Therefore, r has to be in ±-form with respect to β and (−∞, r) is
well-c-shaped with respect to β. Induction yields the well-shapedness with respect to β,
and, thus, also with respect to γ, of (p, r) if p ∈ dom(v). If p ∈ dom(u), we observe that
well-c-shapedness of (l, r) yields l = −∞ or l in ∓-form. In either case, p is in ∓-form
by Lemma 10. Thus, (p, r) is well-c-shaped with respect to γ.
If γ = (α)π for a π-term α, define u = JαKω+ω∗ . We can write p = (p′ , k) and r = (r ′ , n)
for k, n ∈ N ⊎ −N. For k = n, distinguish: if l = −∞, then (l, r) is well-c-shaped and r
has to be in ±-form with respect to γ. Therefore, r ′ has to be in ±-form with respect
to α. If l = (l′ , m) for l′ ∈ dom(u) and m ∈ N ⊎ −N with m <ω+ω∗ k = n, then (l, r)
is well-π-shaped and r ′ , again, is in ±-form. In both cases, this yields that (−∞, r ′ )
is well-c-shaped with respect to α. Induction yields that (p′ , r ′ ) = (Xa (u; −∞), r ′ ) is
well-shaped with respect to α. Since k = n, this implies that (p, r) is well-shaped. If
l = (l′ , m) but m = k = n, then (l′ , r ′ ) has to be well-shaped with respect to α and so
has to be (p′ , r ′ ) by induction, which again means that (p, r) is well-shaped with respect
to γ. If k <ω+ω∗ n and l = −∞, then (l, r) is well-c-shaped, r is in ±-form and p′ is in
+-form by Lemma 10. Therefore, (p, r) is well-π-shaped. If l = (l′ , m) for l′ ∈ dom(u)
and m ∈ N ⊎ −N and m ≤ω+ω∗ k <ω+ω∗ n, then l′ and, thus, also p′ by Lemma 10 has
to be in ∓-form while r ′ has to be in ±-form. This concludes the proof because, then,
(p, r) is well-π-shaped.
By the previous lemma, we know that there is maximally one switching between values
form −N to values from N in l below the branching position and that the same – but

42

in reverse – is true for r when we consider a pair (l, r) which arises from (−∞, +∞) by
applying a sequence of factorizations from FΣ . However, the algorithm described in the
proof of Theorem 5 performs a normalization after each factorization step. So far, we
have ignored this normalization but the next lemma states that normalization preserves
well-shapedness.
Lemma 12. Let (l, r) be a well-shaped, normalizable pair of positions in JγKω+ω∗ for a
γ
π-term γ over Σ. Then, (l, r) is well-shaped.
γ
γ
Proof. Let (l, r) = (¯l, r̄). In the special case l = −∞ and r = +∞, we have (l, r) = (l, r)
and we are done. For the other cases, we proceed by induction over γ.
γ
For γ = ε and γ ∈ Σ, we have that (l, r) is well-c-shaped. In the case γ = αβ for two
π-terms α and β, we distinguish: if l ∈ {−∞} ⊎ dom(JαKω+ω∗ ) and r ∈ dom(JβKω+ω∗ ) ⊎
{+∞}, we have that (l, r) must be well-c-shaped, that ¯l is given by the first component
α

β

of (l, +∞) and that r̄ is given by the second component of (−∞, r) . For l = −∞,
we also have ¯l = −∞ and, for r = +∞, we also have r̄ = +∞. If l 6= −∞, then l
must be in ∓-form. Note that normalization preserves the form of l when normalizing
(l, +∞), so ¯l is in ∓-from as well. Symmetrically, r̄ must be in ±-form if r 6= +∞. Thus,
γ
(l, r) is well-c-shaped. For l ∈ {−∞} ⊎ dom(JαKω+ω∗ ) and also r ∈ dom(JαKω+ω∗ ), we
γ
α
have (l, r) = (l, r) , which is well-shaped by induction. The same argument proves the
symmetric case l ∈ dom(JβKω+ω∗ ) and r ∈ dom(JβKω+ω∗ ) ⊎ {+∞}.
The remaining case is γ = (α)π for a π-term α. If we have l = −∞ or r = +∞, then
we know that l is in ∓-form or that r is in ±-form, respectively, because (l, r) has to
be well-c-shaped. As before, normalizing (−∞, r) or (l, +∞) preserves this form, which
makes the result well-c-shaped as well. Therefore, we have l = (l′ , n) and r = (r ′ , m) for
n, m ∈ N ⊎ −N and positions l′ , r ′ ∈ dom(JαKω+ω∗ ). For n = m, we have ¯l = (l¯′ , 1) and
α
α
r̄ = (r¯′ , 1) with (l¯′ , r¯′ ) = (l′ , r ′ ) . By induction, we have that (l′ , r ′ ) is well-c-shaped
or well-π-shaped with respect to α. In either case, (¯l, r̄) is also well-c-shaped or well-πshaped with respect to γ. For n 6= m, the pair (l, r) has to be well-π-shaped, l′ must be
in ∓-form and r ′ must be in ±-form. Additionally, we have ¯l = (l¯′ , n̄) and r̄ = (r¯′ , m̄)
for n̄, m̄ ∈ N ⊎ −N and positions l¯′ , r¯′ ∈ dom(JαKω+ω∗ ). Note that we also have n̄ 6= m̄
(in both of the cases which can occur when normalizing). Furthermore, normalization
of (l′ , +∞) (with respect to α) preserves the ∓-form of l′ and normalization of (−∞, r ′ )
γ
preserves the ±-form of r ′ , i. e. we have l¯′ in ∓-form and r̄ ′ in ±-form, which makes (l, r)
well-π-shaped.
Combining the previous two lemmas shows the following. Suppose we start with the
position pair (−∞, +∞) and apply a single factorization F1 ∈ FΣ , then we get (l1′ , r1′ ) =
(−∞, +∞) · F1 , which is well-shaped. If we then normalize (l1′ , r1′ ), the resulting pair
γ
(l1 , r1 ) = (l1′ , r1′ ) is also well-shaped. We can continue with another factorization and
normalize again; the result (l1 , r2 ) will still be well-shaped. Therefore, all the pairs of
positions (l, r) which are states in the deterministic finite automaton constructed in the
proof of Theorem 5 are well-shaped and normalized.
One last small observation is necessary before we discuss the details of storing those
pairs: by definition of the normalization, l and r may only have values from {1, −1} for

43

Name
ShapeType
BranchPosition
BranchValues
lSwitchPosition
rSwitchPosition
lEndPosition
rEndPosition

Values
{“well-c-shaped” , “well-π-shaped” }
a π-position or +∞
{(1, 2), (1, −1)}
a π-position or ⊥
a π-position or ⊥
a Σ-position or −∞
a Σ-position or +∞

Size
O(1)
O(log n)
O(1)
O(log n)
O(log n)
O(log n)
O(log n)

Table 1: The variables required to compute the values at π-positions and their sizes.
π-positions which are hierarchically lower than the branching position. Therefore, it is
sufficient to store the potential π-position at which the values switch (from −1 to 1 for
l or form 1 to −1 for r).
Storing a Well-Shaped, Normalized Pair. Summing up all of our observations results in
the situation which is schematically represented in Figure 8. Therefore, we can construct

values: (1, 1)
Branching, possible values:
values: −1

(1, 2) and (1, −1)
values: 1

Switching, value: 1

Switching, value: −1
values: −1

values: 1

r

l

Figure 8: Schematic representation of the possible values of a normalized pair (l, r)
the values of l and r for a normalized, well-shaped pair (l, r) of positions in JγKω+ω∗ at
all relevant π-positions in the π-term γ from the variables specified in Table 1.
We are going to explain the variables in more detail. Obviously, ShapeType gets the
value “well-c-shaped” if (l, r) is well-c-shaped and the value “well-π-shaped” if (l, r) is
well-π-shaped. For a well-c-shaped pair, we store the hierarchically lowest π-position for
which l and r share the same value in BranchPosition. If l and r differ already in the
hierarchically highest π-position, we store +∞ in BranchPosition. For well-π-shaped
pairs, we store the π-position at which l and r branch in BranchPosition and their
respective values there in BranchValues. The value of BranchValues is not relevant in

44

other cases. If there is a π-position at which the values of l switch from −1 to 1 (that
position is bound to be hierarchically lower than the branching position), then we store
the position of the first occurrence of 1 in lSwitchPosition. rSwitchPosition stores
the (potential) corresponding position for r. Finally, in lEndPosition and rEndPosition
we store the position in the π-term γ which corresponds to l or r, respectively.
One may verify that all these values can be stored in the size specified in the table,
where n is the length of the π-term γ seen as a finite word in Σ ⊎ { (, ), π }.
The variables are sufficient to compute the values of l and r at all relevant π-positions
deterministically within logarithmic space bounds. We only discuss how to do this for r,
as this version can easily be adapted for l. Assume we want to compute the value of r at a
π-position given in piPos. Notice that piPos is relevant for r if and only if rEndPosition
lies in between the opening and closing parenthesis belonging to piPos. Because finding
the matching left or right parenthesis is a simple matter of counting the opening and
closing parentheses this can be done deterministically in logarithmic space. Thus, we
may safely assume that our routine is only ever called for π-positions which are relevant
for r. To compute the value of r at piPos, we only have to know to which part of r it
belongs with respect to the schematic representation in Figure 8. The first part where
all values of r are equal to 1 consists of all π-positions which are hierarchically higher
than BranchPosition (assuming that it is not equal to ⊥), including BranchPosition if
ShapeType is “well-c-shape” or excluding if BranchPosition is “well-π-shaped”. Because
we already know that both, BranchPosition and piPos are relevant for r, checking
whether one is hierarchically higher than the other can be done by comparing their
positions in γ, which is possible in logarithmic space. The hierarchically higher one is to
the right of the lower one. If piPos belongs to the first part, we can return 1 immediately.
Next, we check whether BranchPosition is equal to piPos and ShapeType is “well-πshaped”. If this is the case, we can return the value 2 or −1 depending on the value of
BranchValues. The next part is from BranchPosition (excluding) to rSwitchPosition
(excluding). Again, we can check whether piPos belongs to this part by comparing the
position in the π-term and return 1 immediately. If piPos was not in any part so far, we
know that it belongs to the last part from rSwitchPosition (including) onwards and can
return −1. If BranchPosition is +∞ or rSwitchPosition is ⊥, then the corresponding
parts in Figure 8 simply do not exist and we can omit the respective checks.
Compute a Follow-Up Pair. Now that we know how to store the well-shaped, normalized pair (l, r) efficiently, we need to find a way to compute the normalized follow-up
pair if we apply an element from ZΣD = {XaD , YaD | a ∈ Σ, D ∈ {L, R}} (Ca,b needs to be
handled a bit differently; see below). By symmetry, we can restrict our considerations to
elements from XΣD , which means that we have to find the first a-position for an a ∈ Σ
on the right of the position l in JγKω+ω∗ for the π-term γ. For this, we use the additional
variables from Table 2.
We start by setting pBranchPosition to ⊥ and OpenParentheses to 0. CurrentPPosition gets assigned the next position to the right of the value of lEndPosition. The
algorithm now iteratively moves CurrentPPosition to the right one position at a time. If

45

Name
CurrentPPosition
pBranchPosition
OpenParentheses

Values
a position in γ
a π-position or +∞
a value to count open parentheses

Size
O(log n)
O(log n)
O(log n)

Table 2: The variables required to compute the follow-up pair and their sizes.
CurrentPPosition reaches an a-position, we are done. If CurrentPPosition reaches the
end of γ, then we know that there is no further a and we can stop. If CurrentPPosition
reaches an opening parenthesis, then we increment OpenParentheses. If CurrentPPosition reaches a closing parenthesis and pBranchPosition is ⊥, we distinguish: if OpenParentheses is > 0, then we decrement it and move on; if it is = 0, then we know that
the corresponding π-position is relevant for l. We check if the value of l at that position
is equal to −1. If that is the case, we can simply move on. If the value is from N or
< −1, then we set pBranchPosition to the π-position which corresponds to the closing
parenthesis and move CurrentPPosition to the matching opening parentheses using
OpenParentheses to count the number of opening and closing parentheses. From that
position we continue with the normal algorithm. If we then reach a closing parenthesis
and pBranchPosition is equal to CurrentPPosition, then we set pBranchPosition to ⊥
and OpenParenthesis to 0 and continue normally. Any other closing parenthesis which
is reached while pBranchPosition is not equal to ⊥ simply gets ignored.
Example 4. The only interesting part of the algorithm is that when a closing parenthesis
is reached. Therefore, we explain this part in more detail. Suppose we are in the following
situation9 and want to move to the next a:
a (1 (2 a )2

π2

b (3 c b (4 b )4

π4

)3

π3

2

l:

)1

π1

a (5 b )5

π5

c

−1

The algorithm would move CurrentPPosition to the right until it reaches (4 where OpenParentheses gets increased to 1. When )4 gets reached, OpenParentheses is set back
to 0, which triggers a different behavior when reaching )3 in the next step: pBranchPosition gets set to π3 and CurrentPPosition gets moved to (3 since l has the value
2 (and not −1) at π3 . From there, CurrentPPosition moves back to the right until it
reaches )3 because )4 simply gets ignored and because there is no a between (3 and )3 .
At )3 , OpenPrantheses and pBranchPosition are reset to 0 and ⊥. At the next closing
parenthesis )1 , the value of l gets checked again. But this time it is equal to −1 and we
continue to the right where we find the sought-after next a.
If l had had the value −2 at π1 , then the algorithm would have moved to (1 and the
next a would have been the one between (2 and )2 . In that case, pBranchPosition would
have been set to π1 when the final a is reached.
9

The numbers here do not have a special meaning other than to tell the parenthesis pairs and their
exponents apart from one another.

46

When the algorithm stops (and CurrentPPosition is not moved beyond the end of
γ) then CurrentPPosition points to the position in γ which corresponds to the next
a-position p in JγKω+ω∗ . The values at the π-positions can be reconstructed from the
stored variables. Again, this can be done by dividing the π-positions into parts for which
the value is well-known. If a π-position is relevant for p but not for l, then the value of
p at that position has to be 1.
Example 5. In the last example π2 , π4 and π5 are not relevant for l. If CurrentPPosition
would end up within the pair of parentheses belonging to any of these positions, its value
there would be 1.
If pBranchPosition has a value other than ⊥, then p has the value of l plus 1 there.
Note that the value of l cannot be −1 in that case by the definition of the algorithm. For
π-positions which are relevant for l and for p and which are hierarchically higher than
the position in pBranchPosition, we know that the values of l and p are equal. At those
positions which are hierarchically lower than pBranchPosition and which are relevant
for l and for p, the value of p has to be 1 just like in the first case. If pBranchPosition
is ⊥, then the values of p at positions relevant for l and for p are equal to the values of l.
Because – as said – it can be checked in logarithmic space whether a π-position is
relevant for l, p or r, this yields a deterministic algorithm with logarithmic space bounds
for calculating the values for p at all its relevant π-positions. It remains to test whether
p is still strictly smaller than r and to compute the new values of the variables in Table 1
after an XaD -step and normalization. This test can be done by walking through all πpositions in γ from the right to the left and checking whether they are relevant for p and
for r. If that is the case, we check their values. If the value of p is strictly smaller than
that of r, we are done. If they are equal everywhere, then CurrentPPosition needs to
be to the left of rEndPosition in γ.
For calculating the new values for the variables, a similar approach can be applied.
Consider the (slightly more difficult) case of XaR where p gets the new l. We walk through
the π-positions in γ from right to left and check their relevance for p and for r. If they
are relevant for one or the other, we can compute the values. As long as the values are
equal (which means that the position is relevant for both, p and r) we know that the
π-positions belong to the part in Figure 8 where l and r share the value 1. If there is a
π-position where the values are different, we can store that position in BranchPosition
and update BranchValues according to the value pair which normalization would yield.
In that case, we can set ShapeType to “well-π-shaped”. After the BranchPosition, we
have to check p and r individually for a change from values in N to values in −N or vice
versa and store the corresponding position. If the values at all positions have been equal
so far and we reach a position which is relevant for r but not for p (the other way round is
not possible because p has to be smaller than r), we can set ShapeType to “well-c-shaped”
and BranchPosition to the last π-position where the values were equal. ShapeType gets
also set to “well-c-shaped” if we reach rEndPos before there is a difference in the values.
Special Handling of Ca,b . By Theorem 3, we have to test whether JαKω+ω∗ ≡WI
m JβKω+ω ∗
holds in order to test whether α = β holds in Rm+1 ∩ Lm+1 . The definition of ≡WI
m ,

47

however, does not only rely on factorizations at the first or last a. It uses an additional
special factorization which behaves like first factorizing on the first a and then factorizing
on the last b but which is only possible if the first a is to the right of the last b. As defined
above, this kind of factorization is represented by Ca,b .
Clearly, (l, r) · Ca,b can only be defined if (l, r) · Xa Yb is defined. But the other direction
does not hold: it is possible that (l, r) · Xa Yb is defined while (l, r) · Ca,b is undefined.
We have described how we can compute the follow-up values of the variables in Table 1
for a factorization at the first a and, by symmetry, also for factorizations at the last b
when we start with a factor which is given by a normalized pair (l, r). We can combine
these two calculations into a single one for Ca,b . For this, we assume that we have two
instances of the variables in Table 2, one instance for the factorization at the first a and
one instance for the factorization at the last b. For both instances, we apply the normal
algorithm for the corresponding factorization. Afterwards, we check whether the position
of the first a is to the left of r and whether the position of the last b is to the right of
l just like we did before. For Ca,b , we simply add a third check which can be done in
a similar manner to the other checks: we check whether the position of the first a is to
the right of the position of the last b. If this check fails, then we know that (l, r) · Ca,b is
undefined, otherwise it indeed is defined.
Decidability in Nondeterministic Logarithmic Space. Let us recapitulate the proof for
decidability for the word problems for π-terms. First, we saw that the actual problem
we needed to decide was whether JαKω+ω∗ and JβKω+ω are equivalent with respect to the
relation belonging to the variety in question. To decide this, we constructed a deterministic finite automata Aα and Aβ for each of the input π-terms α and β. The automaton
Aα accepted exactly those factorization sequences F ∈ FΣ∗ for which JαKω+ω∗ · F (or
JβKω+ω∗ · F in the case of Aβ ) is defined. Additionally, we also constructed a deterministic finite automaton B which accepted those factorization sequences that need to be
tested for the respective relation. Finally, we created for Aα and for Aβ an automaton
accepting the intersection with the sequences accepted by B. For these automata, we
checked the symmetric difference for emptiness.
Checking the symmetric difference can be done in nondeterministic logarithmic space
by a naïve (iterative) guess and check algorithm. The automaton B is fixed for every
variety in the Trotter-Weil Hierarchy and for DA (or can be constructed deterministically
in space logarithmic in m if one considers this as an input). Creating an automaton for
the intersection can be done in deterministic logarithmic space. The only interesting
operation is the construction of Aα and Aβ . With the ideas from this section, we can
describe how to do this in deterministic logarithmic space.
Input: a π-term α
Output: Aα (which accepts a subset of FΣ∗ )
Algorithm:
for all possible values V of the variables in Table 1 do
for all F ∈ FΣ do

48

Compute the values V ′ of the variables for the follow-up pair after
application of F and normalization.
If there is such a follow-up pair, then output the transition
F

V

V′

end for
end for
Mark the state which represents (−∞, +∞) as initial state.
Mark any state as final.
In difference to our previous construction, the states in this automaton are not the
normalized pairs of positions anymore. Instead, we are representing them by their corresponding values for the variables in Table 1. Of course, not all possible values of the
variables represent a valid normalized pair, but, since the corresponding states cannot
be reached from the initial state, these errors do not affect the result.
These considerations allow us to state the following theorem.
Theorem 6. Each of the word problems for π-terms over Rm , Lm , Rm ∨ Lm , Rm ∩ Lm
and DA can be solved by a nondeterministic Turing machine in logarithmic space (for
every m ∈ N).

9 Deterministic Polynomial Time
While NL is quite efficient from a complexity class perspective, directly translating the
algorithm to polynomial time does not result in a better running time than the algorithm
for DA given by Moura [18]. However, with some additional tweaks, the algorithm’s
efficiency can be improved.
Encoding and Calculating Positions. Because we are not limited in space, we can
encode a position p ∈ dom(w) with w = JγKω+ω∗ for a π-term γ simply by storing the
values at the relevant π-positions and the corresponding position in γ. Clearly, we can
obtain the values of p at a given π-position in constant time. Additionally, we can store
a (possibly normalized) pair (l, r) by storing l and r. If we want to normalized such a
pair, we walk through all relevant π-positions and update the values of l and r there,
which requires at most linear time. Similarly, we can test whether a position is strictly
smaller (or larger) than an other position in linear time.
Suppose we have stored a position p ∈ dom(w) and want to compute Xa (w; p) for an
a ∈ Σ. We can re-use the algorithm which we used previously to solve the problem in
logarithmic space (see page 45). This algorithm moves a pointer, which belongs to a
position in γ, to the right in every step. The only time it is moved to the left is when it
hits a closing parenthesis and p has a value at the corresponding π-position which is not
−1. In that case, we move to the matching opening parenthesis and continue to move
to the right from there until we hit the closing parenthesis again. Note that there is no

49

“back-setting to the left” in that process. Therefore, we can compute the position of the
next a in at most quadratic time.
Computing the Automata and Equivalence Test. As we did before, we construct
a (not necessarily complete) deterministic finite automaton for each input π-term γ.
The automaton accepts exactly those sequences of factorizations which can be applied to
JγKω+ω∗ and which need to be tested for the variety in question. We will only demonstrate
the details of the construction for the variety Rm+1 ∩ Lm+1 and the input term α; the
construction for the other varieties is similar. We need the variables core and fringe,
which contain subsets of (dom(u) × dom(u)) × {1, 2, . . . , m} where u = JγKω+ω∗ such that
all pairs (l, r) ∈ dom(u) × dom(u) are normalized. The algorithm works as follows:
core ← ∅
fringe ← {((−∞, +∞), m)}
while fringe 6= ∅ do
Remove ((l, r), k) from fringe
if k > 0 then
for all a ∈ Σ do
Compute (l′ , r ′ ) = (l, r) · XaL if defined
⊲ time limited by O(n2 )
′
′
if (l , r ) is defined then
α
⊲ time limited by O(n)
(¯l′ , r̄ ′ ) ← (l′ , r ′ )
Save transition
(l, r)
k

XaL

(¯l′ , r̄ ′ )
k−1

Add ((¯l′ , r̄ ′ ), k − 1) to fringe unless it is in core
end if
Compute (l′ , r ′ ) = (l, r) · XaR if it is defined
if (l′ , r ′ ) is defined then
α
(¯l′ , r̄ ′ ) ← (l′ , r ′ )
Save transition
(l, r)
k

XaR

(¯l′ , r̄ ′ )
k

Add ((¯l′ , r̄ ′ ), k) to fringe unless it is in core
end if
Handle YaL and YaR analogously
for all b ∈ Σ do
⊲ Special case which is only required for ≡WI
m
′
′
Compute (l , r ) = (l, r) · Ca,b if it is defined
if (l′ , r ′ ) is defined then
α
(¯l′ , r̄ ′ ) ← (l′ , r ′ )

50

Save transition
(l, r)
k

Ca,b

(¯l′ , r̄ ′ )
k−1

Add ((¯l′ , r̄ ′ ), k − 1) to fringe unless it is in core
end if
end for
end for
Add ((l, r), k) to core
end if
end while
Set ((−∞, +∞), m) as initial state
Mark all states as final states
Clearly, the resulting automaton accepts the desired factorization sequences. We know
that any normalized pair can be encoded by the variables in Table 1. Therefore, the
number of such pairs is limited by O(n5 ) when n is the length of γ seen as a finite word.
This directly yields that the constructed automaton has at most O(n5 m) states. Because
the outer loop handles any ((l, r), k) at most once the algorithm’s running time is limited
by O(n7 m).
After the construction of the two automata for α and β, we need to test them for
equivalence. They are equivalent if and only if JαKω+ω∗ ≡WI
m JβKω+ω ∗ holds. The test for
equivalence can be done by the algorithm of Hopcroft and Karp [9] in almost linear time
in the size of the automata. Since the number of states is bounded by O(n5 m), the total
running time of our complete algorithm is dominated by O(n7 m2 ).
The automata for the varieties Rm , Lm and Rm ∨ Lm need to store whether the last
factor was obtained by an element from XΣD or by an element from YΣD . This information,
however, is only of constant size and, therefore, does not change the asymptotic running
time of the overall algorithm. For DA we can omit the counting for m in k by Fact 1,
which even reduces the number of states.
This finally shows the following theorem.
Theorem 7. The word problems for π-terms over Rm , Lm , Rm ∨ Lm and Rm ∩ Lm
can be solved by a deterministic algorithm with running time in O(n7 m2 ) where n is the
length of the input π-terms. Moreover, the word problem for π-terms over DA can be
solved by a deterministic algorithms in time O(n7 ).

10 Separability
Two languages L1 , L2 ⊆ Σ∗ are separable by a variety V if there is a language S ⊆ Σ∗
with L1 ⊆ S and L2 ∩ S = ∅ such that S can be recognized by a monoid M ∈ V. The
separation problem of a variety V is the problem to decide whether two regular input
languages of finite words are separable by V.

51

We are going to show the decidability of the separations problems of Rm for all m ∈ N
as well as for DA using the techniques presented in this paper10 . Note that, by symmetry,
this also shows decidability for Lm .
The general idea is as follows. If the input languages are separable, then we can find
a separating language S which is recognized by a monoid in the variety in question. We
can do this by recursively enumerating all monoids and all languages in a suitable representation. For the other direction, we show that, if the input languages are inseparable,
then there are π-terms α and β which witness their inseparability. Since we can also
recursively enumerate these π-terms, we have decidability.
To construct suitable π-terms we need an additional combinatorial property of the
≡X
m,n relations (which, in a slightly different form, can also be found in [15]).
Lemma 13. Let n, m ∈ N with m ≥ 2 and let u ≡X
m,n v for two accessible words u and
L
L
X
v. Then, u · Xa ≡m,n−1 v · Xa holds for all a ∈ alph(u) = alph(v).
Proof. We prove the lemma by induction over n. For n = 1, the assertion is satisfied by
X
L
definition. Therefore, assume we have u ≡X
m,n+1 v and we want to show u0 := u·Xa ≡m,n
Y
X
L
v · Xa =: v0 . We already have u0 ≡m−1,n v0 by definition of ≡m,n+1 . This especially
implies alph(u0 ) = alph(v0 ) since we have m ≥ 2 and n ≥ 1, as well as u0 ≡Ym−1,n−1 v0 .
Additionally, we have
u0 · XbL = u · XbL ≡Ym−1,n v · XbL = v0 · XbL
for all b ∈ alph(u0 ) = alph(v0 ), which implies u0 · XbL ≡Ym−1,n−1 v0 · XbL . All that remains
R
to be shown is that u0 ·XbR ≡X
m,n−1 v0 ·Xb holds for all b ∈ alph(u0 ) = alph(v0 ). Applying
R L
R
R L
X
induction on u · XbR ≡X
m,n v · Xb (for the same a) yields u · Xb Xa ≡m,n−1 v · Xb Xa .
R
L
R
R
L
R
L
R
R
Since we have u0 · Xb = u · Xa Xb = u · Xb Xa and v0 · Xb = v · Xa Xb = v · Xb XaL ,
we are done.
Using this property, one can prove the following lemma about the π-term construction.
Lemma 14. Let M be a monoid, ϕ : Σ∗ → M a homomorphism and m ∈ N0 . Let
(un , vn )n∈N0 be an infinite sequence of word pairs (un , vn )n∈N0 with
• u n , vn ∈ Σ ∗ ,

• ϕ(un ) = mu and

• un ≡ X
m,n vn ,

• ϕ(vn ) = mv

for fixed monoid elements mu , mv ∈ M and all n ∈ N0 . Then, the sequence yields π-terms
α and β (over Σ) such that ϕ (JαKM ! ) = mu , ϕ (JβKM ! ) = mv and JαKω+ω∗ ≡X
m JβKω+ω ∗
hold.
10

Decidability of the separation problem of DA is already known [21]. The proof, however, uses a fixed
point algorithm, which is different from our approach.

52

Before we give a proof of the general case, we give a separate one for the case m = 1. It is
basically an adaption of the ideas from the proof showing decidability of the separation
problem for the variety J of J -trivial monoids given by van Rooijen and Zeitoun [29] to
our setting.
Proof (m = 1). This proof is based on Simon’s Factorization Forest Theorem [25]. For
a finite word w ∈ Σ+ , a factorization tree is a rooted, finite, unranked, labeled ordered
tree such that
• the tree’s root is labeled with w,
• the leaves are labeled with letters (from Σ) and
• any internal node has at least two children and, if its children are labeled with
w1 , w2 , . . . , wk ∈ Σ+ , then the node is labeled with w1 w2 . . . wk .
For every homomorphism ψ : Σ∗ → N into a monoid N , Simon’s Factorization Forest
Theorem yields a factorization tree for every finite word w ∈ Σ+ such that ψ maps the
labels of a node’s children to the same idempotent in N if the node has at least three
children. Furthermore, the tree’s height11 is finite and limited by some constant that
solely depends on |N | (and, in particular, not on w).
Before we begin with the actual proof, we note that, if we remove pairs from the
sequence (un , vn )n∈N0 and still have an infinite sequence, then the resulting sequence still
satisfies all conditions stated above, in particular un ≡X
1,n vn .
∗
Σ
We extend ϕ into a homomorphism Σ → M ×2 which maps a word w to its alphabet
alph(w) for the second component.12 Then, we observe that there has to be an infinite
subsequence such that all first components as well as all second components have the
same alphabet. Indeed, these two alphabets have to coincide by the definition of ≡X
1,n !
We remove all other words from the sequence. If the remaining words un and vn are all
empty (i. e. they have alphabet ∅), we can choose α = β = ε as well. Otherwise, we apply
Simon’s Factorization Forest Theorem to the remaining words un and vn , which yields
a sequence of factorization tree pairs (Tu,n , Tv,n ). We first construct α from (Tu,n )n∈N0
such that we have ϕ(JαKM ! ) = mu and the following conditions:
• If w ∈ Σ∗ is a subword13 of un for an n ∈ N0 , then w is a subword of JαKω+ω∗ .
• If w ∈ Σ∗ is a subword of JαKω+ω∗ , then it is a subword of all un with n ≥ n0 for
an n0 ∈ N0 .
Afterwards, we proceed with (Tv,n )n∈N0 to construct β in the same manner.
We may assume that all trees Tu,n have the same height H as the height is bounded
by a constant and we can remove all words un from the underlying sequence which yield
a tree not of height H. If H is zero, all trees consist of a single leaf and all words un
11

A single node has height 0.
2 is the monoid of all subsets of Σ with taking union as the monoid’s operation.
13
Recall that a finite word u = a1 a2 . . . an with ai ∈ Σ is a subword of a (not necessarily finite) word v
if we can write v = v0 a1 v1 a2 v2 . . . an vn for some words v0 , v1 , . . . , vn .

12 Σ

53

consist of a single letter. Among these, one letter a ∈ Σ has to appear infinitely often;
we remove all other words from the sequence and choose α = a. Clearly, all conditions
for α are satisfied.
For H > 0, we consider the situation at the root of each Tu,n . Let un,1 , un,2 , . . . , un,Kn
be the labels of the root’s children in Tu,n . If the sequence (Kn )n∈N0 is bounded, there
is an infinite subsequence such that Kn is equal to a specific K ≥ 2 for all indexes n of
the subsequence; we remove all words not belonging to this subsequence. In the result,
there is an infinite subsequence such that, for each sequence (un,k )n∈N0 with 1 ≤ k ≤ K,
all un,k get mapped to the same monoid element by ϕ; we remove all other words. As
each child of the root yields a subtree, taking these subtrees gives K infinite sequences
of factorization trees of height H − 1. Applying induction on H yields α1 , α2 , . . . , αK .
We define α := α1 α2 . . . αK . Because α1 , α2 , . . . , αK satisfy the conditions stated above
for their respective subtree sequence, so does α for (Tu,n )n∈N0 .
If the sequence (Kn )n∈N0 is unbounded, we can, without loss of generality, assume
Kn ≥ 3 for all n ∈ N0 and that it is strictly increasing – again taking the appropriate
infinite subsequence. Also, we can assume that all un,1 , un,2 , . . . , un,Kn get mapped to the
same idempotent e ∈ M × 2Σ . Choose w ∈ ϕ−1 (e) arbitrarily and define α := (w)π . Note
that we now have alph(un,1 ) = alph(un,2 ) = · · · = alph(un,Kn ) = alph(un ) = alph(w) for
all n ∈ N0 . Therefore, α satisfies the conditions above.
All which remains to be shown is that we now have JαKω+ω∗ ≡X
1 JβKω+ω ∗ . The imw
with
n
∈
N
holds
if
and
only if w1 and w2
portant observation here is that w1 ≡X
2
0
1,n
have the same subwords of length ≤ n. This means we have to show that JαKω+ω∗ and
JβKω+ω∗ have the same subwords (of arbitrary length). To show the subword equality,
assume w is a subword of JαKω+ω∗ (without loss of generality). By the conditions above,
w is a subword of all un with n ≥ n0 for an n0 ∈ N0 . Let ñ = max{n0 , |w|}. Since we
X
have uñ ≡X
1,ñ vñ and by applying our observation regarding subwords and ≡1,ñ , w is a
subword of vñ and, thus, a subword of JβKω+ω∗ .
Next, we give a proof for the general case m ≥ 1.
Proof of Lemma 14. The assertion is trivial for m = 0. The case m = 1 has already
been covered. For m > 1, we proceed by induction over |Σ|. For Σ = ∅, we set α =
β = ε = un = vn . For |Σ| > 0, remember the observation from the previous proof: if we
take an infinite subsequence (u′n , vn′ )n∈N0 of (un , vn )n∈N0 , this sequence will still satisfy
′
all conditions of the lemma. In particular, we will still have u′n ≡X
m,n vn for all n ∈ N0 .
Now, we factorize un = wn,0 an,0 wn,1 an,1 . . . wn,Kn an,Kn wn,Kn +1 for all n ∈ N0 such that
alph(wn,k ) = alph(un ) \ {an,k } for all k ∈ {0, 1, . . . , Kn } and alph(wn,Kn +1 ) ( alph(un ).
If the sequence (Kn )n∈N0 is bounded, let K be one of the numbers which appear infinitely
often in it and restrict all further considerations to the corresponding subsequence of
words. If (Kn )n∈N0 is unbounded, let K = |M |2 + 1 and remove all word pairs (un , vn )
for which Kn is smaller than K from the sequence. For all k ∈ {0, 1, . . . , K}, a single
letter ak ∈ Σ has to appear infinitely often in the sequence (an,k )n∈N0 because Σ is of finite
size. We restrict our consideration to the corresponding subsequence. Then, we define
xn,k = un ·XaR0 XaR1 . . . XaRk−1 XaLk and yn,k = vn ·XaR0 XaR1 . . . XaRk−1 XaLk for k ∈ {0, 1, . . . , K}

54

as well as xn,K+1 = un · XaR0 XaR1 . . . XaRK and yn,K+1 = vn · XaR0 XaR1 . . . XaRK . We, thus,
have un = xn,0 a0 xn,1 a1 . . . xn,K aK xn,K+1 and vn = yn,0 a0 yn,1 a1 . . . yn,K aK yn,K+1 for all
n ∈ N0 . Because K is constant, we can safely assume that ϕ maps all elements of the
sequence (xn,k )n∈N0 (for every k ∈ {0, 1, . . . , K + 1}) to the same element sk ∈ M : one
element has to appear infinitely often and we take the corresponding subsequence. In
the same way, we can ensure that ϕ maps all element of (yn,k )n∈N0 to the same element
tk ∈ M (again, for all k ∈ {0, 1, . . . , K + 1}). By removing the first K + 2 pairs of words,
X
we can also ensure un ≡X
m,n+K+2 vn for all n ∈ N0 . This implies xn,k ≡m,n+K+2−k−1 yn,k
for all n ∈ N0 and all k ∈ {0, 1, . . . , K} by Lemma 13. Directly by the definition of ≡X
m,n ,
X
X
we already have xn,K+1 ≡m,n+K+2−K−1 yn,K+1 and, therefore, xn,k ≡m,n yn,k for all k ∈
{0, 1, . . . , K+1}. We can apply induction to (xn,k , yn,k )n∈N0 for k ∈ {0, 1, . . . , K} since we
have ak 6∈ alph(xn,k ) by construction. This yields π-terms α0 , α1 , . . . , αK , β0 , β1 , . . . , βK .
If (Kn )n∈N0 was bounded, then alph(xn,K+1 ) = alph(yn,K+1) ( alph(un ) = alph(vn )
holds and we can apply induction as well, which yields π-terms αK+1 and βK+1 . Setting
α = α0 a0 α1 a1 . . . αK aK αK+1 and β = β0 a0 β1 a1 . . . βK aK βK+1 satisfies JαKω+ω∗ ≡X
m
2 +1
is
a
congruence.
If
(K
)
was
unbounded,
we
set
K
=
|M
|
JβKω+ω∗ since ≡X
n
n∈N
m
0
and, by the pigeon hole principle, there are i, j ∈ {0, 1, . . . , K} with i < j and
s0 ϕ(a0 )s1 ϕ(a1 ) . . . si ϕ(ai ) = s0 ϕ(a0 )s1 ϕ(a1 ) . . . sj ϕ(aj ) and
t0 ϕ(a0 )t1 ϕ(a1 ) . . . ti ϕ(ai ) = t0 ϕ(a0 )t1 ϕ(a1 ) . . . tj ϕ(aj ).
We define
α = α0 a0 α1 a1 . . . αi ai (αi+1 ai+1 αi+2 ai+2 . . . αj aj )π αK+1 and
β = β0 a0 β1 a1 . . . βi ai (βi+1 ai+1 βi+2 ai+2 . . . βj aj )π βK+1
where αK+1 and βK+1 are obtained by using induction on m (and symmetry) for the sequences (xn,K+1 )n∈N0 and (yn,K+1)n∈N0 , i. e. we have ϕ(JαK+1 KM ! ) = sK+1 , ϕ(JβK+1 KM ! ) =
tK+1 and JαK+1 Kω+ω∗ ≡Ym−1 JβK+1 Kω+ω∗ . Therefore, we have ϕ (JαKM ! ) = mu and
ϕ (JβKM ! ) = mv by construction. We also have JαKω+ω∗ ≡X
m JβKω+ω ∗ : for the part left
π
up to and including the (·) , we have equivalence by induction and because ≡X
m is a
congruence; the right part, we cannot reach by arbitrarily many XaD factorizations since
all letters appear infinitely often in the (·)π part and, if we reach it by using at least one
YaD factorization, we are done since we have JαKω+ω∗ ≡Ym−1 JβKω+ω∗ .
We can now plug everything together and prove the following theorem.
Theorem 8. For each m ∈ N, the separation problem for Rm is decidable and so is the
one for Lm .
Proof. We only consider Rm as the case for Lm is symmetric. If the input languages
are separable, we can find a separating language by enumerating all candidates. If the
languages are inseparable, we have to apply the previous lemma. As regular languages,
the input languages L1 ⊆ Σ∗ and L2 ⊆ Σ∗ can be recognized by monoids M1 and M2
via the homomorphisms ϕ1 and ϕ2 and the homomorphism can be computed. Therefore,

55

they are also recognized by M := M1 × M2 via the homomorphism ϕ which maps a finite
word to a pair whose first component is determined by ϕ1 and whose second component
is determined by ϕ2 . Let n ∈ N0 be arbitrary. Since we have Σ∗ /≡X
m,n ∈ Rm and
since L1 and L2 cannot be separated by Rm , there have to be finite words un , vn ∈ Σ∗
with un ∈ L1 , vn ∈ L2 and un ≡X
m,n vn ; otherwise, we could construct a separating
language. The homomorphism ϕ has to map infinitely many elements of the sequence
(un , vn )n∈N0 to the same element in M since M is finite. If we remove all other elements,
we still have an infinite sequence (un , vn )n∈N0 with un ≡X
m,n vn for all n ∈ N0 which
also satisfies all conditions of Lemma 14. Therefore, there are π-terms α and β with
JαKω+ω∗ ≡X
m JβKω+ω ∗ , ϕ (JαKM ! ) ∈ ϕ(L1 ) and ϕ (JβKM ! ) ∈ ϕ(L2 ). Since we can test
whether JαKω+ω∗ ≡X
m JβKω+ω ∗ holds for any two π-terms α and β by Theorem 5, we can
also recursively enumerate all possible π-term pairs and check whether the conditions
above are met. We know that we can find such a pair if L1 and L2 are inseparable. On
the other hand, suppose L1 and L2 can be separated by S ⊆ Σ∗ which is recognized
by the monoid N ∈ Rm via a homomorphism ψ : Σ∗ → N and we have found a
pair α and β with JαKω+ω∗ ≡X
m JβKω+ω ∗ , ϕ (JαKM ! ) ∈ ϕ(L1 ) and ϕ (JβKM ! ) ∈ ϕ(L2 ).
Then, we have ϕ (JαKN !·M !) = ϕ (JαKM ! ) ∈ ϕ(L1 ) and, thus, JαKN !·M ! ∈ L1 as well as
JβKN !·M ! ∈ L2 (by a similar argument). Also, α = β holds in Rm by Theorem 4, which
implies s := ψ (JαKN !·M ! ) = ψ (JαKN ! ) = ψ (JβKN ! ) = ψ (JβKN !·M ! ). If we have s ∈ ψ(S),
then we have JβKN !·M ! ∈ S ∩ L2 ; otherwise, we have JαKN !·M ! ∈ L1 but JαKN !·M ! 6∈ S and,
thus, a contradiction in either case.
Since two languages are separable by Rm for m = |Σ| + 1 if they are separable by DA
[30], we also get decidability of the separation problem of DA, which has already been
shown by Place, van Rooijen and Zeitoun [21].
Corollary 3. The separation problem for DA is decidable.

References
[1] Jorge Almeida. Implicit operations on finite J -trivial semigroups and a conjecture
of I. Simon. Journal of Pure and Applied Algebra, 69(3):205 – 218, 1991.
[2] Jorge Almeida. Finite Semigroups and Universal Algebra. World Scientific, 1994.
[3] Jorge Almeida. Finite semigroups: an introduction to a unified theory of pseudovarieties. In G.M̃. dos Gomes Moreira da Cunha, Pedro Ventura Alves da Silva, and
Jean-Éric Pin, editors, Semigroups, Algorithms, Automata and Languages, pages
3–64. World Scientific, 2002.
[4] Jorge Almeida and Marc Zeitoun. An automata-theoretic approach to the word
problem for ω-terms over R. Theoretical Computer Science, 370(1):131–169, 2007.
[5] Volker Diekert, Paul Gastin, and Manfred Kufleitner. A survey on small fragments
of first-order logic over finite words. Int. J. Found. Comput. Sci., 19:513–548, 2008.

56

[6] Samuel Eilenberg. Automata, Languages, and Machines, volume B. Academic press,
1976.
[7] J. A. Gerhard and Mario Petrich. Varieties of bands revisited. Proceedings of the
London Mathematical Society, 58(3):323–350, 1989.
[8] Tom E. Hall and Pascal Weil. On radical congruence systems. Semigroup Forum,
59(1):56–73, 1999.
[9] John E. Hopcroft and Richard M. Karp. A linear algorithm for testing equivalence
of finite automata. Technical report, Cornell University, 1971.
[10] Martin Huschenbett and Manfred Kufleitner. Ehrenfeucht-Fraïssé games on omegaterms. In Ernst W. Mayr and Natacha Portier, editors, STACS 2014, Proceedings,
volume 25 of LIPIcs, pages 374–385, Dagstuhl, Germany, 2014. Dagstuhl Publishing.
[11] Kenneth Krohn, John Lewis Rhodes, and Bret Tilson. Homomorphisms and semilocal theory. In Michael A. Arbib, editor, Algebraic Theory of Machines, Languages,
and Semigroups, chapter 8, pages 191–231. Academic Press, New York and London,
1968.
[12] Manfred Kufleitner and Alexander Lauser. The join levels of the Trotter-Weil Hierarchy are decidable. In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer,
editors, MFCS 2012, Proceedings, volume 7464 of LNCS, pages 603–614. Springer,
2012.
[13] Manfred Kufleitner and Pascal Weil. On the lattice of sub-pseudovarieties of DA.
Semigroup Forum, 81:243–254, 2010.
[14] Manfred Kufleitner and Pascal Weil. The FO2 alternation hierarchy is decidable. In
Patrick Cégielski and Arnaud Durand, editors, CSL 2012, Proceedings, volume 16
of LIPIcs, pages 426–439, Dagstuhl, Germany, 2012. Dagstuhl Publishing.
[15] Manfred Kufleitner and Pascal Weil. On logical hierarchies within FO2 -definable
languages. Logical Methods in Computer Science, 8(3):1–30, 2012.
[16] Kamal Lodaya, Paritosh K. Pandya, and Simoni S. Shah. Marking the chops: an
unambiguous temporal logic. In IFIP TCS 2008, Proceedings, IFIP, pages 461–476.
Springer, 2008.
[17] Jonathan P. McCammond. Normal forms for free aperiodic semigroups. Int. J.
Algebra Comput., 11(5):581–625, 2001.
[18] Ana Moura. The word problem for ω-terms over DA. Theoretical Computer Science,
412(46):6556–6569, 2011.
[19] Dominique Perrin and Jean-Éric Pin. Infinite words, volume 141 of Pure and Applied
Mathematics. Elsevier, Amsterdam, 2004.

57

[20] Jean-Éric Pin. Varieties of Formal Languages. North Oxford Academic Publishers
Ltd, 1986.
[21] Thomas Place, Lorijn van Rooijen, and Marc Zeitoun. Separating regular languages
by piecewise testable and unambiguous languages. In MFCS 2013, Proceedings,
pages 729–740. Springer, 2013.
[22] Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8:190–194, 1965.
[23] Thomas Schwentick, Denis Thérien, and Heribert Vollmer. Partially-ordered twoway automata: A new characterization of DA. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, DLT 2001, Proceedings, volume 2295 of LNCS,
pages 239–250. Springer, 2002.
[24] Imre Simon. Piecewise testable events. In Autom. Theor. Form. Lang., 2nd GI
Conf., volume 33 of LNCS, pages 214–222. Springer, 1975.
[25] Imre Simon. Factorization forests of finite height. Theoretical Computer Science,
72(1):65–94, 1990.
[26] Pascal Tesson and Denis Thérien. Diamonds are forever: The variety DA. In
Gracinda Maria dos Gomes Moreira da Cunha, Pedro Ventura Alves da Silva, and
Jean-Éric Pin, editors, Semigroups, Algorithms, Automata and Languages, pages
475–500. World Scientific, 2002.
[27] Denis Thérien and Thomas Wilke. Over words, two variables are as powerful as one
quantifier alternation. In Proceedings of the Thirtieth Annual ACM Symposium on
Theory of Computing, pages 234–240. ACM, 1998.
[28] Peter Trotter and Pascal Weil. The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue. Algebra Universalis, 37(4):491–526, 1997.
[29] Lorijn van Rooijen and Marc Zeitoun. The separation problem for regular languages
by piecewise testable languages. CoRR, abs/1303.2143, 2013.
[30] Philipp Weis and Neil Immerman. Structure Theorem and Strict Alternation Hierarchy for FO2 on Words. Logical Methods in Computer Science, 5(3):1–23, 2009.

58

