Efficient Algorithms for Morphisms over
Omega-Regular Languages
Lukas Fleischer

Manfred Kufleitner

arXiv:1509.06215v2 [cs.FL] 9 Nov 2015

FMI, University of Stuttgart∗
{fleischer,kufleitner}@fmi.uni-stuttgart.de
Abstract. Morphisms to finite semigroups can be used for recognizing
omega-regular languages. The so-called strongly recognizing morphisms
can be seen as a deterministic computation model which provides minimal objects (known as the syntactic morphism) and a trivial complementation procedure. We give a quadratic-time algorithm for computing
the syntactic morphism from any given strongly recognizing morphism,
thereby showing that minimization is easy as well. In addition, we give
algorithms for efficiently solving various decision problems for weakly
recognizing morphisms. Weakly recognizing morphism are often smaller
than their strongly recognizing counterparts. Finally, we describe the
language operations needed for converting formulas in monadic secondorder logic (MSO) into strongly recognizing morphisms, and we give
some experimental results.

1 Introduction
Automata over finite words have a huge number of effective closure properties. Moreover, many problems such as minimization or equivalence of deterministic automata
admit very efficient algorithms [5, 6]. The situation over infinite words is quite similar, but with the major difference that many operations are less efficient. There
are many different automaton models for accepting languages of infinite words, the
so-called ω-regular languages. Each of these models has its advantages and disadvantages. For instance, deterministic Büchi automata are less powerful than nondeterministic Büchi automata [14]. And only very few automaton models admit
efficient minimization algorithms; for example, minimization of deterministic finite
automata can be applied to the lasso automata in [2].
∗

This work was supported by the DFG grants DI 435/5-2 and KU 2716/1-1.

1

The theory of finite semigroups and automata is tightly connected [10]. Since
the semigroup for a language can be exponentially bigger than its automaton, semigroups have very rarely been considered in the context of efficient algorithms. There
is also an algebraic approach to ω-regular languages by using morphisms to finite
semigroups, see e.g. [8, 14]. Among the many nice properties of this approach are
minimal morphisms — the so-called syntactic morphisms — and easy complementation. As for finite words, the semigroup for an ω-regular language can be exponentially bigger than its Büchi automaton. However, since many operations for
ω-regular languages are less efficient than for regular languages over finite words,
the drawback of this exponential blow-up in size is less serious. This is even more
so when minimizing all intermediate objects.
A typical algorithm for computing the syntactic morphism of a regular language
over finite words is to minimize the (deterministic) automaton defined by the Cayley
graph of a morphism, and then the syntactic morphism is given by the transition
semigroup of the minimal automaton. This approach does not work for infinite words
and we therefore give a direct algorithm for computing the syntactic morphism. Our
algorithm is an adaptation of Hopcroft’s minimization algorithm [5] and its running
time is quadratic in the size of the semigroup. We show that this is rather optimal.
There are two different modes for recognizing omega-regular languages by a morphism to a finite semigroup: weak and strong recognition. Strong recognition is a
special case of weak recognition. Easy complementation and the computation of the
syntactic morphism only works for strong recognition. We show how to test whether
a given weak recognition is actually strong. Another useful tool for morphisms is
the computation of the so-called conjugacy classes.
As an application, we consider the translation of MSO formulas into strongly recognizing morphisms. To this end, we show that a powerset construction preserves
strong recognition, and that this construction can be used for computing the image under a length-preserving morphism. Finally, we give the test results of some
translations from MSO to strong recognition. Deciding the satisfiability of an MSO
formula is non-elementary [12] and therefore, minimization of intermediate objects
is usually very helpful for solving some special cases. This is confirmed by our test
results.

2 Preliminaries
Words. Let A be a finite alphabet. The elements of A are called letters. A finite
word is a sequence a1 a2 · · · an of letters of A and an infinite word is an infinite sequence a1 a2 · · · . The empty word is denoted by ε. The set of non-empty finite words
over A is A+ . Let K be a set of finite words and let L be a set of infinite words. We set
KL = {uα | u ∈ K, α ∈ L}, K + = {u1 u2 · · · un | n > 1, ui ∈ K} and K ∗ = K + ∪ {ε}.
Moreover, if ε 6∈ K we define the infinite iteration K ω = {u1 u2 · · · | ui ∈ K}. A
natural extension to K ⊆ A∗ is K ω = (K \ {ε})ω .

2

Finite semigroups. Let S be a finite semigroup. An element e of Sis idempotent if
e2 = e. The set of idempotent
elements
of S is denoted by E(S) = e ∈ S | e2 = e .
n
o
For each s ∈ S the set sk | k > 1 of all powers of s is finite and it contains exactly
one idempotent element.
A semigroup S is called X-generated if X is a subset of S and every element of
S can be written as a product of elements of X. The right Cayley graph of an Xgenerated semigroup S has S as vertices and its labeled edges are the triples of the
form (s, a, sa) for s ∈ S and a ∈ X. The left Cayley graph of S is defined analogously
with edges of the form (s, a, as). The definitions of Cayley graphs depend on the
choice of the set X. In the following, when a surjective morphism h : A+ → S is
given, we choose X = h(A) as the set of generators.
Green’s relations are an important tool in the study of finite semigroups. We
denote by S 1 the monoid that is obtained by adding a new neutral element 1 to S.
For s, t ∈ S let
s R t if there exist q, q ′ ∈ S 1 such that sq = t and tq ′ = s,
s L t if there exist p, p′ ∈ S 1 such that ps = t and p′ t = s.
These relations are equivalence relations and the equivalence classes of R (resp. L)
are called R-classes (resp. L-classes). The R-classes (resp. L-classes) of a semigroup
S can be computed in time linear in |S| by applying Tarjan’s algorithm to the right
(resp. left) Cayley graph of S, see [4].
An element (s, e) ∈ S × E(S) is a linked pair if se = s. Two linked pairs (s, e)
and (t, f ) are conjugate, written as (s, e) ∼ (t, f ), if there exist x, y ∈ S such that
sx = t, xy = e and yx = f . The conjugacy relation ∼ on the set of linked pairs is an
equivalence relation, see e.g. [8]. The equivalence classes of ∼ are called conjugacy
classes. A set P of linked pairs is closed under conjugation if it is a union of conjugacy
classes.
Recognition by morphisms. A language L ⊆ Aω is regular (or ω-regular) if it is recognized by some finite Büchi automaton, see e.g. [3]. The family of regular languages
is closed under Boolean operations, i.e., set union, set intersection and complementation. We now describe algebraic recognition modes for regular languages. Let
h : A+ → S be a morphism onto a finite semigroup S. For s ∈ S, we set [s] = h−1 (s)
and for P ⊆ S × S, we set
[P ] =

[

[s][t]ω

(s,t)∈P

if h is understood from the context. A language L ⊆ Aω is weakly recognized by
a morphism h : A+ → S if there exists a set of linked pairs P ⊆ S × E(S) with
L = [P ]. If in addition P is closed under conjugation, then h strongly recognizes L.
Another well-known characterisation of strong recognition is the following.

3

Proposition 1 Let h : A+ → S be a morphism onto a finite semigroup. Then h
strongly recognizes L if and only if [s][t]ω ∩ L 6= ∅ implies [s][t]ω ⊆ L for all s, t ∈ S.
Proof. For the direction from left to right, we have L = [P ] for some set P that is
closed under conjugation. Let α, β ∈ [s][t]ω for some s, t ∈ S and let n > 1 such that
tn ∈ E(S). Note that (stn , tn ) is a linked pair and we also have α, β ∈ [stn ][tn ]ω .
It suffices to show that α ∈ L implies β ∈ L. If α ∈ L, there exist a linked
pair (r, e) ∈ P and a factorization α = uv1 v1′ v2 v2′ · · · with h(u) = stn , h(uv1 ) = r,
h(vi vi′ ) = tn and h(vi′ vi+1 ) = e for all i > 1. Additionally, since S is finite, there exist
indices i, j with 1 6 i < j such that h(vi ) = h(vj ). We set x = h(vi ) = h(vj ) and
′ v ) = rei−1 = r.
′
). Now, stn x = stni x = h(uv1 v1′ · · · vi−1 vi−1
y = h(vi′ vi+1 · · · vj−1 vj−1
i
n
n
By a similar argument, we get xy = t and yx = e. Thus, (st , tn ) is contained in
P and we have β ∈ L.
For the converse implication, we define P as the union of all linked pairs (s, e) with
[s][e]ω ⊆ L. Let (s, e) ∈ P and let (t, f ) be a linked pair such that (s, e) and (t, f )
are conjugate, i.e., sx = t, xy = e and yx = f for some x, y ∈ S. Since h is onto,
there exist words u, v, w ∈ A+ such that h(u) = s, h(v) = x and h(w) = y. Now,
the infinite word u(vw)ω = uv(wv)ω is contained in the intersection [s][e]ω ∩ [t][f ]ω
and by assumption we have [t][f ]ω ⊆ L. This shows that (t, f ) is in P .

The syntactic congruence ≡L of a language L ⊆ Aω is defined over A+ as u ≡L v
if the equivalences
(xuy)z ω ∈ L ⇔ (xvy)z ω ∈ L and
z(xuy)ω ∈ L ⇔ z(xvy)ω ∈ L
hold for all finite words x, y, z ∈ A∗ . Our definition is slightly different but equivalent to the syntactic congruence introduced by Arnold [1]. The congruence classes
of ≡L form the so-called syntactic semigroup A+ /≡L and the syntactic morphism
hL : A+ → A+ /≡L is the natural quotient map. If L is regular, the syntactic semigroup of L is finite and hL strongly recognizes L [1, 8].
Model of computation. Morphisms h : A+ → S are given implicitly through a
mapping f : A → S with f (a) = h(a) for all a ∈ A. We assume that for finite
semigroups S, multiplications can be performed in constant time. Some algorithms
only perform multiplications of the form h(a) · s or s · h(a) where h is a morphism,
s is an element of S and a is a letter. In that case, semigroups can be represented
efficiently by their left and right Cayley graphs. For two elements s, t ∈ S we can
check in constant time whether s = t and it is possible to organize elements of S
in a hash map such that operations on subsets of S can be implemented efficiently.
When a set P ⊆ S × S is part of the input, we assume that for each s, t ∈ S one can
check in constant time whether (s, t) ∈ P .

4

3 Conversion between Büchi automata, weak and strong
recognition
In this section, we describe well-known constructions for the conversion between the
different acceptance modes for regular languages. For details and proofs, we refer
to [8, 9, 14].

3.1 From Büchi automata to strong recognition
In the case of finite words, when proving that each regular language is recognizable by
a morphism onto a finite semigroup, one usually considers the transition semigroup
of a finite automaton. However, when applying the same construction to Büchi
automata, the resulting morphism only weakly recognizes the language. In this
section, we describe a construction to convert a Büchi automaton A = (Q, A, δ, I, F )
into a semigroup S and a morphism h : A+ → S that strongly recognizes L(A).
u
For states p, q ∈ Q and a finite word u ∈ A+ , we write p −
→ q if there exists a
sequence q0 a1 q1 a2 q2 · · · qn−1 an qn with q0 = p, qn = q and (qi , ai+1 , qi+1 ) ∈ δ for all
u
i ∈ {0, . . . , n − 1}. If, additionally, qi ∈ F for some i ∈ {0, . . . , n}, we write p −
→ q.
We now assign to each word u ∈ A+ a Q × Q matrix h(u) defined by

(h(u))pq =



1




u

F

u

if p −
→ q but not p −
→q
u

F

2 if p −
→q




0

F

otherwise

A routine verification shows that this naturally extends the image of A+ under h
to a semigroup S. We say that a linked pair (R, E) where R = (rpq )p,q∈Q and
E = (epq )p,q∈Q is accepting if there exist states p, q ∈ Q such that rpq > 1 and
eqq = 2. One can now verify that the set P of all accepting linked pairs is closed
under conjugation and that [P ] = L(A).

3.2 From weak recognition to Büchi automata
Suppose we are given a morphism h : A+ → S onto a finite semigroup S that weakly
recognizes a language L, i.e., L = [P ] for some set of linked pairs P ⊆ S × E(S).
One can use the following construction from [9] to obtain a Büchi automaton A with
L(A) = L.
The set of states is Q = S 1 × E(S), the set of initial states is I = P and the set
of final states is F = {1} × E(S). The transition relation δ consists of all tuples of
the form ((s, e), a, (t, e)) ∈ Q × A × Q where h(a)t = s or h(a)t = se.
By combining the constructions from this and the previous subsection, we also
obtain a construction to convert a morphism that weakly recognizes a language L

5

into a morphism that strongly recognizes L. There are also direct, more efficient
constructions, to perform this conversion, see e.g. [8]. The converse direction is trivial
since, by definition, a morphism h : A+ → S that strongly recognizes a language L
also weakly recognizes L.

4 Computing conjugacy classes
When designing an algorithm that takes a set of linked pairs P ⊆ S × E(S) as input,
it is often convenient to assume that P is closed under conjugation. However, this
is not always the case in practice: The input set P might be a proper subset of its
closure under conjugation Q such that [P ] = [Q]. In this section, we describe an
algorithm to compute the conjugacy classes efficiently. It justifies the assumption
that P is always closed under conjugation in the following sections, particularly in
Section 6.
As a warm-up, we first describe how to compute the set F of linked pairs. The
linked pairs are exactly the pairs of the form (se, e) with s ∈ S and e ∈ E(S). Thus,
we first check for each element e ∈ S whether e2 = e. If the outcome of the check
is positive, we perform a depth-first search in the left Cayley graph of S, starting
at element e. For each element s that is visited, (s, e) is a linked pair. The total
running time of this routine is O(|S| + |A| · |F |).
An equivalence relation ≡ on the set of linked pairs is called left-stable if for all
p ∈ S and for linked pairs (s, e), (t, f ) with (s, e) ≡ (t, f ), we have (ps, e) ≡ (pt, f ).
We define an equivalence relation ≈ on the set of linked pairs by (s, e) ≈ (t, f ) if
and only if e L s R t L f or (s, e) = (t, f ). Its relationship to conjugacy is captured
in the following Lemma:
Lemma 2 The conjugacy relation ∼ is the finest left-stable equivalence relation
coarser than ≈.
Proof. It follows directly from the definitions of linked pairs and conjugacy that ∼ is
left-stable. Let (s, e) and (t, f ) be linked pairs with (s, e) ≈ (t, f ) and (s, e) 6= (t, f ).
Since s R t, there exist q, q ′ ∈ S 1 such that sq = t and tq ′ = s. We set x = eq and
y = f q ′ . Now, sx = seq = sq = t. Moreover, since s L e, there exists p ∈ S 1 with
ps = e. Thus, we have xy = eqy = psqy = pty = ptf q ′ = ptq ′ = ps = e. A similar
argument can be used to show that yx = f . Hence, (s, e) and (t, f ) are conjugate,
and ∼ is indeed coarser than ≈.
In order to show that ∼ is the finest relation with these properties, we consider an
arbitrary left-stable equivalence relation ≃ on the set of linked pairs which is coarser
than ≈. We show that (s, e) ∼ (t, f ) implies (s, e) ≃ (t, f ). Let x, y ∈ S such that
sx = t, xy = e and yx = f . Then we have ex = xyx = xf and xf y = xyxy = e2 = e,
which shows that e R xf . Furthermore we have xf L f , since yxf = f 2 = f . By
the definition of ≈, this means that (e, e) ≈ (xf, f ) and since ≈ refines ≃, it follows
that (e, e) ≃ (xf, f ). Left-stability yields (s, e) = (se, e) ≃ (sxf, f ) = (t, f ).


6

Since R-classes and L-classes can be computed in time linear in the size of the
semigroup, this allows us to efficiently compute the conjugacy classes as shown
in Algorithm 1. We use a so-called disjoint-set data structure that provides two
operations on a partition. Find(s, e) returns a unique element from the class that
contains (s, e), i.e., if (s, e) and (t, f ) are in the same class, we have Find(s, e) =
Find(t, f ). Union((s, e), (t, f )) merges the classes of (s, e) and (t, f ). To simplify
the notation we also introduce an operation Union+ (R) for subsets R of S × S that
merges all classes with elements in R. Union+ (R) can be implemented using |R| − 1
atomic Union operations. The partition is initialized with singleton sets {(s, e)}
for all linked pairs (s, e). The second data structure used in the algorithm is a set
T ⊆ 2F .
Algorithm 1 Computing conjugacy classes
initialize T with the non-trivial equivalence classes of ≈
for all R ∈ T do Union+ (R) end for
while T 6= ∅ do
remove some set R from T
for all a ∈ A do
R′ ← ∅
for all (s, e) ∈ R do R′ ← R′ ∪ {Find(h(a)s, e)} end for
if |R′ | > 1 then
Union+ (R′ )
T ← T ∪ {R′ }
end if
end for
end while
To prove the correctness and running time of the algorithm, one can combine
Lemma 2 with arguments similar to those given in the correctness and running time
proofs of the Hopcroft-Karp equivalence test [6]. We first show that the relation
induced by the final partition is left-stable:
Lemma 3 Let (s, e) and (t, f ) be linked pairs of the same class upon termination,
then, for each a ∈ A, the pairs (h(a)s, e) and (h(a)t, f ) are in the same class as well.
Proof. We write Findi (s, e) = Findi (t, f ) if (s, e) and (t, f ) belong to the same
class after the i-th iteration of the while-loop. The index ∞ is used to describe the
situation upon termination.
Let i be minimal such that for some pairs (s, e), (t, f ) and a letter a ∈ A, we have
Findi (s, e) = Findi (t, f ) and Find∞ (h(a)s, e) 6= Find∞ (h(a)t, f ). Note that i > 0
because otherwise, a set containing both (s, e) and (t, f ) would be added to T during
initialization. Hence, there exists a pair (s′ , e′ ) with Findi−1 (s′ , e′ ) = Findi−1 (s, e)

7

and a pair (t′ , f ′ ) with Findi−1 (t′ , f ′ ) = Findi−1 (t, f ) such that Union+ (R) is executed for some set R ⊇ {(s′ , e′ ), (t′ , f ′ )}. By choice of i, we have Find∞ (h(a)s, e) =
Find∞ (h(a)s′ , e′ ) and Find∞ (h(a)t, f ) = Find∞ (h(a)t′ , f ′ ). Since we add the set R
to T in iteration i, the equality Find∞ (h(a)s′ , e′ ) = Find∞ (h(a)t′ , f ′ ) holds as well,
and thus Find∞ (h(a)s, e) = Find∞ (h(a)t, f ), a contradiction.

There is of course a dual statement for the pairs (s · h(a), e) and (t · h(a), f ).
Theorem 4 Let F be the set of linked pairs of S. When Algorithm 1 terminates,
the classes of the partition correspond to the conjugacy classes of F . Furthermore,
the algorithm executes at most
◮ |F | − 1 Union operations and
◮ 2 |A| (|F | − 1) Find operations.
Proof. By Lemma 3, the relation induced by the final partition is left-stable and
throughout the main algorithm, two classes are only merged when required to establish this property. Thus, the relation is the finest left-stable equivalence relation
coarser than ≈ and, by Lemma 2, equivalent to the conjugacy relation.
The number of Union operations is bounded by |F |−1 since each operation reduces
the number of classes in the partitions by 1. Let R1 , . . . , Rk be the sets that are
added to T during the execution of the algorithm. Whenever one of the sets Ri is
inserted into T , |Ri | − 1 Union operations are executed. Thus, we have
k
X
i=1

|Ri | − 1 6 |F | − 1.


When Ri is removed from T , exactly |A| · |Ri | Find operations are executed in the
same iteration of the while-loop. The total number of Find operations is therefore
bounded by
k
X
i=1

|A| · |Ri | 6

k
X

|A| · (2 |Ri | − 2) 6 2 |A| · (|F | − 1)

i=1

where the first inequality follows from the fact that each of the sets Ri contains at
least two elements.

A sequence of n Union- and m Find-operations can be performed in O(n + m · α(n))
time where α(n) denotes the extremely slow-growing inverse Ackermann function [13].
Thus, when considering a fixed-size alphabet, the total running time of our algorithm
is “almost linear” in the number of linked pairs.

5 Testing for strong recognition
Common decision problems, such as the universality problem or the inclusion problem, are easy in the case of strong recognition. In the context of weak recognition,

8

the algorithm presented in this section is a powerful tool to answer a broad range of
similar problems. Given a morphism h : A+ → S onto a finite semigroup S and two
sets of linked pairs P, Q ⊆ S × E(S), it can be used to check whether [P ] ⊆ [Q]. In
particular, it allows for testing whether the morphism strongly recognizes a language
L = [P ] by first computing the closure Q of P under conjugation and then using
the algorithm to test whether [Q] ⊆ [P ].
Before we present the algorithm, we remark that inclusion is not only a property
of the semigroup S and the sets P and Q but it also depends on the set of generators
h(A). In order to see this, we consider the finite semigroup S = {(i, j) | 1 6 i, j 6 2}
with the multiplication given by (i, j) · (k, ℓ) = (i, ℓ) for all i, j, k, ℓ ∈ {1, 2}. Let
A = {a, b} and let h : A+ → S be the surjective morphism defined by h(a) = (1, 2)
and h(b) = (2, 1). We consider the two sets of linked pairs P = {((1, 1), (1, 1))} and
Q = {((1, 2), (2, 2))}. It is easy to check that [P ] = [Q] = (a+ b+ )ω . However, if
we add a new letter c to A and extend h by setting h(c) = (1, 1), the infinite word
cω is contained in [P ] but not in [Q], which implies [P ] 6⊆ [Q]. The morphism (or
another description of the set of generators) thus needs to be part of the input of
any algorithm performing the inclusion test described above.
Let us now describe the algorithm. It maintains two sets R, T ⊆ S × S 1 × S 1 .
The former keeps record of the elements that are added to T during the course of
the algorithm. To simplify the presentation, we define x · a−1 to be the set of all
elements p ∈ S 1 which satisfy the equation p · h(a) = x.
Algorithm 2 Testing for strong recognition
initialize R and T with the set {(s, e, 1) | (s, e) ∈ P }
while T 6= ∅ do
remove some element (s, x, y) from T
if x = 1 then return “[P ] 6⊆ [Q]” end if
if (sx, yxyx) 6∈ Q then
for all a ∈ A, p ∈ x · a−1 do
if (s, p, h(a)y) 6∈ R then add (s, p, h(a)y) to R and to T end if
end for
end if
end while
return “[P ] ⊆ [Q]”
The following technical Lemma is crucial for the correctness proof of the algorithm:
Lemma 5 Let u, v ∈ A+ and let (s, e) and (h(u), h(v)) be linked pairs. Then uv ω
is contained in [s][e]ω if and only if there exists a factorization v = v1 v2 such that
v1 6= ε, h(uv1 ) = s and h(v2 vv1 ) = e.

9

Proof. Let v = a1 a2 · · · an with n > 1 and ai ∈ A. If uv ω is contained in [s][e]ω ,
there exists a factorization uv ω = u′ v1′ v2′ · · · such that h(u′ ) = s and h(vi′ ) = e for
all i > 1. Since u and v are finite words, there exist indices j > i > 1, powers
′
= uv k a1 a2 · · · am
k, ℓ > 1 and a position m ∈ {1, . . . , n} such that u′ v1′ v2′ · · · vi−1
′
′
′
ℓ
and vi vi+1 · · · vj = am+1 am+2 · · · an v a1 a2 · · · am . We set v1 = a1 a2 · · · am and v2 =
am+1 am+2 · · · an . Then v1 v2 = v,
′
= h(u′ v1′ v2′ · · · vi−1
) = sei−1 = s and

h(uv1 ) = h(uv k a1 a2 · · · am )

′
h(v2 vv1 ) = h(am+1 am+2 · · · an v ℓ a1 a2 · · · am ) = h(vi′ vi+1
· · · vj′ )

= ej−i+1 = e.

To prove the converse direction, consider the factorization uv ω = uv1 (v2 vv1 )ω .



To simplify the proofs of the following two Lemmas, we extend h to a monoid
morphism h1 : A∗ → S 1 by setting h1 (u) = h(u) for all u ∈ A+ and h1 (ε) = 1.
Lemma 6 If the difference [P ]\[Q] is non-empty, the algorithm returns “[P ] 6⊆ [Q]”.
Proof. By the closure properties of regular languages, we know that there exists a
word α = u(a1 a2 · · · an )ω ∈ [P ] \ [Q]. Let s = h(u) and e = h(a1 a2 · · · an ). Lemma 5
shows that we can assume without loss of generality that (s, e) is contained in P .
We now prove by induction on the parameter k that upon termination, we have
(s, h1 (a1 a2 · · · ak ), h1 (ak+1 ak+2 · · · an )) ∈ R for all k ∈ {0, . . . , n}. In particular, by
considering the case k = 0, we see that the element (s, 1, e) is added to R. Since
every element added to R is also added to Q, the algorithm returns “[P ] 6⊆ [Q]”.
The base case k = n is covered by the initialization of the set R. Let now
k < n, x = h1 (a1 a2 · · · ak+1 ) and y = h1 (ak+2 ak+3 · · · an ). By the induction hypothesis, we know that the tuple (s, x, y) is added to T during the course of the
algorithm. Consider the iteration when this tuple is removed from T . Because
of α 6∈ [Q], we know that (sx, yxyx) 6∈ Q. Thus the inner loop guarantees that
(s, h1 (a1 a2 · · · ak ), h1 (ak+1 ak+2 · · · an )) is added to R.

Lemma 7 If the algorithm returns “[P ] 6⊆ [Q]”, the difference [P ]\[Q] is non-empty.
Proof. We construct a word in the difference [P ] \ [Q]. For every triple (s, e, 1) that
is added to R during the initialization, we define w[s, e, 1] = ε. If a triple (s, p, h(a)y)
is added to R later, we set w[s, p, h(a)y] = a · w[s, p · h(a), y]. For every (s, x, y) 6∈ R,
the word w[s, x, y] is undefined. For the other words, well-definedness follows from
the fact that each triple (s, x, y) is added to R at most once. Furthermore, if w[s, x, y]
is defined, its image under h1 is y and we have (s, xy) ∈ P . Both properties are easy
to prove by induction.
Let (s, 1, y) be the triple that was removed from T immediately before the termination of the algorithm. Consider an arbitrary word u ∈ [s] and set v = w[s, 1, y].

10

We have (s, y) ∈ P and thus uv ω ∈ [P ]. For every factorization v = v1 av2 where
v1 , v2 ∈ A∗ and a ∈ A, the word w[s, h1 (v1 ), h1 (av2 )] is defined as av2 and thus, the
tuple (h(uv1 a), h(v2 vv1 a)) is not contained in Q. In view of Lemma 5, this shows
that uv ω 6∈ [Q].

We are now able to state the main result of this section:
Theorem 8 Given a morphism h : A+ → S onto a finite semigroup S and two
sets of linked pairs P, Q ⊆ S × E(S), one can check in O(|A| · |S|3 ) time whether
[P ] ⊆ [Q].
Proof. The correctness of Algorithm 2 follows from the previous two Lemmas. Since
R contains at most (|S| + 1)3 elements when the algorithm terminates, the outer
loop is executed at most (|S| + 1)3 times. Moreover, for all a ∈ A and s, t ∈ S with
s 6= t, the sets s ·a−1 and t ·a−1 are disjoint. Thus, each element p ∈ S 1 is considered
at most |A| · (|S| + 1)2 times in the inner loop. If R is implemented as a bit field
and T is implemented as a linked list, all operations take constant time. This shows
that the total running time is in O(|A| · |S|3 ).


6 Computation of the syntactic morphism
In this section, we present an algorithm to compute the syntactic semigroup for a
given language. The syntactic homomorphism is obtained as a byproduct. One can
show that the syntactic semigroup is the smallest semigroup strongly recognizing a
language [1, 8], so this operation is similar to the minimization of finite automata.
The most important difference is that our algorithm requires only quadratic time,
whereas minimization is PSPACE-hard in the case of Büchi automata [7, 11].
Let S be a finite semigroup, let h : A+ → S be a surjective morphism and let P be
a set of linked pairs that is closed under conjugation. To make the following notation
more readable, we define Q as the maximal subset of S × S such that [P ] = [Q].
Lemma 9 Let u, v ∈ A+ . Then uv ω ∈ [P ] if and only if (h(u), h(v)) ∈ Q.
Proof. Suppose that uv ω ∈ [P ]. By Proposition 1, we have [h(u)][h(v)]ω ⊆ [P ] =
[Q]. Since Q is maximal, the pair (h(u), h(v)) is contained in Q. The converse
implication is trivial.

∼
∼
We now define a equivalence relation = on S by s = t if for all z ∈ S, we have
(z, s) ∈ Q ⇔ (z, t) ∈ Q and
(s, z) ∈ Q ⇔ (t, z) ∈ Q.
Moreover, let ≡ be the coarsest congruence on S that refines ∼
=, i.e., s ≡ t if xsy ∼
=
1
xty for all x, y ∈ S . We denote by [s]≡ the equivalence class {t ∈ S | t ≡ s} of an
element s ∈ S. The relation ≡ is closely related to the syntactic congruence, as
confirmed by the following result:

11

Proposition 10 The quotient semigroup S/≡ is isomorphic to A+ /≡L .
Proof. We first define a morphism g : A+ → S/≡ by setting g(u) = [h(u)]≡ for
all u ∈ A+ . Let now u, v ∈ A+ . By Lemma 9, we have h(u) ≡ h(v) if and only if
hL (u) = hL (v). Thus, g ◦ h−1

L is a semigroup isomorphism.
The computation of the syntactic semigroup requires two steps:
1. Compute the partition induced by the equivalence relation ∼
=.
2. Refine the partition until the underlying equivalence relation becomes a congruence.
The first step can be performed in time quadratic in the size of the semigroup.
For the second step, we can adapt Hopcroft’s minimization algorithm for finite
automata [5]. For C ⊆ S and a ∈ A, we define
C · a−1 = {s ∈ S | s · h(a) ∈ C}

and

a−1 · C = {s ∈ S | h(a) · s ∈ C} .

The full algorithm is shown in Algorithm 3. It relies on the Split routine that is
usually implemented as part of a partition refinement data structure, see e.g. [5]
for details. Its semantics is shown in Algorithm 4. In addition to modifying the
partition, that routine also updates a set T ⊆ 2S that is used in the main algorithm.
Algorithm 3 Computing the syntactic semigroup
initialize a partition with a single class S
for all s ∈ S do
Split({t ∈ S | (s, t) ∈ Q})
Split({t ∈ S | (t, s) ∈ Q})
end for
initialize T with the non-trivial classes of the partition
while T 6= ∅ do
remove some set C from T
for all a ∈ A do
Split(C · a−1 )
⊲ Refine the partition and update T
−1
Split(a · C)
⊲ Refine the partition and update T
end for
end while
The next Lemma shows that upon termination, the equivalence relation induced
by the partition is indeed a congruence:
Lemma 11 If, upon termination, the elements s and t belong to the same class of
the partition, then, for each a ∈ A, the elements h(a)s and h(a)t are in the same
class as well.

12

Algorithm 4 The Split operation to refine a partition P
procedure Split(X)
for all C ∈ P do
C1 ← C ∩ X, C2 ← C \ X
if C1 6= ∅ and C2 6= ∅ then
P ← (P \ {C}) ∪ {C1 , C2 }
if C ∈ T then
T ← (T \ {C}) ∪ {C1 , C2 }
else
if |C1 | 6 |C2 | then T ← T ∪ {C1 } else T ← T ∪ {C2 } end if
end if
end if
end for
end procedure
Proof. Suppose that h(a) · s and h(a) · t belong to different classes. These elements
are split either during the initialization or in the main loop. In either case, a set C
that contains either h(a) · s or h(a) · t is added to T . When this set is removed from
T , the operation Split(a−1 · C) asserts that s and t lie in different classes as well. 
There is of course a dual statement for the elements s · h(a) and t · h(a).
Theorem 12 The syntactic morphism can be computed in O(|S|2 + |A| · |S| log |S|)
time.
Proof. Let us first argue that Algorithm 3 is correct. The partition is initialized
with the equivalence classes of ∼
=. A class is only split when it is necessary to restore
the left-stability or right-stability. Upon termination, the relation induced by the
partition is a congruence, as stated in Lemma 11. Thus, it is the coarsest congruence
that refines ∼
= and hence equivalent to ≡.
For the analysis of the running time, we assume that the operation Split(X) can
be implemented in time linear in |X|. Then the initialization clearly takes O(|S|2 )
time. We denote by C1 , . . . , Ck the sets that are added to T during the course of
the algorithm. Let s ∈ S and let ns = {i | 1 6 i 6 k, s ∈ Ci } be the number of sets
Ci containing s. At any point in time, there is at most one set in T that contains s.
If such a set C is removed from T and another set C ′ with s ∈ C ′ is added to T at
a later point in time, we have that |C ′ | 6 |C| /2. Thus, the inequality ns 6 log |S|
holds for all s ∈ S and we have
k X
X

i=1 a∈A

Ci · a−1 + a−1 · Ci



=

X

s∈S,a∈A

ns·h(a) + nh(a)·s 6 2 |A| · |S| log |S|.


Consequently, the total running time of the while-loop is in O(|A| · |S| log |S|), assuming that T is implemented efficiently, e.g. as a linked list.


13

If the alphabet A is fixed and the semigroup S becomes large, the running time
is dominated by the initialization. However, one can show that the algorithm we
presented is quite optimal. Before we start with the proof of the optimality result,
we need the following technical Lemma that asserts the existence of a semigroup
with certain properties:
Lemma 13 For every n > 4 there exist a semigroup T with n2 · 2n + n elements
and a set D ⊆ E(T ) such that the following properties hold:
1. T has rank 2, i.e., T is X-generated for some X ⊆ T with |X| = 2.
2. |D| = 2n−1 .
3. For all e, f ∈ D and x, y ∈ T , we have e = f or xy 6= e or yx 6= f .
Proof. Let n > 4 and let N = {0, . . . , n − 1}. Let T be the set N × 2N × N ∪ N .
We denote by + be the addition modulo n which can be extended to T as follows:
(i, X, j) + (k, Y, ℓ) = (i, X ∪ {j + k} ∪ Y, ℓ)
(i, X, j) + k = (i, X, j + k)
i + (j, X, k) = (i + j, X, k)
for all i, j, k, ℓ ∈ N and X, Y ⊆ N . It is easy to check that this operation is
associative and thus, (T, +) forms a semigroup. The number of elements of T is
n2 · 2n + n. One can also easily verify that T is {1, (0, ∅, 0)}-generated.
Now, consider the set D of all elements of the form (0, X, 0) for 0 ∈ X ⊆ N .
We have (0, X, 0) · (0, X, 0) = (0, X ∪ {0} ∪ X, 0) = (0, X, 0) and thus, D ⊆ E(T ).
The number of elements in D is 2n−1 . To show property 3, we assume that there
exist E, F ⊆ N and (i, X, j), (k, Y, ℓ) ∈ T such that (i, X, j) · (k, Y, ℓ) = (0, E, 0) and
(k, Y, ℓ) · (i, X, j) = (0, F, 0). By the definition of the operation + on T , this implies
i = j = k = ℓ = 0. Moreover, we have E = X ∪ {0} ∪ Y = Y ∪ {0} ∪ X = F . The
other cases (x ∈ N or y ∈ N ) are similar.

We now use the previous Lemma to construct another semigroup with four generators and a large number of conjugacy classes.
n

o

Lemma 14 Let A = a, b, a, b , let c ∈ N and let λ ∈ R be a strictly positive
number. Then there exist a semigroup S and a surjective morphism g : A+ → S,
such that S has more than c · |S|2−λ conjugacy classes.
n

o

Proof. We first define B = {a, b}, B = a, b and choose n > 4 such that 32cn2 <
2λn . Let T be a finite semigroup and let D be a subset of E(T ) with the properties
described in Lemma 13. Let h : B + → T be a surjective homomorphism. We denote
by T a disjoint copy of T and by h the morphism h : B → T induced by h. Now we

1
define S = (T × 1) ∪ (1 × T 1 ) \ (1, 1) with the multiplication
(s, s) · (t, t) =

(

(1, s · t) if s = t = 1
(s · t, 1) otherwise

14

1

where 1 denotes the identity in T 1 \ T and 1 denotes the identity in T \ T . By
construction, the semigroup S has 2n2 2n + 2n + 1 < 4n2 2n elements. The morphism
g : A+ → S defined by g(c) = (h(c), 1) for c ∈ B and g(c) = (1, h(c)) for c ∈ B is
surjective.
Consider the set F = (T × 1) × (1 × D). We will show that F contains more than
c · |S|2−λ elements, that each element of F is a linked pair of S and that no two
different elements of F are conjugate, thereby proving the claim.
We start with the cardinality of F . We have |F | > n2 22n−1 = n2 22n−λn+λn−1 >
16cn4 (2n )2−λ > c(4n2 2n )2−λ > c |S|2−λ , where the second inequality follows by the
choice of n. Showing that F only consists of linked pairs is easy and is left as an
exercise to the reader. Now consider two pairs ((s, 1), (1, e)) and ((t, 1), (1, f )) from
F . Suppose these pairs are conjugate, i.e., there exist (x, x), (y, y) ∈ S such that
(s, 1) · (x, x) = (t, 1), (x, x) · (y, y) = (1, e) and (y, y) · (x, x) = (1, f ). From the second
equation, we see that x = y = 1. Therefore, s = t. Additionally, we have xy = e, as
well as yx = f . Property 3 in Lemma 13 yields e = f .

The optimality result now follows by using the previous construction as an input
to the minimization algorithm.
Proposition 15 The syntactic morphism cannot be computed in time O(|S|2−λ ) for
any strictly positive, fixed value λ ∈ R.
Proof. Assume there exists an algorithm and a constant c > 1 such that every input
of size n = |S| can be minimized in time T (n) 6 c · n2−λ . Consider the execution of
the algorithm on the semigroup S described in Lemma 14 and on P = F . We denote
by (s1 , e1 ), (s2 , e2 ), . . . , (sℓ , eℓ ) the sequence of linked pairs for which the algorithm
checks whether (si , ei ) ∈ P . We have ℓ 6 T (n) 6 c · |S|2−λ and thus, there is a
conjugacy class C such that (si , ei ) 6∈ C for all i ∈ {1, . . . , ℓ}. Since the algorithm
is deterministic, the execution sequence on input Q = P \ C is the same, and the
algorithm returns, again, the trivial semigroup consisting of one element. However,
[Q] 6= Aω and thus, the algorithm is incorrect.


7 Language operations on morphisms
One of the merits of strong recognition is that complementation is easy. If a morphism h : A+ → S onto a finite semigroup S strongly recognizes a language L ⊆ Aω ,
it also strongly recognizes the complement Aω \ L. As in the case of finite words, we
can use direct products for unions and intersections.
Another operation on languages which is of particular interest when it comes
to converting MSO formulas to strongly recognizing morphisms are so-called lengthpreserving morphisms. Suppose we are given alphabets A, B and a length-preserving
morphism π : A+ → B + , i.e., π(a) ∈ B for all a ∈ A. We naturally extend this

15

morphism to infinite words by setting π(a1 a2 · · · ) = π(a1 )π(a2 ) · · · and to languages
L ⊆ Aω by setting π(L) = {π(α) | α ∈ L}.
Proposition 16 Let π : A+ → B + be a length-preserving morphism, let S be a finite
semigroup and let h : A+ → S be a surjective morphism that strongly recognizes a
language L ⊆ Aω . Then there exist a semigroup T of size 2|S| and a morphism
g : B + → T that strongly recognizes π(L).
Proof. We first define T to be the set 2S of all subsets of S and extend it to a
semigroup by defining an associative multiplication X · Y = {xy | x ∈ X, y ∈ Y }.
The morphism g : B + → T is uniquely defined by g(a) = h(π −1 (a)) for all a ∈ B.
Let us now verify that g strongly recognizes π(L). Consider a linked pair (s, e)
and two infinite words α, β ∈ g−1 (s)(g−1 (e))ω . By Proposition 1, it suffices to show
that α ∈ π(L) implies β ∈ π(L). If α is contained in π(L), we can conclude by
Ramsey’s theorem that there exists a linked pair (t, f ) of S with t ∈ s, f ∈ e
and h−1 (t)(h−1 (f ))ω ∩ L 6= ∅. By assumption, h strongly recognizes L and thus,
we have h−1 (t)(h−1 (f ))ω ⊆ L. Since we know that there exists an infinite word
uv1 v2 · · · ∈ π −1 (β) such that h(u) = t and h(vi ) = f for all i > 1, this immediately
yields uv1 v2 · · · ∈ L and hence β ∈ π(L).


8 Experimental results
In order to test the algorithms and constructions in practice, we implemented the
conversion of MSO formulas into strongly recognizing morphisms. The constructions
described in Section 7 are used to recursively convert the formulas, and all intermediate results are minimized using the algorithm from Section 6. For details on MSO
logic over infinite words and its connexion to regular languages, we refer to [14, 15].
The conversion to strongly recognizing morphisms instead of Büchi automata has
the advantage that all intermediate objects can be minimized efficiently. Table 1
shows the size of the computed syntactic semigroup S, the number of linked pairs
F and the size of the accepting set P (which is closed unter conjugation) for the following three families of MSO formulas with parameter k > 1 and free second-order
variables Xk+1 = X1 , X2 , . . . , Xk :
ϕk = ∀x

k
^

∃y (x < y ∧ y ∈ Xi )

i=1

ψk = ∀x∀y (y = x + 1) →

k
^

(x ∈ Xi → y ∈ Xi+1 )

i=1

χk = ∀x

k
^

(x ∈ Xi → ∃y (x < y ∧ (y ∈ Xi−1 ∨ y ∈ Xi+1 )))

i=1

16

ϕk
k
k
k
k
k

=2
=3
=4
=5
=6

ψk

χk

|S|

|F |

|P |

|S|

|F |

|P |

|S|

|F |

|P |

4
8
16
32
64

5
22
74
232
710

1
1
1
1
1

12
43
148
539
1863

15
50
163
570
1926

10
41
146
537
1861

7
11
17
41
105

14
26
61
227
716

11
15
30
85
184

Table 1: Experimental results for different parameter values
All computations were made on a Intel Core i5-3320M with 4GiB of RAM. The
execution time was less than three seconds for each formula.

9 Summary and Outlook
We described several algorithms for weakly recognizing morphisms and strongly recognizing morphisms over infinite words. Our tests indicate that strongly recognizing
morphisms, when combined with the minimization algorithm presented in Section 6,
are a practical alternative to automata-based models when it comes to deciding
properties of MSO formulas.
Some of the algorithms leave room for optimization. In particular, it would be
interesting to see whether there is a linear-time algorithm to compute conjugacy
classes and whether the running time of the algorithm described in Section 5 can be
improved to O(|A| · S 2 ).

References
[1] A. Arnold. A syntactic congruence for rational ω-languages. Theoretical Comput. Sci., 39:333–335, 1985.
[2] H. Calbrix, M. Nivat, and A. Podelski. Ultimately periodic words of rational
ω-languages. In MFCS 94, Proceedings, volume 802 of LNCS, pages 554–566.
Springer, 1994.
[3] V. Diekert and P. Gastin. First-order definable languages. In J. Flum, E. Grädel,
and T. Wilke, editors, Logic and Automata: History and Perspectives, Texts in
Logic and Games, pages 261–306. Amsterdam University Press, 2008.
[4] V. Froidure and J.-E. Pin. Algorithms for computing finite semigroups. In
F. Cucker and M. Shub, editors, Foundations of Computational Mathematics,
pages 112–126. Springer, 1997.

17

[5] J. Hopcroft. An n log n algorithm for minimizing states in a finite automaton.
In Z. Kohavi and A. Paz, editors, Theory of Machines and Computations, pages
189–196. Academic Press, New York, 1971.
[6] J. Hopcroft and R. Karp. A linear algorithm for testing equivalence of finite automata. Technical report, Dept. of Computer Science, Cornell Univ., December
1971.
[7] A. R. Meyer and L. J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In 13th Annual Symposium
on Switching and Automata Theory, pages 125–129. IEEE Computer Society,
1972.
[8] D. Perrin and J.-É. Pin. Infinite words, volume 141 of Pure and Applied Mathematics. Elsevier, 2004.
[9] J.-P. Pécuchet. Varietés de semisgroupes et mots infinis. In STACS 86, volume
210 of LNCS, pages 180–191. Springer, 1986.
[10] M. O. Rabin and D. Scott. Finite automata and their decision problems.
IBM Journal of Research and Development, 3:114–125, 1959. Reprinted in
E. F. Moore, editor, Sequential Machines: Selected Papers, Addison-Wesley,
1964.
[11] A. P. Sistla, M. Y. Vardi, and P. L. Wolper. The complementation problem for
Büchi automata with applications to temporal logic. Theoretical Comput. Sci.,
49(2-3):217–237, 1987.
[12] L. J. Stockmeyer. The complexity of decision problems in automata theory and
logic. PhD thesis, TR 133, M.I.T., Cambridge, 1974.
[13] R. E. Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM,
22(2):215–225, Apr. 1975.
[14] W. Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook
of Theoretical Computer Science, chapter 4, pages 133–191. Elsevier, 1990.
[15] W. Thomas. Languages, automata and logic. In A. Salomaa and G. Rozenberg,
editors, Handbook of Formal Languages, volume 3, Beyond Words, pages 389–
455. Springer, Berlin, 1997.

18

