Monoid generalizations of the Richard Thompson groups
Monoid generalizations of the Richard Thompson groups
J.C. Birget ∗
24 Jan. 2016
Abstract
The groups Gk,1 of Richard Thompson and Graham Higman can be generalized in a natural
way to monoids, that we call Mk,1, and to inverse monoids, called Invk,1; this is done by simply
generalizing bijections to partial functions or partial injective functions. The monoids Mk,1 have
connections with circuit complexity (studied in another paper). Here we prove thatMk,1 and Invk,1
are congruence-simple for all k. Their Green relations J and D are characterized: Mk,1 and Invk,1
are J -0-simple, and they have k− 1 non-zero D-classes. They are submonoids of the multiplicative
part of the Cuntz algebra Ok. They are finitely generated, and their word problem over any finite
generating set is in P. Their word problem is coNP-complete over certain infinite generating sets.1
1 Thompson-Higman monoids
Since their introduction by Richard J. Thompson in the mid 1960s [29, 26, 30], the Thompson groups
have had a great impact on infinite group theory. Graham Higman generalized the Thompson groups
to an infinite family [20]. These groups and some of their subgroups have appeared in many contexts
and have been widely studied; see for example [12, 8, 15, 10, 17, 18, 9, 11, 23].
The definition of the Thompson-Higman groups lends itself easily to generalizations to inverse
monoids and to more general monoids. These monoids are also generalizations of the finite symmetric
monoids (of all functions on a set), and this leads to connections with circuit complexity; more details
on this appear in [2, 3, 5].
By definition the Thompson-Higman group Gk,1 consists of all maximally extended isomorphisms
between finitely generated essential right ideals of A∗, where A is an alphabet of cardinality k. The
multiplication is defined to be composition followed by maximal extension: for any ϕ,ψ ∈ Gk,1, we
have ϕ · ψ = max(ϕ ◦ ψ). Every element ϕ ∈ Gk,1 can also be given by a bijection ϕ : P → Q where
P,Q ⊂ A∗ are two finite maximal prefix codes over A; this bijection can be described concretely by a
finite function table. For a detailed definition according to this approach, see [4] (which is also similar
to [28], but with a different terminology); moreover, Subsection 1.1 gives all the needed definitions.
It is natural to generalize the maximally extended isomorphisms between finitely generated essential
right ideals of A∗ to homomorphisms, and to drop the requirement that the right ideals be essential.
It will turn out that this generalization leads to interesting monoids, or inverse monoids, which we call
Thompson-Higman monoids. Our generalization of the Thompson-Higman groups to monoids will also
generalize the embedding of these groups into the Cuntz algebras [4, 27], which provides an additional
∗ Earlier versions of this paper appeared in http://arxiv.org/abs/0704.0189 (v1 in April 2007, and v2 in April 2008),
and also appeared in reference [1]. Supported by NSF grant CCR-0310793.
Changes in this version: Section 4 has been thoroughly revised, and errors have been corrected; however, the
main results of Section 4 do not change. The main changes are in Theorem 4.5, Definition 4.5A (the concept of a normal
right-ideal morphism), and the final proof of Theorem 4.13. Sections 1, 2, and 3 are unchanged, except for the proof of
Theorem 2.3, which was incomplete; a complete proof was published in the Appendix of reference [6], and is also given
here.
http://arxiv.org/abs/0704.0189v3
http://arxiv.org/abs/0704.0189
motivation for our definition. Moreover, since these homomorphisms are close to being arbitrary
finite string transformations, there is a connection between these monoids and combinational boolean
circuits; the study of the connection between Thompson-Higman groups and circuits was started in
[5, 3] and will be developed more generally for monoids in [2]; the present paper lays some of the
foundations for [2].
1.1 Definition of the Thompson-Higman groups and monoids
Before defining the Thompson-Higman monoids we need some basic definitions, that are similar to
the introductory material that is needed for defining the Thompson-Higman groups Gk,1; we follow
[4] (which is similar to [28]). We use an alphabet A of cardinality |A| = k, and we list its elements as
A = {a1, . . . , ak}. Let A∗ denote the set of all finite words over A (i.e., all finite sequences of elements
of A); this includes the empty word ε. The length of w ∈ A∗ is denoted by |w|; let An denote the set
of words of length n. For two words u, v ∈ A∗ we denote their concatenation by uv or by u · v; for sets
B,C ⊆ A∗ the concatenation is BC = {uv : u ∈ B, v ∈ C}. A right ideal of A∗ is a subset R ⊆ A∗
such that RA∗ ⊆ R. A generating set of a right ideal R is a set C such that R is the intersection of
all right ideals that contain C; equivalently, R = CA∗. A right ideal R is called essential iff R has a
non-empty intersections with every right ideal of A∗. For words u, v ∈ A∗, we say that u is a prefix of
v iff there exists z ∈ A∗ such that uz = v. A prefix code is a subset C ⊆ A∗ such that no element of
C is a prefix of another element of C. A prefix code is maximal iff it is not a strict subset of another
prefix code. One can prove that a right ideal R has a unique minimal (under inclusion) generating set,
and that this minimal generating set is a prefix code; this prefix code is maximal iff R is an essential
right ideal.
For right ideals R′ ⊆ R ⊆ A∗ we say that R′ is essential in R iff R′ intersects all right subideals of
R in a non-empty way.
Tree interpretation: The free monoid A∗ can be pictured by its right Cayley graph, which is the
rooted infinite regular k-ary tree with vertex set A∗ and edge set {(v, va) : v ∈ A∗, a ∈ A}. We simply
call this the tree of A∗. It is a directed tree, with all paths moving away from the root ε (the empty
word); by “path” we will always mean a directed path. A word v is a prefix of a word w iff v is is an
ancestor of w in the tree. A set P is a prefix code iff no two elements of P are on the same path. A set
R is a right ideal iff any path that starts in R has all its vertices in R. The prefix code that generates
R consists of the elements of R that are maximal (within R) in the prefix order, i.e., closest to the root
ε. A finitely generated right ideal R is essential iff every infinite path of the tree eventually reaches
R (and then stays in it from there on). Similarly, a finite prefix code P is maximal iff any infinite
path starting at the root eventually intersects P . For two finitely generated right ideals R′ ⊂ R, R′ is
essential in R iff any infinite path starting in R eventually reaches R′ (and then stays in R′ from there
on). In other words for finitely generated right ideals R′ ⊆ R, R′ is essential in R iff R′ and R have
the same “ends”. For the prefix tree of A∗ we can consider also the “boundary” Aω (i.e., all infinite
words), a.k.a. the ends of the tree. In Thompson’s original definition [29, 30], G2,1 was given by a
total action on {0, 1}ω . In [4] this total action was extended to a partial action on A∗∪Aω; the partial
action on A∗ ∪Aω is uniquely determined by the total action on Aω; it is also uniquely determined by
the partial action on A∗. Here, as in [4], we only use the partial action on A∗.
Definition 1.1 A right ideal homomorphism of A∗ is a total function ϕ : R1 → A∗ such that R1 is
a right ideal of A∗, and for all x1 ∈ R1 and all w ∈ A∗: ϕ(x1w) = ϕ(x1) w.
For any partial function f : A∗ → A∗, let Dom(f) denote the domain and let Im(f) denote the image
(range) of f . For a right ideal homomorphism ϕ : R1 → A∗ it is easy to see that the image Im(ϕ)
is also right ideal of A∗, which is finitely generated (as a right ideal) if the domain R1 = Dom(ϕ) is
finitely generated.
A right ideal homomorphism ϕ : R1 → R2, where R1 = Dom(ϕ) and R2 = Im(ϕ), can be described
by a total surjective function P1 → S2, with P1, S2 ⊂ A∗; here P1 is the prefix code (not necessarily
maximal) that generates R1 as a right ideal, and S2 is a set (not necessarily a prefix code) that
generates R2 as a right ideal; so R1 = P1A
∗ and R2 = S2A
∗. The function P1 → S2 corresponding to
ϕ : R1 → R2 is called the table of ϕ. The prefix code P1 is called the domain code of ϕ and we write
P1 = domC(ϕ). When S2 is a prefix code we call S2 the image code of ϕ and we write S2 = imC(ϕ).
We denote the table size of ϕ (i.e., the cardinality of domC(ϕ)) by ‖ϕ‖.
Definition 1.2 An injective right ideal homomorphism is called a right ideal isomorphism. A right
ideal homomorphism ϕ : R1 → R2 is called total iff the domain right ideal R1 is essential. And ϕ is
called surjective iff the image right ideal R2 is essential.
The table P1 → P2 of a right ideal isomorphism ϕ is a bijection between prefix codes (that are not
necessarily maximal). The table P1 → S2 of a total right ideal homomorphism is a function from
a maximal prefix code to a set, and the table P1 → S2 of a surjective right ideal homomorphism is
a function from a prefix code to a set that generates an essential right ideal. The word “total” is
justified by the fact that if a homomorphism ϕ is total (and if domC(ϕ) is finite) then ϕ(w) is defined
for every word that is long enough (e.g., when |w| is longer than the longest word in the domain code
P1); equivalently, ϕ is defined from some point onward on every infinite path in the tree of A
∗ starting
at the root.
Definition 1.3 An essential restriction of a right ideal homomorphism ϕ : R1 → A∗ is a right ideal
homomorphism Φ : R′1 → A∗ such that R′1 is essential in R1, and such that for all x′1 ∈ R′1: ϕ(x′1) =
Φ(x′1).
We say that ϕ is an essential extension of Φ iff Φ is an essential restriction of ϕ.
Note that if Φ is an essential restriction of ϕ then R′2 = Im(Φ) will automatically be essential in
R2 = Im(ϕ). Indeed, if I is any non-empty right subideal of R1 then I∩R′1 6= ∅, hence ∅ 6= Φ(I∩R′1)
⊆ Φ(I) ∩ Φ(R′1) = Φ(I) ∩ R′2; moreover, any right subideal J of R2 is of the form J = Φ(I) where
I = Φ−1(J) is a right subideal of R1; hence, for any right subideal J of R2, ∅ 6= J ∩R′2.
Proposition 1.4 (1) Let ϕ,Φ be homomorphisms between finitely generated right ideals of A∗, where
A = {a1, . . . , ak}. Then Φ is an essential restriction of ϕ iff Φ can be obtained from ϕ by starting
from the table of ϕ and applying a finite number of restriction steps of the following form: Replace
(x, y) in a table by {(xa1, ya1), . . . , (xak, yak)}.
(2) Every homomorphism between finitely generated right ideals of A∗ has a unique maximal essential
extension.
Proof. (1) Consider a homomorphism between finitely generated right ideals ϕ : R1 → R2, let P1 be
the finite prefix code that generates the right ideal R1, and let S2 = ϕ(P1), so S2 generates the right
ideal R2.
If x ∈ P1 and y = ϕ(x) ∈ S2 then (since ϕ is a right ideal homomorphism), yai = ϕ(xai) for
i = 1, . . . , k. Then R1 − {x} is a right ideal which is essential in R1, and R1 − {x} is generated
by (P1 − {x}) ∪ {xa1, . . . , xak}. Indeed, in the tree of A∗ every downward directed path starting
at vertex x goes through one of the vertices xai. Thus, removing (x, y) from the graph of ϕ is an
essential restriction; for the table of ϕ, the effect is to replace the entry (x, y) by the set of entries
{(xa1, ya1), . . . , (xak, yak)}. If finitely many restriction steps of the above type are carried out, the
result is again an essential restriction of ϕ.
Conversely, let us show that if Φ is an essential restriction of ϕ then Φ can be obtained by a finite
number of replacement steps of the form “replace (x, y) by {(xa1, ya1), . . . , (xak, yak)} in the table”.
Using the tree of A∗ we have: If R and R′ are right ideals of A∗ generated by the finite prefix codes
P , respectively P ′, and if R′ is essential in R then every infinite path from P intersects P ′. It follows
from this characterization of essentiality and from the finiteness of P1 and P
1 that R1 − R′1 is finite.
Hence ϕ and Φ differ only in finitely many places, i.e., one can transform ϕ into Φ in a finite number
of restriction steps.
So, the restriction Φ of ϕ is obtained by removing a finite number of pairs (x, y) from ϕ; however,
not every such removal leads to a right ideal homomorphism or an essential restriction of ϕ. If (x0, y0)
is removed from ϕ then x0 is removed from R1 (since ϕ is a function). Also, since R
1 is a right ideal,
when x0 is removed then all prefixes of x0 (equivalently, all ancestor vertices of x0 in the tree of A
have to be removed. So we have the following removal rule (still assuming that domain and image
right ideals are finitely generated):
If Φ is an essential restriction of ϕ then ϕ can be transformed into Φ by removing a finite set of
strings from R1, with the following restriction: If a string x0 is removed then all prefixes of x0 are
also removed from R1; moreover, x0 is removed from R1 iff (x0, ϕ(x0)) is removed from ϕ.
As a converse of this rule, we claim that if the transformation from ϕ to Φ is done according to
this rule, then Φ is an essential restriction of ϕ. Indeed, Φ will be a right ideal homomorphism: if
Φ(x1) is defined then Φ(x1z) will also be defined (if it were not, the prefix x1 of x1z would have been
removed), and Φ(x1z) = ϕ(x1z) = ϕ(x1) z = Φ(x1) z. Moreover, Dom(Φ) = R
1 will be essential in
R1: every directed path starting at R1 eventually meets R
1 because only finitely many words were
removed from R1 to form R
1. Hence by the tree characterization of essentiality, R
1 is essential in R1.
In summary, if Φ is an essential restriction of ϕ then Φ is obtained from ϕ by a finite sequence of
steps, each of which removes one pair (x, ϕ(x)). In Dom(ϕ) the string x is removed. The domain code
becomes (P1 −{x}) ∪ {xa1, . . . , xak}, since {xa1, . . . , xak} is the set of children of x in the tree of A∗.
This means that in the table of ϕ, the pair (x, ϕ(x)) is replaced by {(xa1, ϕ(x) a1), . . . , (xak, ϕ(x) ak)}.
(2) Uniqueness of the maximal essential extension: By (1) above, essential extensions are obtained
by the set of rewrite rules of the form {(xa1, ya1), . . . , (xak, yak)} → (x, y), applied to tables. This
rewriting system is locally confluent (because different rules have non-overlapping left sides) and ter-
minating (because they decrease the length); hence maximal essential extensions exist and are unique.
Proposition 1.4 yields another tree interpretation of essential restriction: Assume first that a total order
a1 < a2 < . . . < ak has been chosen for the alphabet A; this means that the tree of A
∗ is now an oriented
rooted tree, i.e., the children of each vertex v have a total order (namely, va1 < va2 < . . . < vak). The
rule “replace (x, y) in the table by {(xa1, ya1), . . . , (xak, yak)}” has the following tree interpretation:
Replace x and y = ϕ(x) by the children of x, respectively of y, matched according to the order of the
children.
Important remark:
As we saw, every right ideal homomorphism can be described by a table P → S where P is a prefix
code and S is a set. But we also have: Every right ideal homomorphism ϕ has an essential restriction
ϕ′ whose table P ′ → Q′ is such that both P ′ and Q′ are prefix codes; moreover, Q′ can be chosen to
be a subset of An for some n ≤ max{|s| : s ∈ S}. Example (with alphabet A = {a, b}):
has an essential restriction
aa ab b
aa ab aa
. Theorem 4.5B gives a tighter result with poly-
nomial bounds.
Definition 1.5 The Thompson-Higman partial function monoid Mk,1 consists of all maximal essen-
tial extensions of homomorphisms between finitely generated right ideals of A∗. The multiplication is
composition followed by maximal essential extension.
In order to prove associativity of the multiplication of Mk,1 we define the following and we prove a few
Lemmas.
Definition 1.6 By RIk we denote the monoid of all right ideal homomorphisms between finitely
generated right ideals of A∗, with function composition as multiplication. We consider the equivalence
relation ≡ defined for ϕ1, ϕ2 ∈ RI k by: ϕ1 ≡ ϕ2 iff max(ϕ1) = max(ϕ2).
It is easy to prove that RI k is closed under composition. Moreover, by existence and uniqueness of
the maximal essential extension (Prop. 1.4(2)) each ≡-equivalence class contains exactly one element
of Mk,1. We want to prove:
Proposition 1.7 The equivalence relation ≡ is a monoid congruence on RI k, and Mk,1 is isomorphic
(as a monoid) to RI k/≡. Hence, Mk,1 is associative.
First some Lemmas.
Lemma 1.8 If R′i ⊆ Ri (i = 1, 2) are finitely generated right ideals with R′i essential in Ri, then
R′1 ∩R′2 is essential in R1 ∩R2.
Proof. We use the tree characterization of essentiality. Any infinite path p in R1 ∩ R2 is also in Ri
(i = 1, 2), hence p eventually enters into R′i. Thus p eventually meets R
1 and R
2, i.e., p meets R
1∩R′2.
Lemma 1.9 All ϕ1, ϕ2 ∈ RI k have restrictions Φ1,Φ2 ∈ RI k (not necessarily essential restrictions)
such that:
• Φ2 ◦ Φ1 = ϕ2 ◦ ϕ1, and
• Dom(Φ2) = Im(Φ1) = Dom(ϕ2) ∩ Im(ϕ1).
Proof. Let R = Dom(ϕ2) ∩ Im(ϕ1). This is a right ideal which is finitely generated since Dom(ϕ2)
and Im(ϕ1) are finitely generated (see Lemma 3.3 of [4]). Now we restrict ϕ1 to Φ1 in such a way that
Im(Φ1) = R and Dom(Φ1) = ϕ
1 (R), and we restrict ϕ2 to Φ2 in such a way that Dom(Φ2) = R and
Im(Φ2) = ϕ2(R). Then Φ2 ◦Φ1(.) and ϕ2 ◦ϕ1(.) agree on ϕ−11 (R); moreover, Dom(Φ2 ◦Φ1) = ϕ
1 (R).
Since ϕ2 ◦ ϕ1(x) is only defined when ϕ1(x) ∈ R, we have Φ2 ◦ Φ1 = ϕ2 ◦ ϕ1. Also, by the definition
of R we have Dom(Φ2) = Im(Φ1). ✷
Lemma 1.10 For all ϕ1, ϕ2 ∈ RI k we have:
max(ϕ2 ◦ ϕ1) = max(max(ϕ2) ◦ ϕ1) = max(ϕ2 ◦max(ϕ1)).
Proof. We only prove the first equality; the proof of the second one is similar. By Lemma 1.9 we
can restrict ϕ1 and ϕ2 to ϕ
1, respectively ϕ
2, so that ϕ
2 ◦ ϕ′1 = ϕ2 ◦ ϕ1, and Dom(ϕ′2) = Im(ϕ′1) =
Dom(ϕ2) ∩ Im(ϕ1); let R′ = Dom(ϕ2) ∩ Im(ϕ1).
Similarly we can restrict ϕ1 and max(ϕ2) to ϕ
1 , respectively ϕ
2 , so that ϕ
2 ◦ ϕ′′1 = max(ϕ2) ◦ ϕ1,
and Dom(ϕ′′2) = Im(ϕ
1) = Dom(max(ϕ2)) ∩ Im(ϕ1); let R′′ = Dom(max(ϕ2)) ∩ Im(ϕ1).
Obviously, R′ ⊆ R′′ (since ϕ2 is a restriction of max(ϕ2)). Moreover, R′ is essential in R′′, by
Lemma 1.8; indeed, Dom(ϕ2) is essential in Dom(max(ϕ2)) since max(ϕ2) is an essential extension of
ϕ2. Since R
′ is essential in R′′, ϕ2 ◦ϕ1 is an essential restriction of max(ϕ2)◦ϕ1. Hence by uniqueness
of the maximal essential extension, max(max(ϕ2) ◦ ϕ1) = max(ϕ2 ◦max(ϕ1)). ✷
Proof of Prop. 1.7: If ϕ2 ≡ ψ2 then, by definition, max(ϕ2) = max(ψ2), hence by Lemma 1.10:
max(ϕ2 ◦ ϕ) = max(max(ϕ2) ◦ ϕ) = max(max(ψ2) ◦ ϕ) = max(ψ2 ◦ ϕ),
for all ϕ ∈ RI k. Thus (by the definition of ≡), ϕ2 ◦ ϕ ≡ ψ2 ◦ ϕ, so ≡ is a right congruence. Similarly
one proves that ≡ is a left congruence. Thus, RI k/≡ is a monoid.
Since every ≡-equivalence class contains exactly one element of Mk,1 there is a one-to-one cor-
respondence between RI k/≡ and Mk,1. Moreover, the map ϕ ∈ RI k 7−→ max(ϕ) ∈ Mk,1 is a
homomorphism, by Lemma 1.10 and by the definition of multiplication in Mk,1. Hence RI k/≡ is
isomorphic to Mk,1. ✷
1.2 Other Thompson-Higman monoids
We now introduce a few more families of Thompson-Higman monoids, whose definition comes about
naturally in analogy with Mk,1.
Definition 1.11 The Thompson-Higman total function monoid totMk,1 and the Thompson-Higman
surjective function monoid surMk,1 consist of maximal essential extensions of homomorphisms between
finitely generated right ideals of A∗ where the domain, respectively, the image ideal, is an essential right
ideal.
The Thompson-Higman inverse monoid Invk,1 consists of all maximal essential extensions of iso-
morphisms between finitely generated (not necessarily essential) right ideals of A∗.
Every element ϕ ∈ totMk,1 can be described by a function P → Q, called the table of ϕ, where
P,Q ⊂ A∗ with P a finite maximal prefix code over A. A similar description applies to surMk,1 but
now with Q a finite maximal prefix code. Every ϕ ∈ Invk,1 can be described by a bijection P → Q
where P,Q ⊂ A∗ are two finite prefix codes (not necessarily maximal).
It is easy to prove that essential extension and restriction of right ideal homomorphisms, as well
as composition of such homomorphisms, preserve injectiveness, totality, and surjectiveness. Thus
totMk,1, surMk,1, and Invk,1 are submonoids of Mk,1.
We also consider the intersection totMk,1 ∩ surMk,1, i.e., the monoid of all maximal essential
extensions of homomorphisms between finitely generated essential right ideals of A∗; we denote this
monoid by totsurMk,1. The monoids Mk,1, totMk,1, surMk,1, and totsurMk,1 are regular monoids. (A
monoid M is regular iff for every m ∈ M there exists x ∈ M such that mxm = m.) The monoid
Invk,1 is an inverse monoid. (A monoid M is inverse iff for every m ∈ M there exists one and only
one x ∈M such that mxm = m and x = xmx.)
We consider the submonoids totInv k,1 and surInvk,1 of Invk,1, described by bijections P → Q
where P,Q ⊂ A∗ are two finite prefix codes with P , respectively Q maximal. The (unique) inverses
of elements in totInv k,1 are in surInvk,1, and vice versa, so these submonoids of Invk,1 are not regular
monoids. We have totInv k,1 ∩ surInvk,1 = Gk,1 (the Thompson-Higman group).
It is easy to see that for all n > 0, Mk,1 contains the symmetric monoids PF kn of all partial
functions on kn elements, represented by all elements of Mk,1 with a table P → Q where P,Q ⊆ An.
Hence Mk,1 contains all finite monoids. Similarly, totMk,1 contains the symmetric monoids Fkn of all
total functions on kn elements. And Invk,1 contains Ikn (the finite symmetric inverse monoid of all
injective partial functions on An).
1.3 Cuntz algebras and Thompson-Higman monoids
All the monoids, inverse monoids, and groups, defined above, are submonoids of the multiplicative
part of the Cuntz algebra Ok.
The Cuntz algebra Ok, introduced by Dixmier [16] (for k = 2) and Cuntz [14], is a k-generated
star-algebra (over the field of complex numbers) with identity element 1 and zero 0, given by the
following finite presentation. The generating set is A = {a1, . . . , ak}. Since this is defined as a star-
algebra, we automatically have the star-inverses {a1, . . . , ak}; for clarity we use overlines rather than
stars.
Relations of the presentation:
aiai = 1, for i = 1, . . . , k;
aiaj = 0, when i 6= j, 1 ≤ i, j ≤ k;
a1a1 + . . .+ akak = 1.
It is easy to verify that this defines a star-algebra. The Cuntz algebras are actually C∗-algebras with
many remarkable properties (proved in [14]), but here we only need them as star-algebras, without
their norm and Cauchy completion.
In [4] and independently in [27] it was proved that the Thompson-Higman group Gk,1 is the
subgroup of Ok consisting of the elements that have an expression of the form
x∈P f(x) x where we
require the following: P and Q range over all finite maximal prefix codes over the alphabet {a1, . . . , ak},
and f is any bijection P → Q. Another proof is given in [22]. More generally we also have:
Theorem 1.12 The Thompson-Higman monoid Mk,1 is a submonoid of the multiplicative part of
the Cuntz algebra Ok.
Proof outline. The Thompson-Higman partial function monoid Mk,1 is the set of all elements of Ok
that have an expression of the form
x∈P f(x) x where P ⊂ A∗ ranges over all finite prefix codes,
and f ranges over functions P → A∗.
The details of the proof are very similar to the proofs in [4, 27]; the definition of essential restriction
(and extension) and Proposition 1.4 insure that the same proof goes through. ✷
The embeddability into the Cuntz algebra is a further justification of the definitional choices that
we made for the Thompson-Higman monoid Mk,1.
2 Structure and simplicity of the Thompson-Higman monoids
We give some structural properties of the Thompson-Higman monoids; in particular, we show that
Mk,1 and Invk,1 are simple for all k.
2.1 Group of units, J-relation, simplicity
By definition, the group of units of a monoid M is the set of invertible elements (i.e., the elements
u ∈M for which there exists x ∈M such that xu = ux = 1, where 1 is the identity element of M).
Proposition 2.1 The Thompson-Higman group Gk,1 is the group of units of the monoids Mk,1,
totMk,1, surMk,1, totsurMk,1, and Invk,1.
Proof. It is obvious that the groups of units of the above monoids contain Gk,1. Conversely, we want
to show that that if ϕ ∈ Mk,1 (and in particular, if ϕ is in one of the other monoids) and if ϕ has a
left inverse and a right inverse, then ϕ ∈ Gk,1.
First, it follows that ϕ is injective, i.e., ϕ ∈ Invk,1. Indeed, existence of a left inverse implies that
for some α ∈Mk,1 we have α ϕ = 1; hence, if ϕ(x1) = ϕ(x2) then x1 = α ϕ(x1) = α ϕ(x2) = x2.
Next, we show that domC(ϕ) is a maximal prefix code, hence ϕ ∈ totInv k,1. Indeed, we can again
consider α ∈Mk,1 such that α ϕ = 1. For any essential restriction of 1 the domain code is a maximal
prefix code, hence domC(α ◦ ϕ) is maximal (where ◦ denotes functional composition). Moreover,
domC(α ◦ϕ) is also contained in the domain code of some restriction of ϕ, since ϕ(x) must be defined
when α ◦ ϕ(x) is defined. Hence domC(ϕ′), for some restriction ϕ′ of ϕ, is a maximal prefix code; it
follows that domC(ϕ) is a maximal prefix code.
If we apply the reasoning of the previous paragraph to ϕ−1 (which exists since we saw that ϕ is
injective), we conclude that domC(ϕ−1) = imC(ϕ) is a maximal prefix code. Thus, ϕ ∈ surInvk,1.
We proved that if ϕ has a left inverse and a right inverse then ϕ ∈ totInv k,1 ∩ surInv k,1. Since
totInv k,1 ∩ surInvk,1 = Gk,1 we conclude that ϕ ∈ Gk,1. ✷
We now characterize some of the Green relations of Mk,1 and of Invk,1, and we prove simplicity.
By definition, two elements x, y of a monoid M are J-related (denoted x ≡J y) iff x and y belong
to exactly the same ideals of M . More generally, the J-preorder of M is defined as follows: x ≤J y
iff x belongs to every ideal that y belongs to. It is easy to see that x ≡J y iff x ≤J y and y ≤J x;
moreover, x ≤J y iff there exist α, β ∈ M such that x = αyβ. A monoid M is called J-simple iff M
has only one J-class (or equivalently, M has only one ideal, namely M itself). A monoid M is called
0-J-simple iff M has exactly two J-classes, one of which consist of just a zero element (equivalently,
M has only two ideals, one of which is a zero element, and the other is M itself). See [13, 19] for more
information on the J-relation. Cuntz [14] proved that the multiplicative part of the C∗-algebra Ok is
a 0-J-simple monoid, and that as an algebra Ok is simple. We will now prove similar results for the
Thompson-Higman monoids.
Proposition 2.2 The inverse monoid Invk,1 and the monoid Mk,1 are 0-J-simple. The monoid
totMk,1 is J-simple.
Proof. Let ϕ ∈ Mk,1 (or ∈ Invk,1). When ϕ is not the empty map there are x0, y0 ∈ A∗ such that
y0 = ϕ(x0). Let us define α, β ∈ Invk,1 by the tables α = {(ε 7→ x0)} and β = {(y0 7→ ε)}. Recall that
ε denotes the empty word. Then β ϕα(.) = {(ε 7→ ε)} = 1. So, every non-zero element of Mk,1 (and
of Invk,1) is in the same J-class as the identity element.
In the case of totMk,1 we can take α = {(ε 7→ x0)} as before (since the domain code of α is {ε},
which is a maximal prefix code), and we take β′ : Q 7→ {ε} (i.e., the map that sends every element of Q
to ε), where Q is any finite maximal prefix code containing y0. Then again, β
′ ϕα(.) = {(ε 7→ ε)} = 1.
Thompson proved that V (= G2,1) is a simple group; Higman proved more generally that when k is
even then Gk,1 is simple, and when k is odd then Gk,1 contains a simple normal subgroup of index
2. We will show next that in the monoid case we have simplicity for all k (not only when k is even).
For a monoid M , “simple”, or more precisely, “congruence-simple” is defined to mean that the only
congruences on M are the trivial congruences (i.e., the equality relation, and the congruence that
lumps all elements of M into one congruence class).
Theorem 2.3 The Thompson-Higman monoids Invk,1 and Mk,1 are congruence-simple for all k.
Proof. Let ≡ be any congruence on Mk,1 that is not the equality relation. We will show that then
the whole monoid is congruent to the empty map 0. We will make use of 0-J -simplicity.
Case 0: Assume that Φ ≡ 0 for some element Φ 6= 0 of Mk,1. Then for all α, β ∈ Mk,1 we have
obviously αΦβ ≡ 0. Moreover, by 0-J -simplicity of Mk,1 we have Mk,1 = {αΦβ : α, β ∈ Mk,1}
since Φ 6= 0. Hence in this case all elements of Mk,1 are congruent to 0.
For the remainder we suppose that ϕ ≡ ψ and ϕ 6= ψ, for some elements ϕ,ψ of Mk,1 − {0}.
For a right ideal R ⊆ A∗ generated by a prefix code P we call PAω the set of ends of R. We
call two right ideals R1, R2 essentially equal iff R1 and R2 have the same ends, and we denote this
by R1 =ess R2. This is equivalent to the following property: Every right ideal that intersects R1 also
intersects R2, and vice versa (see [6] and [7]).
Case 1: Dom(ϕ) 6=ess Dom(ψ).
Then there exists x0 ∈ A∗ such that x0A∗ ⊆ Dom(ϕ), but Dom(ψ) ∩ x0A∗ = ∅; or, vice versa,
there exists x0 ∈ A∗ such that x0A∗ ⊆ Dom(ψ), but Dom(ϕ) ∩ x0A∗ = ∅. Let us assume the
former. Letting β = (x0 7→ x0), we have ϕβ(.) = (x0 7→ ϕ(x0)). We also have ψ β(.) = 0, since
∗ ∩Dom(ψ) = ∅. So, ϕβ ≡ ψ β = 0, but ϕβ 6= 0. Hence case 0, applied to Φ = ϕβ, implies that
the entire monoid Mk,1 is congruent to 0.
Case 2.1: Im(ϕ) 6=ess Im(ψ) and Dom(ϕ) =ess Dom(ψ).
Then there exists y0 ∈ A∗ such that y0A∗ ⊆ Im(ϕ), but Im(ψ) ∩ y0A∗ = ∅; or, vice versa,
∗ ⊆ Im(ψ), but Im(ϕ) ∩ y0A∗ = ∅. Let us assume the former. Let x0 ∈ A∗ be such that
y0 = ϕ(x0). Then (y0 7→ y0) ◦ ϕ ◦ (x0 7→ x0) = (x0 7→ y0).
On the other hand, (y0 7→ y0) ◦ ψ ◦ (x0 7→ x0) = 0. Indeed, if x0A∗ ∩ Dom(ψ) = ∅ then for all
w ∈ A∗ : ψ ◦ (x0 7→ x0)(x0w) = ψ(x0w) = ∅. And if x0A∗ ∩ Dom(ψ) 6= ∅ then for those w ∈ A∗
such that x0w ∈ Dom(ψ) we have (y0 7→ y0) ◦ψ ◦ (x0 7→ x0)(x0w) = (y0 7→ y0)(ψ(x0w)) = ∅, since
Im(ψ) ∩ y0A∗ = ∅. Now case 0 applies to 0 6= Φ = (y0 7→ y0) ◦ ϕ ◦ (x0 7→ x0) ≡ 0; hence all elements
of Mk,1 are congruent to 0.
Case 2.2: Im(ϕ) =ess Im(ψ) and Dom(ϕ) =ess Dom(ψ).
Then after restricting ϕ and ψ to Dom(ϕ) ∩ Dom(ψ) (=ess Dom(ϕ) =ess Dom(ψ)), we have:
domC(ϕ) = domC(ψ), and there exist x0 ∈ domC(ϕ) = domC(ψ) and y0 ∈ Im(ϕ), y1 ∈ Im(ψ) such
that ϕ(x0) = y0 6= y1 = ψ(x0). We have two sub-cases.
Case 2.2.1: y0 and y1 are not prefix-comparable.
Then (y0 7→ y0) ◦ ϕ ◦ (x0 7→ x0) = (x0 7→ y0).
On the other hand, (y0 7→ y0) ◦ ψ ◦ (x0 7→ x0)(x0w) = (y0 7→ y0)(y1w) = ∅ for all w ∈ A∗
(since y0 and y1 are not prefix-comparable). So (y0 7→ y0) ◦ψ ◦ (x0 7→ x0) = 0. Hence case 0 applies
to 0 6= Φ = (y0 7→ y0) ◦ ϕ ◦ (x0 7→ x0) ≡ 0.
Case 2.2.2: y0 is a prefix of y1, and y0 6= y1. (The case where y0 is a prefix of y1 is similar.)
Then y1 = y0au1 for some a ∈ A, u1 ∈ A∗. Letting b ∈ A−{a}, and y2 = y0b, we obtain a string y2
that is not prefix-comparable with y1. Now, (y2 7→ y2)◦ϕ◦(x0 7→ x0)(x0v2) = (y2 7→ y2)(y0v2) = y2.
But for all w ∈ A∗, (y2 7→ y2) ◦ψ ◦ (x0 7→ x0)(x0w) = (y2 7→ y2)(y1w) = ∅, since y2 and y1 are not
prefix-comparable. Thus, case 0 applies to 0 6= Φ = (y2 7→ y2) ◦ ϕ ◦ (x0 7→ x0) ≡ 0.
The same proof works for Invk,1 since all the multipliers used in the proof (of the form (u 7→ v)
for some u, v ∈ A∗) belong to Invk,1. ✷
2.2 D-relation
Besides the J-relation and the J-preorder, based on ideals, there are the R- and L−relations and
R- and L−preorders, based on right (or left) ideals. Two elements x, y ∈ M are R-related (denoted
x ≡R y) iff x and y belong to exactly the same right ideals of M . The R-preorder is defined as follows:
x ≤R y iff x belongs to every right ideal that y belongs to. It is easy to see that x ≡R iff x ≤R y and
y ≤R x; also, x ≤R y iff there exists α ∈ M such that x = yα. In a similar way one defines ≡L and
≤L. Finally, there is the D-relation of M , which is defined as follows: x ≡D y iff there exists s ∈ M
such that x ≡R s ≡L y; this is easily seen to be equivalent to saying that there exists t ∈M such that
x ≡L t ≡R y. For more information on these definitions see for example [13, 19].
The D-relation of Mk,1 and Invk,1 has an interesting characterization, as we shall prove next. We
will represent all elements of Mk,1 by tables of the from ϕ : P → Q, where both P and Q are finite
prefix codes over A (with |A| = k). For such a table we also write P = domC(ϕ) (the domain code
of ϕ) and Q = imC(ϕ) (the image code of ϕ). In general, tables of elements of Mk,1 have the form
P → S, where P is a finite prefix code and S is a finite set; but by using essential restrictions, if
necessary, every element of Mk,1 can be given a table P → Q, where both P and Q are finite prefix
codes.
Note the following invariants with respect to essential restrictions:
Proposition 2.4 Let ϕ1 : P1 → Q1 be a table for an element of Mk,1, where P1, Q1 ⊂ A∗ are finite
prefix codes. Let ϕ2 : P2 → Q2 be another finite table for the same element of Mk,1, obtained from the
table ϕ1 by an essential restriction. Then P2, Q2 ⊂ A∗ are finite prefix codes and we have
|P1| ≡ |P2| mod (k − 1) and
|Q1| ≡ |Q2| mod (k − 1).
These modular congruences also hold for essential extensions, provided that we only extend to tables
in which the image is a prefix code.
Proof. An essential restriction consists of a finite sequence of essential restriction steps; an essential
restriction step consists of replacing a table entry (x, y) of ϕ1 by {(xa1, ya1), . . . , (xak, yak)} (according
to Proposition 1.4). For a finite prefix code Q ⊂ A∗, and q ∈ Q, the finite set (Q−{q})∪{qa1, . . . , qak}
is also a prefix code, as is easy to prove. In this process, the cardinalities change as follows: |P1|
becomes |P1|−1+k and |Q1| becomes |Q1|−1+k. Indeed (looking at Q1 for example), first an element
y is removed from Q1, then the k elements {ya1, . . . , yak} are added. The elements yai that are added
are all different from the elements that are already present in Q1−{y}; in fact, more strongly, yai and
the elements of Q1 − {y} are not prefixes of each other. ✷
As a consequence of Prop. 2.4 it makes sense, for any ϕ ∈ Mk,1, to talk about |domC(ϕ)| and
|imC(ϕ)| as elements of Zk−1, independently of the representation of ϕ by a right-ideal homomorphism.
Theorem 2.5 For any non-zero elements ϕ,ψ of Mk,1 (or of Invk,1) the D-relation is characterized
as follows:
ϕ ≡D ψ iff |imC(ϕ)| ≡ |imC(ψ)| mod (k − 1).
Hence, Mk,1 and Invk,1 have k− 1 non-zero D-classes. In particular, M2,1 and Inv2,1 are 0-D-simple
(also called 0-bisimple).
The proof of Theorem 2.5 uses several Lemmas.
Lemma 2.6 ([5] Lemma 6.1; Arxiv version of [5] Lemma 9.9). For every finite alphabet A and every
integer i ≥ 0 there exists a maximal prefix code of cardinality 1+(|A|−1) i. And every finite maximal
prefix code over A has cardinality 1 + (|A| − 1) i, for some integer i ≥ 0.
It follows that when |A| = 2, there are finite prefix codes over A of every finite cardinality. ✷
As a consequence of this Lemma we have for all ϕ ∈ Gk,1: ‖ϕ‖ ≡ 1 mod (k− 1). Thus, except for the
Thompson group V (when k = 2), there is a constraint on the table size of the elements of the group.
In the following idQ denotes the element of Invk,1 given by the table {(x 7→ x) : x ∈ Q} where
Q ⊂ A∗ is any finite prefix code.
Lemma 2.7 (1) For any ϕ ∈ Mk,1 (or ∈ Invk,1) with table P → Q (where P,Q are finite prefix
codes) we have: ϕ ≡R idQ.
(2) If S, T are finite prefix codes with |S| = |T | then idS ≡D idT .
(3) If ϕ1 : P1 → Q1 and ϕ2 : P2 → Q2 are such that |Q1| = |Q2| then ϕ1 ≡D ϕ2.
Proof. (1) Let P ′ ⊆ P be a set of representatives modulo ϕ (i.e., we form P ′ by choosing one element
in every set ϕ−1ϕ(x) as x ranges over P ). So, |P ′| = |Q|. Let α ∈ Invk,1 be given by a table Q→ P ′;
the exact map does not matter, as long as α is bijective. Then ϕ ◦ α(.) is a permutation of Q, and
ϕ ◦ α ≡R ϕ ◦ α ◦ (ϕ ◦ α)−1 = idQ.
Now, ϕ ≥R ϕ ◦ α ≥R ϕ ◦ α ◦ (ϕ ◦ α)−1 ◦ ϕ = idQ ◦ ϕ = ϕ, hence ϕ ≡R ϕ ◦ α (≡R idQ).
(2) Let α : S → T be a bijection (which exists since |S| = |T |); so α represents an element of Invk,1.
Then α = α ◦ idS(.) and idS = α−1 ◦ α(.); hence, α ≡L idS .
Also, α = idT ◦ α(.) and idT = α ◦ α−1(.); hence, α ≡R idT . Thus, idS ≡L α ≡R idT .
(3) If |Q1| = |Q2| then idQ1 ≡D idQ2 by (2). Moreover, ϕ1 ≡D idQ1 and ϕ2 ≡D idQ2 by (1). The
result follows by transitivity of ≡D. ✷
Lemma 2.8 (1) For any m ≥ k let i be the residue of m modulo k − 1 in the range 2 ≤ i ≤ k,
and let us write m = i+ (k − 1)j, for some j ≥ 0. Then there exists a prefix code Qi,j of cardinality
|Qi,j| = m, such that idQi,j is an essential restriction of id{a1,...,ai}. Hence, idQi,j = id{a1,...,ai} as
elements of Invk,1.
(2) In Mk,1 and in Invk,1 we have id{a1} ≡D id{a1,...,ak} = 1.
Proof. (1) For any m ≥ k there exist i, j ≥ 0 such that 1 ≤ i ≤ k and m = i+ (k− 1)j. We consider
the prefix code
Qi,j = {a2, . . . , ai} ∪
r=1 a
1(A− {a1}) ∪ a
It is easy to see that Qi,j is a prefix code, which is maximal iff i = k; see Fig. 1 below. Clearly,
|Qi,j| = i + (k − 1)j. Since Qi,j contains aj1A, we can perform an essential extension of idQi,j by
replacing the table entries {(aj1a1, a
1a1), (a
1a2, a
1a2), . . . , (a
1ak, a
1ak)} by (a
1). This replaces Qi,j
by Qi,j−1. So, idQi,j can be essentially extended to idQi,j−1 . By repeating this we find that idQi,j is
the same element (in Mk,1 and in Invk,1) as idQi,0 = id{a1,...,ai}.
(2) By essential restriction, id{a1} = id{a1a1,a1a2,...,a1ak}, in Mk,1 and in Invk,1. And by Lemma 2.7(2),
id{a1a1,a1a2,...,a1ak} ≡D id{a1,...,ak}; the latter, by essential extension, is 1. ✷
{a2, . . . , ai}
❍❍. . .✁✁
a1 (A− {a1})
❍❍. . .✁✁
ar1 (A− {a1})
❍❍. . .✁✁
1 (A− {a1})
❍❍. . .✁✁
✁✁ ❆❆. . .
Fig. 1: The prefix tree of Qi,j.
Lemma 2.9 For all ϕ,ψ ∈ Invk,1: If ϕ ≥L(Mk,1) ψ, where ≥L(Mk,1) is the L-preorder of Mk,1, then
ϕ ≥L(Ik,1) ψ, where ≥L(Ik,1) is the L-preorder of Invk,1.
The same holds with ≥L replaced by ≡L, ≥R, ≡R, ≡D, ≥J and ≡J .
Proof. If ψ = αϕ for some α ∈ Mk,1 then let us define α′ by α′ = α idIm(ϕ). Then we have:
ψ ϕ−1 = α ϕ ϕ−1 = α idIm(ϕ) = α
′, hence α′ ∈ Invk,1 (since ϕ,ψ ∈ Invk,1). Moreover, α′ ϕ =
α idIm(ϕ) ϕ = αϕ = ψ. ✷
So far our Lemmas imply that in Mk,1 and in Invk,1, every non-zero element is ≡D to one of the
k − 1 elements id{a1,...,ai}, for i = 1, . . . , k − 1. Moreover the Lemmas show that if two elements of
Mk,1 (or of Invk,1) are given by tables ϕ1 : P1 → Q1 and ϕ2 : P2 → Q2, where P1, Q1, P2 and Q2 are
finite prefix codes, then we have: If |Q1| ≡ |Q2| mod (k − 1) then ϕ1 ≡D ϕ2.
We still need to prove the converse of this. It is sufficient to prove the converse for Invk,1, by
Lemma 2.9 and because every element of Mk,1 is ≡D to an element of Invk,1 (namely id{a1,...,ai}).
Lemma 2.10 Let ϕ,ψ ∈ Invk,1. If ϕ ≡D ψ in Invk,1, then ‖ϕ‖ ≡ ‖ψ‖ mod (k − 1).
Proof. (1) We first prove that if ϕ ≡L ψ then |domC(ϕ)| ≡ |domC(ψ)| mod (k − 1).
By definition, ϕ ≡L ψ iff ϕ = β ψ and ψ = αϕ for some α, β ∈ Invk,1. By Lemma 1.9 there are
restrictions β′ and ψ′ of β, respectively ψ, and an essential restriction Φ of ϕ such that:
Φ = β′ ◦ ψ′, and Dom(β′) = Im(ψ′).
It follows that Dom(Φ) ⊆ Dom(ψ′), since if ψ′(x) is not defined then Φ(x) = β′ ◦ ψ′(x) is not defined
either. Similarly, there is an essential restriction Ψ of ψ and a restriction ϕ′ of ϕ and such that
Dom(Ψ) ⊆ Dom(ϕ′).
Thus, the restriction of both ϕ and ψ to the intersection Dom(Φ)∩Dom(Ψ) yields restrictions ϕ′′,
respectively ψ′′ such that Dom(ϕ′′) = Dom(ψ′′).
Claim: ϕ′′ and ψ′′ are essential restrictions of ϕ, respectively ψ.
Indeed, every right ideal R of A∗ that intersects Dom(ψ) also intersects Dom(Ψ) (since Ψ is an
essential restriction of ψ). Since Dom(Ψ) ⊆ Dom(ϕ′) ⊆ Dom(ϕ), it follows that R also intersects
Dom(ϕ). Moreover, since Φ is an essential restriction of ϕ, R also intersects Dom(Φ). Thus, Dom(Φ)
is essential in Dom(ψ). Since Dom(Ψ) is also essential in Dom(ψ), it follows that Dom(Φ) ∩Dom(Ψ)
is essential in Dom(ψ); indeed, in general, the intersection of two right ideals R1, R2 that are essential
in a right ideal R3, is essential in R3 (this is a special case of Lemma 1.8). This means that ψ
′′ is an
essential restriction of ψ. Similarly, one proves that ϕ′′ is an essential restriction of ϕ. [This proves
the Claim.]
So, ϕ′′ and ψ′′ are essential restrictions such that Dom(ϕ′′) = Dom(ψ′′). Hence, domC(ϕ′′) =
domC(ψ′′); Proposition 2.4 then implies that |domC(ϕ)| ≡ |domC(ϕ′′)| = |domC(ψ′′)| ≡ |domC(ψ)|
mod (k − 1).
(2) Next, let us prove that if ϕ ≡R ψ then |imC(ϕ)| ≡ |imC(ψ)| mod (k−1). In Invk,1 we have ϕ ≡R ψ
iff ϕ−1 ≡L ψ−1. Also, imC(ϕ) = domC(ϕ−1). Hence, (2) follows from (1).
The Lemma now follows from (1) and (2), since for elements of Invk,1, |imC(ϕ)| = |domC(ϕ)| = ‖ϕ‖,
and since the D-relation is the composite of the L-relation and the R-relation. ✷
Proof of Theorem 2.5. We saw already (in the observations before Lemma 2.10 and in the preceding
Lemmas) that for ϕ1 : P1 → Q1 and ϕ2 : P2 → Q2 (where P1, Q1, P2 and Q2 are non-empty finite
prefix codes) we have: If |Q1| ≡ |Q2| mod (k − 1) then ϕ1 ≡D ϕ2. In particular, when |Q1| ≡ i
mod (k − 1) then ϕ1 ≡D id{a1,...,ai}.
It follows from Lemma 2.10 that the elements id{a1,...,ai} (for i = 1, . . . , k − 1) are all in different
D-classes. ✷
So far we have characterized the D- and J-relations of Mk,1 and Invk,1. We leave the general study
of the Green relations of Mk,1, Invk,1, and the other Thompson-Higman monoids for future work. The
main result of this paper, to be proved next, is that the Thompson-Higman monoids Mk,1 and Invk,1
are finitely generated and that their word problem over any finite generating set is in P.
3 Finite generating sets
We will show that Invk,1 and Mk,1 are finitely generated. An application of the latter fact is that a
finite generating set of Mk,1 can be used to build combinational circuits for finite boolean functions
that do not have fixed-length inputs or outputs. In engineering, non-fixed length inputs or outputs
make sense, for example, if the inputs or outputs are handled sequentially, and if the possible input
strings form a prefix code.
First we need some more definitions about prefix codes. The prefix tree of a prefix code P ⊂ A∗
is, by definition, a tree whose vertex set is the set of all the prefixes of the elements of P , and whose
edge set is {(x, xa) : a ∈ A, xa is a prefix of some element of P}. The tree is rooted, with root ε (the
empty word). Thus, the prefix tree of P is a subtree of the tree of A∗. The set of leaves of the prefix
tree of P is P itself. The vertices that are not leaves are called internal vertices. We will say more
briefly an “internal vertex of P” instead of internal vertex of the prefix tree of P . An internal vertex
has between 1 and k children; an internal vertex is called saturated iff it has k children.
One can prove easily that a prefix code P is maximal iff every internal vertex of the prefix tree of
P is saturated. Hence, every prefix code P can be embedded in a maximal prefix code (which is finite
when P is finite), obtained by saturating the prefix tree of P . Moreover we have:
Lemma 3.1 For any two finite non-maximal prefix codes P1, P2 ⊂ A∗ there are finite maximal prefix
codes P ′1, P
2 ⊂ A∗ such that P1 ⊂ P ′1, P2 ⊂ P ′2, and |P ′1| = |P ′2|.
Proof. First we saturate P1 and P2 to obtain two maximal prefix codes P
1 and P
2 such that P1 ⊂ P ′′1 ,
and P2 ⊂ P ′′2 . If |P ′′1 | 6= |P ′′2 | (e.g., if |P ′′1 | < |P ′′2 |) then |P ′′1 | and |P ′′2 | differ by a multiple of k − 1
(by Prop. 2.4). So, in order to make |P ′′1 | equal to |P ′′2 | we repeat the following (until |P ′′1 | = |P ′′2 |):
consider a leaf of the prefix tree of P ′′1 that does not belong to P1, and attach k children at that leaf;
now this leaf is no longer a leaf, and the net increase in the number of leaves is k − 1. ✷
Lemma 3.2 Let P and Q be finite prefix codes of A∗ with |P | = |Q|. If P and Q are both maximal
prefix codes, or if both are non-maximal, then there is an element of Gk,1 that maps P onto Q. On the
other hand, if one of P and Q is maximal and the other one is not maximal, then there is no element
of Gk,1 that maps P onto Q.
Proof. When P and Q are both maximal then any one-to-one correspondence between P and Q is
an element of Gk,1.
When P and Q are both non-maximal, we use Lemma 3.1 above to find two maximal prefix codes
P ′ and Q′ such that P ⊂ P ′, Q ⊂ Q′, and |P ′| = |Q′|. Consider now any bijection from P ′ onto Q′
that is also a bijection from P onto Q. This is an element of Gk,1.
When P is maximal and Q is non-maximal, then every element ϕ ∈Mk,1 that maps P onto Q will
satisfy domC(ϕ) = P ; since ϕ is onto Q, we have imC(ϕ) = Q. Hence, ϕ 6∈ Gk,1 since imC(ϕ) is a
non-maximal prefix code. A similar reasoning shows that no element of Gk,1 maps P onto Q if P is
non-maximal and Q is maximal. ✷
Notation: For u, v ∈ A∗, the element of Invk,1 with one-element domain code {u} and one-element
image code {v} is denoted by (u 7→ v). When (u 7→ v) is composed with itself j times the resulting
element of Invk,1 is denoted by (u 7→ v)j .
Lemma 3.3 (1) For all j > 0: (a1 7→ a1a1)j = (a1 7→ aj+11 ).
(2) Let S = {aj1a1, a
1a2, . . . , a
1ai}, for some 1 ≤ i ≤ k−1, 0 ≤ j. Then idS is generated by the k+1
elements {(a1 7→ a1a1), (a1a1 7→ a1)} ∪ {id{a1a1, a1a2, ..., a1ai} : 1 ≤ i ≤ k − 1}.
(3) For all j ≥ 2: (ε 7→ aj1)(.) = (a1 7→ a1a1)j−1 · (ε 7→ a1)(.).
Proof. (1) We prove by induction that (a1 7→ a1a1)j = (a1 7→ a1aj1) for all j ≥ 1.
Indeed, (a1 7→ a1a1)j+1(.) = (a1 7→ a1a1) · (a1 7→ a1aj1)(.), and by essential restriction this is
1 a1w (w ∈ Aj − {a
a1a1a
1 a1a1w
· (a1 7→ a1aj1)(.) = (a1 7→ a1a1a
1)(.).
(2) For S = {aj1a1, a
1a2, . . . , a
1ai} we have
idS =
a1a1 a1a2 . . . a1ai
1a1 a
1a2 . . . a
1a1 a
1a2 . . . a
a1a1 a1a2 . . . a1ai
a1a1 a1a2 . . . a1ai
1a1 a
1a2 . . . a
a1a1 a1a2 . . . a1ai a1ai+1 . . . a1ak
1a1 a
1a2 . . . a
1ai a
1ai+1 . . . a
· id{a1a1, a1a2, ..., a1ai}(.)
= (a1 7→ aj1)· id{a1a1, a1a2, ..., a1ai} = (a1 7→ a1a1)
j−1· id{a1a1, a1a2, ..., a1ai}.
The map id{a1a1} is redundant as a generator since (a1a1 7→ a1a1) = (a1a1 7→ a1) (a1 7→ a1a1)(.).
(3) By (1) we have (ε 7→ aj1) = (a1 7→ a
1) · (ε 7→ a1)(.), and (a1 7→ a
1) = (a1 7→ a1a1)j−1. ✷
Theorem 3.4 The inverse monoid Invk,1 is finitely generated.
Proof. Our strategy for finding a finite generating set for Invk,1 is as follows: We will use the fact
that the Thompson-Higman group Gk,1 is finitely generated. Hence, if ϕ ∈ Invk,1, g1, g2 ∈ Gk,1, and
if g2ϕg1 can be expressed as a product p over a fixed finite set of elements of Invk,1, then it follows
that ϕ = g−12 p g
1 can also be expressed as a product over a fixed finite set of elements of Invk,1. We
assume that a finite generating set for Gk,1 has been chosen.
For any element ϕ ∈ Invk,1 with domain code domC(ϕ) = P and image code imC(ϕ) = Q, we
distinguish four cases, depending on the maximality or non-maximality of P and Q.
(1) If P and Q are both maximal prefix codes then ϕ ∈ Gk,1, and we can express ϕ over a finite fixed
generating set of Gk,1.
(2) Assume P and Q are both non-maximal prefix codes. By Lemma 3.1 there are finite maximal prefix
codes P ′, Q′ such that P ⊂ P ′, Q ⊂ Q′, and |P ′| = |Q′|; and by Lemma 2.6, |P ′| = |Q′| = 1+(k−1)N
for someN ≥ 0. Consider the following maximal prefix code C, of cardinality |P ′| = |Q′| = 1+(k−1)N :
r=0 a
1(A− {a1}) ∪ a
The maximal prefix code C is none other than the code Qi,j when i = k and j = N − 1 (introduced
in the proof of Lemma 2.8, Fig. 1). The elements g1 : C → P ′ and g2 : Q′ → C of Gk,1 can be chosen
so that ψ = g2ϕg1(.) is a partial identity with domC(ψ) = imC(ψ) ⊂ C consisting of the |P | first
elements of C in the dictionary order. So, ψ is the identity map restricted to these |P | first elements
of C, and ψ is undefined on the rest of C. To describe domC(ψ) = imC(ψ) in more detail, let us write
|P | = i+ (k − 1) ℓ, for some i, ℓ with 1 ≤ i < k and 0 ≤ ℓ ≤ N − 1. Then
domC(ψ) = imC(ψ) = aN−11 A ∪
r=j+1 a
1(A− {a1}) ∪ a
1 {a2, . . . , ai}.
where j = N − 1− ℓ. Since ψ = iddomC(ψ), we claim:
By essential maximal extension
ψ = idS (as elements of Invk,1), where S = {aj1a1, a
1a2, . . . , a
1ai},
with i, j as in the description of domC(ψ) = imC(ψ) above, i.e., 1 < i < k, N−1 ≥ j = N−1− ℓ ≥ 0,
and |P | = i+ (k − 1) ℓ.
Indeed, if |P | < k then S is just domC(ψ), with i = |P |, and ℓ = 0 (hence j = N − 1). If
|P | ≥ k then the maximum essential extension of ψ will replace the 1 + (k − 1) ℓ elements aN−11 A ∪
r=N−j+1 a
1(A− {a1}) by the single element a
N−ℓ+1
1 = a
1 . What remains is the set
S = {aj+11 } ∪ a
1 {a2, . . . , ai}.
Finally, by Lemma 3.3, idS (where S = {aj1a1, a
1a2, . . . , a
1ai}) can be generated by the k + 1
elements {(a1 7→ a1a1), (a1a1 7→ a1)} ∪ {id{a1a1, a1a2, ..., a1ai} : 1 ≤ i ≤ k − 1}.
(3) Assume P is a maximal prefix code and Q is non-maximal. Let Q′ be the finite maximal prefix code
obtained by saturating the prefix tree of Q. Then Q ⊂ Q′, |Q′| = 1+(k−1)N ′, and |P | = 1+(k−1)N
for some N ′ > N ≥ 0. We consider the maximal prefix codes C and C ′ as defined in the proof of (2),
using N ′ for defining C ′. We can choose g1 : C → P and g2 : Q′ → C ′ in Gk,1 so that ψ = g2ϕg1(.) is
the dictionary-order preserving map that maps C to the first |C| elements of C ′. So we have
domC(ψ) = C, and
imC(ψ) = S0 , where S0 ⊂ C ′ consist of the |C| first elements of C ′, in dictionary order.
Since |C| = 1 + (k − 1)N , we can describe S0 in more detail by
⋃N ′−2
r=N ′−N a
1(A− {a1}) ∪ a
N ′−1
Next, by essential maximal extension we now obtain ψ = (ε 7→ aN
Indeed, we saw that |P | = 1+ (k− 1)N . If |P | = 1 then P = {ε}, and ψ = (ε 7→ aN ′1 ). If |P | ≥ k
then maximum essential extension of ψ will replace all the elements of C by the single element ε, and
it will replace all the elements of S0 by the single element a
N ′−N
Finally, by Lemma 3.3, (ε 7→ aN ′−N1 ) is generated by the two elements (ε 7→ a1) and (a1 7→ a1a1).
(4) The case where P is a non-maximal maximal prefix code and Q is maximal can be derived from
case (3) by taking the inverses of the elements from case (3). ✷
Theorem 3.5 The monoid Mk,1 is finitely generated.
Proof. Let ϕ : P → Q be the table of any element of Mk,1, mapping P onto Q, where P,Q ⊂ A∗
are finite prefix codes. The map described by the table is total and surjective, so if |P | = |Q| (and in
particular, if ϕ is the empty map) then ϕ ∈ Invk,1, hence ϕ can be expressed over the finite generating
set of Invk,1. In the rest of the proof we assume |P | > |Q|. The main observation is the following.
Claim. ϕ can be written as the composition of finitely many elements ϕi ∈Mk,1 with tables Pi → Qi
such that 0 ≤ |Pi| − |Qi| ≤ 1.
Proof of the Claim: We use induction on |P | − |Q|. There is nothing to prove when |P | − |Q| ≤ 1, so
we assume now that |P | − |Q| ≥ 2.
If ϕ(x1) = ϕ(x2) = ϕ(x3) = y1 for some x1, x2, x3 ∈ P (all three being different) and y1 ∈ Q, then
we can write ϕ as a composition ϕ(.) = ψ2 ◦ψ1(.), as follows. The map ψ1 : P −→ P −{x1} is defined
by ψ1(x1) = ψ1(x2) = x2, and acts as the identity everywhere else on P . The map ψ2 : P −{x1} −→ Q
is defined by ψ2(x2) = ψ2(x3) = y1, and acts in the same way as ϕ everywhere else on P −{x1}. Then
for ψ1 we have |P | − |P − {x1}| < |P | − |Q|, and for ψ2 we have |P − {x1}| − |Q| < |P | − |Q|.
If ϕ(x1) = ϕ(x2) = y1 and ϕ(x3) = ϕ(x4) = y2 for some x1, x2, x3, x4 ∈ P (all four being different)
and y1, y2 ∈ Q (y1 6= y2), then we can write ϕ as a composition ϕ(.) = ψ2 ◦ψ1(.), as follows. First the
map ψ1 : P −→ P −{x1} is defined by ψ1(x1) = ψ1(x2) = x2, and acts as the identity everywhere else
on P . Second, the map ψ2 : P −{x1} −→ Q is defined by ψ2(x2) = y1 and ψ2(x3) = ψ2(x4) = y2, and
acts like ϕ everywhere else on P − {x1}. Again, for ψ1 we have |P | − |P − {x1}| < |P | − |Q| and
for ψ2 we have |P − {x1}| − |Q| < |P | − |Q|. [End, proof of the Claim.]
Because of the Claim we now only need to consider elements ϕ ∈ Mk,1 with tables P → Q such
that the prefix codes P,Q satisfy |P | = |Q|+ 1. We denote P = {p1, . . . , pn} and Q = {q1, . . . , qn−1},
with ϕ(pj) = qj for 1 ≤ j ≤ n− 1, and ϕ(pn−1) = ϕ(pn) = qn−1. We define the following prefix code
C with |C| = |P |:
• if |P | = i ≤ k then C = {a1, . . . , ai}; note that i ≥ 2, since |P | > |Q| > 0;
• if |P | > k then C = {a2, . . . , ai} ∪
r=1 a
1(A− {a1}) ∪ a
where i, j are such that |P | = i + (k − 1)j, 2 ≤ i ≤ k, and 1 ≤ j (see Fig. 1). Let us write C in
increasing dictionary order as C = {c1, . . . , cn}. The last element of C in the dictionary order is thus
cn = ai.
We now write ϕ(.) = ψ3 ψ2 ψ1(.) where ψ1, ψ2, ψ3 are as follows:
• ψ1 : P −→ C is bijective and is defined by pj 7→ cj for 1 ≤ j ≤ n;
• ψ2 : C −→ C − {ai} is the identity map on {c1, . . . , cn−1}, and ψ2(cn) = cn−1.
• ψ3 : C − {ai} −→ Q is bijective and is defined by cj 7→ qj for 1 ≤ j ≤ n− 1.
It follows that ψ1 and ψ3 can be expressed over the finite generating set of Invk,1. On the other
hand, ψ2 has a maximum essential extension, as follows.
• If 2 ≤ |P | = i ≤ k then
a1 . . . ai−2 ai−1 ai
a1 . . . ai−2 ai−1 ai−1
id{a1, ..., ai−1} ai
• If |P | = i+ (k − 1)j > k and if i > 2 then, after maximal essential extension, ψ2 also becomes
max(ψ2) =
id{a1, ..., ai−1} ai
• If |P | = i+ (k − 1)j > k and if i = 2 then, after essential extensions,
max(ψ2) =
a1a1 . . . a1ak−2 a1ak−1 a1ak a2
a1a1 . . . a1ak−2 a1ak−1 a1ak a1ak
ida1A a2
a1 a2
a1 a1ak
In summary, we have factored ϕ over a finite set of generators of Invk,1 and k additional generators
in Mk,1. ✷
Factorization algorithm: The proofs of Theorems 3.4 and 3.5 are constructive; they provide algo-
rithms that, given ϕ ∈ Invk,1 or ∈ Mk,1, output a factorization of ϕ over the finite generating set of
Invk,1, respectively Mk,1.
In [20] (p. 49) Higman introduces a four-element generating set for G2,1; a special property of these
generators is that their domain codes and their image codes only contain words of length ≤ 2, and
∣ |γ(x)| − |x|
∣ ≤ 1 for every generator γ and every x ∈ domC(γ). The generators in the finite
generating set of Mk,1 that we introduced above also have those properties. Thus we obtain:
Corollary 3.6 The monoid M2,1 has a finite generating set such that all the generators have the
following property: The domain codes and the image codes only contain words of length ≤ 2, and
∣ |γ(x)| − |x|
∣ ≤ 1 for every generator γ and every x ∈ domC(γ). ✷
For reference we list an explicit finite generating set forM2,1. It consists, first, of the Higman generators
of G2,1 ([20] p. 49):
Not =
, (01 ↔ 1) =
00 01 1
00 1 01
, (0 ↔ 10) =
0 10 11
10 0 11
, and
τ1,2 =
00 01 10 11
00 10 01 11
the additional generators for Inv2,1:
(ε→ 0), (0 → ε), (0 → 00), (00 → 0);
the additional generators for M2,1:
, and
00 01 1
00 01 01
Observe that Higman’s generators of Gk,1 (in [20] p. 27) have domain and image codes with at most
3 internal vertices. We observe that the additional generators that we introduced for Invk,1 and Mk,1
have domain and image codes have at most 2 internal vertices.
The following problem remains open: Are Invk,1 and Mk,1 finitely presented?
4 The word problem of the Thompson-Higman monoids
We saw that the Thompson-Higman monoid Mk,1 is finitely generated. We want to show now that
the word problem of Mk,1 over any finite generating set can be decided in deterministic polynomial
time, i.e., it belongs to the complexity class P. 2
In [4] it was shown that the word problem of the Thompson-Higman group Gk,1 over any finite
generating set is in P. In fact, it is in the parallel complexity class AC1 [4], and it is co-context-free
[25]. In [5] it was shown that the word problem of the Thompson-Higman group Gk,1 over the infinite
generating set Γk,1∪{τi,i+1 : i > 0} is coNP-complete, where Γk,1 is any finite generating set of Gk,1;
the position transposition τi,i+1 ∈ Gk,1 has domC(τi,i+1) = imC(τi,i+1) = Ai+1, and is defined by
uαβ 7→ uβα for all letters α, β ∈ A and all words u ∈ Ai−1. We will see below that the word problem
of Mk,1 over Γk,1 ∪ {τi,i+1 : i > 0} is also coNP-complete, where Γk,1 is any finite generating set of
Mk,1.
4.1 The image code formula
Our proof in [4] that the word problem of the Thompson-Higman group Gk,1 (over any finite generating
set) is in P, was based on the following fact (the table size formula):
∀ϕ,ψ ∈ Gk,1: ‖ψ ◦ ϕ‖ ≤ ‖ψ‖+ ‖ϕ‖.
Here ‖ϕ‖ denotes the table size of ϕ, i.e., the cardinality of domC(ϕ). See Proposition 3.5, Theorem
3.8, and Proposition 4.2 in [4]. In Mk,1 the above formula does not hold in general, as the following
example shows. We give some definitions and notation first.
Definition 4.1 For any finite set S ⊆ A∗ we denote the length of the longest word in S by ℓ(S). The
cardinality of S is denoted by |S|.
The table of a right-ideal morphism ϕ is the set {(x, ϕ(x)) : x ∈ domC(ϕ)}.
2 This section has been revised in depth, to correct errors.
Proposition 4.2 For every n > 0 there exists Φn = ϕ
2 ϕ1 ∈ M2,1 (for some ϕ1, ϕ2 ∈ M2,1) with
the following properties:
The table sizes are ‖Φn‖ = 2n, and ‖ϕ2‖ = ‖ϕ1‖ = 2. So, ‖Φn‖ is exponentially larger than
(n− 1) · ‖ϕ2‖+ ‖ϕ1‖. Hence the table size formula does not hold in M2,1.
The word lengths of ϕ1, ϕ2, and Φn (over the finite generating set Γ of M2,1 from Section 3 in [1])
satisfy |ϕ1|Γ = 1, |ϕ2|Γ ≤ 2, and |Φn|Γ < 2n. So the table size of Φn is exponentially larger than its
word length: ‖Φn‖ >
|Φn|Γ .
Proof. Consider ϕ1, ϕ2 ∈ M2,1 given by the tables ϕ1 = {(0 7→ 0), (1 7→ 0)}, and ϕ2 = {(00 7→
0), (01 7→ 0)}. One verifies that Φn = ϕn−12 ◦ ϕ1(.) sends every bitstring of length n to the word
0; its domain code is {0, 1}n, its image code is {0}, and it is its maximum essential extension. Thus,
‖ϕn−12 ◦ ϕ1‖ = 2n, whereas (n − 1) · ‖ϕ2‖+ ‖ϕ1‖ = 2n. Also, ϕ2(.) = (0 7→ 0, 1 7→ 0) · (0 7→ ε), so
|ϕ1|Γ = 1, |ϕ2|Γ ≤ 2, and |Φn|Γ ≤ 2n− 1; hence ‖Φn‖ > 2|Φn|Γ/2. ✷
We will use the following facts that are easy to prove: If R ⊂ A∗ is a right ideal and ϕ is a
right-ideal morphism then ϕ(R) and ϕ−1(R) are right ideals. The intersection and the union of right
ideals are right ideals. We also need the following result.
(Lemma 3.3 of [4]) If P,Q, S ⊆ A∗ are such that PA∗ ∩QA∗ = SA∗, and if S is a prefix code then
S ⊆ P ∪Q. ✷
Lemma 4.3 Let θ be a right-ideal morphism, and assume SA∗ ⊆ Dom(θ), where S ⊂ A∗ is a finite
prefix code. Then there is a finite prefix code R ⊂ A∗ such that θ(SA∗) = RA∗ and R ⊆ θ(S).
Proof. Since θ is a right-ideal morphism we have θ(SA∗) = θ(S) A∗. Since θ(S) might not be a
prefix code we take R = {r ∈ θ(S) : r is minimal (shortest) in the prefix order within θ(S)}. Then R
is a prefix code that has the required properties. ✷
Lemma 4.4 3 For any right-ideal morphism θ and any prefix code Z ⊂ A∗, θ−1(Z) is a prefix code.
In particular, θ−1(imC(θ)) is a prefix code, and θ−1(imC(θ)) ⊆ domC(θ). There exist right-ideal
morphisms θ with finite domain code, such that θ−1(imC(θ)) 6= domC(θ).
Proof. First, θ−1(Z) is a prefix code. Indeed, if we had x1 = x2u for some x1, x2 ∈ θ−1(Z) with u
non-empty, then θ(x1) = θ(x2) u, with θ(x1), θ(x2) ∈ Z. This would contradict the assumption that
Z is a prefix code.
Second, let Q = imC(θ); then θ−1(Q)A∗ ⊆ θ−1(QA∗). Indeed, if x ∈ θ−1(Q), then x = pw for some
p ∈ domC(θ) and w ∈ A∗. Hence, θ(x) = θ(p)w, and θ(x) ∈ Q. Since θ(p)w ∈ Q and θ(p) ∈ QA∗, we
have θ(p)w = θ(p) (since Q is a prefix code). So w is empty, hence x = pw = p ∈ domC(θ).
Example: Let A = {0, 1}, and let θ be the right-ideal morphism defined by domC(θ) = {01, 1},
imC(θ) = {ε}, and θ(01) = 0, θ(1) = ε. Then, θ−1(imC(θ)) = {1} 6= domC(θ). ✷
The following generalizes the “table size formula” of Gk,1 to the monoid Mk,1.
Theorem 4.5 (Generalized image code formulas). 4
Let ϕi be right-ideal morphism with finite domain codes, for i = 1, 2, . . . , n. Then
∣imC(ϕn ◦ . . . ◦ ϕ1)
∣ ≤ |imC(ϕ1)| +
i=2 |ϕi(domC(ϕi))|,
(2) ℓ
domC(ϕn ◦ . . . ◦ ϕ1)
i=1 ℓ(domC(ϕi)),
3 This Lemma was incorrect in the earlier versions of this paper and in [1].
4 This Theorem was incorrect in the previous versions and in [1]; this is a corrected (and expanded) version.
(3) ℓ
ϕn . . . ϕ1(domC(ϕn ◦ . . . ◦ ϕ1))
i=1 ℓ(ϕi(domC(ϕi))),
(4) ℓ
imC(ϕn ◦ . . . ◦ ϕ1)
≤ ℓ(imC(ϕ1)) +
i=2 ℓ(ϕi(domC(ϕi))),
∣ϕn . . . ϕ1(domC(ϕn ◦ . . . ◦ ϕ1))
i=1 |(ϕi(domC(ϕi))|, and
ϕn . . . ϕ1(domC(ϕn ◦ . . . ◦ ϕ1)) ⊆
i=1 ϕn . . . ϕi(domC(ϕi)).
Proof. Let Pi = domC(ϕi) and Qi = imC(ϕi).
(1) The proof is similar to the proof of Proposition 3.5 in [4]. We have Dom(ϕ2 ◦ϕ1) = ϕ−11 (Q1A∗ ∩
∗) and Im(ϕ2◦ϕ1) = ϕ2(Q1A∗∩P2A∗). So the following maps are total and onto on the indicated
sets:
ϕ−11 (Q1A
∗ ∩ P2A∗)
ϕ1−→ Q1A∗ ∩ P2A∗
ϕ2−→ ϕ2(Q1A∗ ∩ P2A∗).
By Lemma 3.3 of [4] (quoted above) we have Q1A
∗ ∩ P2A∗ = SA∗ for some finite prefix code S with
S ⊆ Q1 ∪ P2. Moreover, by Lemma 4.3 we have ϕ2(SA∗) = R2A∗ for some finite prefix code R2
such that R2 ⊆ ϕ2(S). Now, since S ⊆ Q1 ∪ P2 we have R2 ⊆ ϕ2(S) ⊆ ϕ2(Q1) ∪ ϕ2(P2). Thus,
|imC(ϕ2 ◦ ϕ1)| = |R2| ≤ |ϕ2(P2)|+ |ϕ2(Q1)|. Since |ϕ2(Q1)| ≤ |Q1|, we have |R2| ≤ |ϕ2(P2)|+ |Q1|.
By induction for n > 2, |imC(ϕn ◦ ϕn−1 ◦ . . . ◦ϕ1)| ≤ |ϕn(domC(ϕn))| + |imC(ϕn−1 ◦ . . . ◦ϕ1)|
≤ |ϕn(domC(ϕn))| +
i=2 |ϕi(domC(ϕi))| + |imC(ϕ1)| .
(2) We prove the formula when n = 2; the general formula then follows immediately by induction.
Let x ∈ domC(ϕ2 ◦ ϕ1); then ϕ1(x) is defined, hence x = p1u for some p1 ∈ P1, u ∈ A∗. And ϕ2 is
defined on ϕ1(x) = ϕ1(p1)u, so ϕ1(x) ∈ P2A∗ = Dom(ϕ2). Hence there exist p2 ∈ P2 and v ∈ A∗ such
(⋆) ϕ1(p1)u = p2v ∈ ϕ1(P1)A∗ ∩ P2A∗.
It follows that u and v are suffix-comparable.
Claim. The words u and v in (⋆) satisfy: u = ε, or v = ε.
Proof of the Claim: Since u and v are suffix-comparable, let us first consider the case where v is a
suffix of u, i.e., u = tv for some t ∈ A∗. Then ϕ1(x) = ϕ1(p1) tv = p2v, hence ϕ1(p1) t = p2, hence ϕ2
is defined on ϕ1(p1) t = p2. So, ϕ2 ◦ ϕ1 is defined on p1t, i.e., p1t ∈ domC(ϕ2 ◦ ϕ1). But we also have
x = p1tv ∈ domC(ϕ2 ◦ ϕ1). Since domC(ϕ2 ◦ ϕ1) is a prefix code, it follows that v = ε.
Let us next consider the other case, namely where u is a suffix of v, i.e., v = su for some s ∈ A∗.
Then ϕ1(x) = ϕ1(p1)u = p2su, hence ϕ1(p1) = p2s, hence ϕ2 is defined on ϕ1(p1) = p2s, hence
p1 ∈ domC(ϕ2 ◦ ϕ1). But we also have x = p1u ∈ domC(ϕ2 ◦ ϕ1). Since domC(ϕ2 ◦ ϕ1) is a prefix
code, it follows that u = ε. [This proves the Claim.]
Now for x ∈ domC(ϕ2 ◦ ϕ1) we have x = p1u, and ϕ1(p1)u = p2v, hence |x| = |p1| + |u| and
|ϕ1(p1)|+ |u| = |p2|+ |v|. By the Claim, either |u| = 0 or |v| = 0.
If |u| = 0 then |x| = |p1| ≤ ℓ(domC(ϕ1)).
If |v| = 0 then |x| = |p1|+ |u| = |p1|+ |p2|+ |v| − |ϕ1(p1)| = |p1|+ |p2| − |ϕ1(p1)| ≤ |p1|+ |p2| ≤
ℓ(domC(ϕ1)) + ℓ(domC(ϕ2)).
(3) As in the proof of (2) we only need to consider n = 2. Let x ∈ domC(ϕ2ϕ1), hence ϕ2ϕ1(x) ∈
ϕ2ϕ1(domC(ϕ2ϕ1)). By (⋆) (and with the notation of the proof of (2)) we have ϕ2ϕ1(x) = ϕ2(ϕ1(p1)u)
= ϕ2(p2) v ∈ ϕ2(ϕ1(P1)A∗ ∩ P2A∗) = Im(ϕ2ϕ1). By the reasoning of the proof of (2), we have two
cases:
If |u| = 0 then |v| = |ϕ1(p1)| + |u| − |p2| = |ϕ1(p1)| − |p2| ≤ |ϕ1(p1)|. Hence, |ϕ2ϕ1(x)| =
|ϕ2(p2)|+ |v| ≤ |ϕ2(p2)|+ |ϕ1(p1)| ≤ ℓ(ϕ2(domC(ϕ2)) + ℓ(ϕ1(domC(ϕ1)).
If |v| = 0 then ϕ2ϕ1(x) = ϕ2(p2), hence |ϕ2ϕ1(x)| = |ϕ2(p2)| ≤ ℓ(ϕ2(domC(ϕ2)).
(4) We first consider the case n = 2. As we saw in the proof of (1), imC(ϕ2ϕ1) = R2 whereR2 ⊆ ϕ2(S),
and where S is a prefix code such that S ⊆ Q1 ∩ P2. Hence R2 ⊆ ϕ2(Q1) ∪ ϕ2(P2).
Hence for any z ∈ R2, either z ∈ ϕ2(P2) or z ∈ ϕ2(Q1). If z ∈ ϕ2(P2) then |z| ≤ ℓ(ϕ2(P2)). If
z ∈ ϕ2(Q1), then z = ϕ2(q1) for some q1 ∈ Q1 ∩ P2A∗, so q1 = p2u for some p2 ∈ P2 and u ∈ A∗. We
have q1 ∈ P2A∗ (= Im(ϕ2)), so q1 ∈ Im(ϕ2). Now |z| = |ϕ2(p2)| + |u|, and |u| = |q1| − |p2| ≤ |q1| ≤
ℓ(imC(ϕ1)). Thus, |z| ≤ |ϕ2(p2)|+ ℓ(imC(ϕ1)) ≤ ℓ(ϕ2(domC(ϕ2))) + ℓ(imC(ϕ1)).
The formula for n > 2 now follows by induction in the same way as in the proof of (1).
(5) We first prove the formula for n = 2. As we saw in the proof of (2), if x ∈ domC(ϕ2ϕ1) then
there exist u, v ∈ A∗, p1 ∈ P1, p2 ∈ P2, such that x = p1u and ϕ1(x) = ϕ1(p1)u = p2v. Moreover, by
the Claim in (2) we have u = ε or v = ε. Also, ϕ2ϕ1(x) = ϕ2(ϕ1(p1)u) = ϕ2(p2) v.
If v = ε then ϕ2ϕ1(x) = ϕ2(p2) ∈ ϕ2(domC(ϕ2)). If u = ε then ϕ2ϕ1(x) = ϕ2ϕ1(p1) ∈
ϕ2ϕ1(domC(ϕ1)). Thus we proved the following fact:
ϕ2ϕ1(domC(ϕ2ϕ1)) ⊆ ϕ2(domC(ϕ2)) ∪ ϕ2ϕ1(domC(ϕ1)).
Now, since |ϕ2ϕ1(domC(ϕ1))| ≤ |ϕ1(domC(ϕ1))|, the fact implies that |ϕ2ϕ1(domC(ϕ2ϕ1))| ≤
|ϕ2(domC(ϕ2))| + |ϕ1(domC(ϕ1))|. By induction we immediately obtain
∣ϕn . . . ϕ1(domC(ϕn ◦ . . . ◦ ϕ1))
i=1 |(ϕi(domC(ϕi))|, and
ϕn . . . ϕ1(domC(ϕn ◦ . . . ◦ ϕ1))
⊆ ϕn(domC(ϕn)) ∪ ϕnϕn−1(domC(ϕn−1)) ∪ . . . . . . . . .
∪ ϕn . . . ϕi(domC(ϕi)) ∪ . . . . . . . . . ∪ ϕn . . . ϕi . . . ϕ1(domC(ϕ1)). ✷
Remarks. Obviously, Dom(ϕ2ϕ1) ⊆ Dom(ϕ1); however, in infinitely many cases (in “most” cases),
domC(ϕ2ϕ1) 6⊆ domC(ϕ1). Instead, we have the more complicated formula of Theorem 4.5(5).
By Prop. 4.2, we cannot have a formula for |domC(ϕn . . . ϕ1)| of a similar nature as the formulas
in Theorem 4.5.
The following class of right-ideal morphisms plays an important role here (as well as in Section 5 of
[7], where it was introduced). 5
Definition 4.5A (Normal). A right-ideal morphism ϕ is called normal iff ϕ(domC(ϕ)) = imC(ϕ).
By Lemma 5.7 of [7] we also have: ϕ is normal iff ϕ−1(imC(ϕ)) = domC(ϕ). In other words, ϕ is
normal iff ϕ is entirely determined by the way it maps domC(ϕ) onto imC(ϕ).
For example, every injective right-ideal morphism is normal (by Lemma 5.1 in [7]). The finite
generating set Γ of Mk,1, constructed in Section 3, consist entirely of normal right-ideal morphisms.
On the other hand, the composition of two normal right-ideal morphisms does not always result
in a normal morphism, as is shown by the following example: domC(f) = {0, 1} and f(0) = 0,
f(1) = 10; domC(g) = {0, 1} and g(0) = g(1) = 0; so f and g are normal. But domC(gf) = {0, 1}
and gf(0) = 0, gf(1) = 00; so gf is not normal (for more details, see Prop. 5.8 in [7]).
The next result (Theorem 4.5B) shows that every element of Mk,1 can be represented by a normal
right-ideal morphism. So one can say informally that “from the point of view of Mk,1, all right-ideal
morphisms are normal”. For proving this we need some definitions. We always assume |A| ≥ 2.
Definitions and notation. If x1, x2 ∈ A∗ are such that x1 is a prefix of x2, i.e., x2 ∈ x1A∗, we
denote this by x1 ≤pref x2.
For Z ⊆ A∗, the set of prefixes of Z is pref(Z) = {v ∈ A∗ : v ≤pref z for some z ∈ Z}.
5 Def. 4.5A, Theorem 4.5B, and Cor. 4.5C are new in this version.
For a set X ⊆ A∗ and a word v ∈ A∗, v−1X denotes the set {s ∈ A∗ : vs ∈ X}.
The tree of A∗ has root ε, vertex set A∗, and edge set {(w,wa) : w ∈ A∗, a ∈ A}.
A subtree of the tree of A∗ has as root any string r ∈ A∗, and as vertex set any subset V ⊆ rA∗,
such that the following holds for all v ∈ V and u ∈ A∗: r ≤pref u ≤pref v implies u ∈ V .
The following is a slight generalization of the classical notion of a prefix tree.
Definition (Prefix tree). Let Z ⊆ A∗, and let q ∈ A∗. The prefix tree T (q, Z) is the subtree of the
tree of A∗ with root q and vertex set Vq,Z = {v ∈ A∗ : q ≤pref v, and v ≤pref z for some z ∈ Z}.
Remark. Let L be the set of leaves of T (q, Z); then L and q−1L are prefix codes.
Definition (Saturated tree). A subtree T of the tree of A∗ is saturated iff for every vertex v of T
we have: v has no child in T (i.e., v is a leaf), or v has |A| children in T .
Definition (Tree saturation). Let T be a subtree of the tree of A∗, with root q, set of vertices V ,
and set of leaves L. The saturation of T is the smallest (under inclusion) saturated subtree of the tree
of A∗ with root q, that contains T . In other words, if T is just {q}, it is its own saturation; otherwise
the saturation has root q and has vertex set V ∪ (V − L) ·A. We denote the saturation of T by sT .
Remark. (1) The prefix tree T (q, Z) and its saturation have the same depth (i.e., length of a longest
path from the root). Every leaf of T (q, Z) is also a leaf of sT (q, Z), but unless T (q, Z) is already
saturated, sT (q, Z) has more leaves than T (q, Z). The non-leaf vertices of T (q, Z) and sT (q, Z) are
the same.
(2) The number of leaves in the saturated tree sT (q, Z) is < |Vq,Z | · |A|.
(3) Let L be the leaf set of the saturated tree sT (q, Z); if Z is finite then q−1L is a maximal prefix
code.
Theorem 4.5B (Equivalent normal morphism). For every right-ideal morphism ϕ with finite
domain code there exists a normal right-ideal morphism ϕ0 with finite domain code, such that ϕ = ϕ0
in Mk,1. Moreover,
|imC(ϕ0)| = |ϕ0(domC(ϕ0))| ≤ |A| · (ℓ(ϕ(P )) + 1) · |ϕ(P )|,
|domC(ϕ0)| ≤ |P | · |A| · (ℓ(ϕ(P )) + 1) · |ϕ(P )|,
ℓ(imC(ϕ0)) = ℓ(ϕ0(domC(ϕ0))) = ℓ(ϕ(domC(ϕ))),
ℓ(domC(ϕ0)) ≤ ℓ(domC(ϕ)) + ℓ(ϕ(domC(ϕ))).
Proof. Let P = domC(ϕ), Q = imC(ϕ), P0 = domC(ϕ0), Q0 = imC(ϕ0). For each p ∈ P , let
ϕ(p)Wϕ(p) be the the set of leaves of the saturated tree sT
ϕ(p), ϕ(P ) ∩ ϕ(p)A∗
. By Remark (3)
above, Wϕ(p) is a finite maximal prefix code. Now we define ϕ0 as follows:
ϕ0 is the restriction of ϕ to
p∈P pWϕ(p)A
Let us verify that ϕ0 has the required properties. Since P andWϕ(p) are finite prefix codes,
p∈P pWϕ(p)
is a finite prefix code. So,
domC(ϕ0) =
p∈P pWϕ(p).
Since each Wϕ(p) is a maximal prefix code, the right ideal
p∈P pWϕ(p)A
∗ is essential in the right
ideal PA∗; hence ϕ and ϕ0 are equal as elements of Mk,1. Finally, let us show that ϕ0(domC(ϕ0)) is
a prefix code. We have
ϕ0(domC(ϕ0)) =
p∈P ϕ(p) Wϕ(p),
which is the set of leaves of the union of the saturated prefix trees sT
ϕ(p), ϕ(P ) ∩ ϕ(p)A∗
, for p
ranging over P . For each p ∈ P , the leaves of sT
ϕ(p), ϕ(P )∩ϕ(p)A∗
form the prefix code ϕ(p)Wϕ(p).
For p1 6= p2 in P , if ϕ(p1) is a prefix of ϕ(p2) then the leaves of sT
ϕ(p2), ϕ(P ) ∩ ϕ(p2)A∗
are a
subset of the leaves of sT
ϕ(p1), ϕ(P ) ∩ ϕ(p1)A∗
, so the union of these two leaf sets is just the
leaf set of sT
ϕ(p1), ϕ(P ) ∩ ϕ(p1)A∗
; a similar thing happens if ϕ(p2) is a prefix of ϕ(p1). So in
p∈P ϕ(p) Wϕ(p) we can ignore elements p of P for which ϕ(p) is a strict prefix of another element of
ϕ(P ). If ϕ(p1) and ϕ(p2) are not prefix-comparable, then the leaves of sT
ϕ(pi), ϕ(P )∩ϕ(pi)A∗
ϕ(pi) as a prefix, so these two trees have leaf sets that are two-by-two prefix-incomparable (namely the
sets ϕ(p1)Wϕ(p1) and ϕ(p2)Wϕ(p2)). The union of prefix codes that are two-by-two prefix-incomparable
forms a prefix code; hence,
p∈P ϕ(p) Wϕ(p) is a prefix code.
Now, since ϕ0(domC(ϕ0)) is a prefix code it follows that imC(ϕ0) = ϕ0(domC(ϕ0)), so ϕ0 is
normal. This proves the first part of the theorem.
Let us prove the formulas. We saw that imC(ϕ0) = ϕ0(domC(ϕ0)) =
p∈P ϕ(p) Wϕ(p), and
ϕ(p) Wϕ(p) is the leaf set of the saturated tree sT
ϕ(p), ϕ(P ) ∩ ϕ(p)A∗
. By the definition of prefix
trees, the vertices of all the (non-saturated) trees T
ϕ(p), ϕ(P ) ∩ ϕ(p)A∗
are subsets of pref(ϕ(P )).
By Remark (2) above, the number of leaves in a saturated tree sT
ϕ(p), ϕ(P )∩ϕ(p)A∗
is at most |A|
times the number of vertices of the non-saturated tree. Hence, |imC(ϕ0)| ≤ |A|·|pref(ϕ(P ))|. Moreover,
for any finite Z ⊂ A∗, |pref(Z)| ≤ (1 + ℓ(Z)) · |Z|, hence, |imC(ϕ0)| ≤ |A| · (ℓ(ϕ(P )) + 1) · |ϕ(P )|.
We have domC(ϕ0) =
p∈P pWϕ(p), and ϕ(p)Wϕ(p) is the leaf set of sT
ϕ(p), ϕ(P ) ∩ ϕ(p)A∗
Hence by the same reasoning as for |imC(ϕ0)|: |Wϕ(p)| = |ϕ(p)Wϕ(p)| ≤ |A| · (ℓ(ϕ(P )) + 1) · |ϕ(P )|.
Hence, |domC(ϕ0)| ≤
p∈P |Wϕ(p)| ≤
p∈P |A|·(ℓ(ϕ(P ))+1)·|ϕ(P )| ≤ |P |·|A|·(ℓ(ϕ(P ))+1)·|ϕ(P )|.
We have imC(ϕ0) =
p∈P ϕ(p)Wϕ(p), and ϕ(p)Wϕ(p) is the leaf set of sT
ϕ(p), ϕ(P ) ∩ ϕ(p)A∗
Hence, ℓ(imC(ϕ0)) ≤ ℓ(ϕ(P )); indeed, tree saturation does not increase the depth of a tree, and the
depth of T
ϕ(p), ϕ(P ) ∩ ϕ(p)A∗
is ≤ ℓ(ϕ(P )).
We have domC(ϕ0) =
p∈P pWϕ(p). And ℓ(Wϕ(p)) ≤ ℓ(ϕ(p)Wϕ(p)) ≤ ℓ(ϕ(P )), since ϕ(p)Wϕ(p)
is the leaf set of sT
ϕ(p), ϕ(P ) ∩ ϕ(p)A∗
. Hence, for every x ∈ domC(ϕ0) we have x ∈ pWϕ(p) for
some p ∈ P , so |x| ≤ |p|+ ℓ(Wϕ(p)). Therefore, ℓ(domC(ϕ0)) ≤ ℓ(P ) + ℓ(ϕ(P )). ✷
Theorem 4.5B tells us that as far as Mk,1 is concerned, all right-ideal morphisms are normal.
Corollary 4.5C (Image code formula).
Let ϕi be a right-ideal morphism (for i = 1, . . . , n), and let Φ = ϕn ◦ . . . ◦ ϕ1.
(1) If ϕi is normal for 2 ≤ i ≤ n, then
|imC(Φ)| ≤
i=1 |imC(ϕi)| .
(2) If all ϕi are normal (for 1 ≤ i ≤ n), then
ℓ(domC(Φ) ∪ imC(Φ)) ≤
i=1 ℓ(domC(ϕi) ∪ imC(ϕi)) .
Proof. (1) follows immediately from Theorem 4.5(1), and (2) follows from 4.5(2) and 4.5(4). ✷
Counter-examples:
(1) The following shows that the image code formula of Corollary 4.5C(1) is wrong in some examples
when ϕ2 is not normal (but ϕ1 is normal). Let A = {0, 1}, n ≥ 2, and
ϕ1 = {(01, 00), (00, 01), (10, 1011), (11, 1100)}, and
ϕ2 = {(00u0, 000u1) : u ∈ {0, 1}n−1} ∪ {(01v0, 001v1) : v ∈ {0, 1}n−1} ∪ {(10, 000), (11, 001)}.
So, imC(ϕ1) = {00, 01, 1011, 1100}, and imC(ϕ2) = {000, 001}, hence |imC(ϕ1)|+ |imC(ϕ2)| = 6. Note
that the right-ideal morphisms ϕ1 and ϕ2 are in maximally extended form.
6 The concept of normal morphism and Theorem 4.5 enable us to rehabilitate the image code formula (which was
incorrect as stated in Theorem 4.5 of [1], but which is correct when one adds the hypothesis that the morphisms ϕi are
normal).
Now, ϕ2 ◦ϕ1 : 01u0 7→ 00u0 7→ 000u1 and ϕ2 ◦ϕ1 : 00v0 7→ 01v0 7→ 001v1, for all u, v ∈ {0, 1}n−1;
and ϕ2 ◦ ϕ1 : 10 7→ 1011 7→ 00011, ϕ2 ◦ ϕ1 : 11 7→ 1100 7→ 00100. Note that ϕ2 ◦ ϕ1 is in maximally
extended form.
Then imC(ϕ2 ◦ϕ1) = {00011, 00100} ∪ 000 {00, 01, 11} {0, 1}n−2 ∪ 001 {00, 01, 11} {0, 1}n−2 . Thus
when n ≥ 2: 2 + 6 · 2n−2 = |imC(ϕ2 ◦ ϕ1)| 6≤ |imC(ϕ1)|+ |imC(ϕ2)| = 6. ✷
(2) The following shows that the formula of Corollary 4.5C(2) is wrong in some examples when ϕ2 is
not normal (but ϕ1 is normal). We abbreviate ℓ(domC(ϕ) ∪ imC(ϕ)) by ℓ(ϕ). Let A = {0, 1}, n ≥ 2,
ϕ1 = {(0, 0n)}, and
ϕ2 = {(0, 0n+1), (1, 0)}.
So, ℓ(ϕ1) = n, and ℓ(ϕ2) = 1 since imC(ϕ2) = {0}. Now, ϕ2 ◦ ϕ1 = {(0, 02n)}. Thus when n ≥ 2:
2n = ℓ(ϕ2 ◦ ϕ1) 6≤ ℓ(ϕ2) + ℓ(ϕ1) = n+ 1. ✷
For elements of Invk,1 the image code has the same size as the domain code, which is also the table
size. Moreover, injective right-ideal morphisms are normal, thus Corollary 4.5C implies:
Corollary 4.6 For all injective right-ideal morphisms ϕ,ψ: ‖ψ ◦ ϕ‖ ≤ ‖ψ‖+ ‖ϕ‖. ✷
In other words, the table size formula holds for Invk,1. Another immediate consequence of Theorem
4.5 is the following.
Corollary 4.7 Let ϕi be normal right-ideal morphisms for i = 1, . . . , n, and let c1, c2 be positive
constants.
(1) If |imC(ϕi)| ≤ c1 for all i then |imC(ϕn ◦ . . . ◦ ϕ1)| ≤ c1 n.
(2) If ℓ(imC(ϕi)) ≤ c2 for all i then ℓ(imC(ϕn ◦ . . . ◦ ϕ1)) ≤ c2 n. ✷
The position transposition τi,j (with 0 < i < j) is, by definition, the partial permutation of A
which transposes the letters at positions i and j; τi,j is undefined on words of length < j. More
precisely, we have domC(τi,j) = imC(τi,j) = A
j, and uαvβ 7→ uβvα for all letters α, β ∈ A and all
words u ∈ Ai−1 and v ∈ Aj−i−1. In this form, τi,j is equal to its maximum essential extension.
Corollary 4.8 The word-length of τi,j over any finite generating set of Mk,1 is exponential.
Proof. We have |imC(τi,j)| = kj . The Corollary follows then from Corollary 4.7(1). ✷
4.2 Some algorithmic problems about right-ideal morphisms
We consider several problems about right-ideal morphisms of A∗ and show that they have deterministic
polynomial-time algorithms. We also show that the word problem of Mk,1 over Γk,1∪ {τi,i+1 : 0 < i}
is coNP-complete, where Γk,1 is any finite generating set of Mk,1. We saw that Γk,1 can be chosen so
as to consist of normal right-ideal morphisms.
Lemma 4.9 There are deterministic polynomial time algorithms for the following problems.
Input: Two finite prefix codes P1, P2 ⊂ A∗, given explicitly by lists of words.
Output 1: The finite prefix code Π ⊂ A∗ such that ΠA∗ = P1A∗ ∩P2A∗, where Π is produced explicitly
as a list of words.
Question 2: Is P1A
∗ ∩ P2A∗ essential in P1A∗ (or in P2A∗, or in both)?
Proof. We saw already that Π exists and Π ⊆ P1 ∪ P2; see Lemma 3.3 of [4] (quoted before Lemma
4.3 above).
Algorithm for Output 1: Since Π ⊆ P1 ∪ P2, we just need to search for the elements of Π within
P1 ∪ P2. For each x ∈ P1 we check whether x also belongs to P2A∗ (by checking whether any element
of P2 is a prefix of x). Since P1 and P2 are explicitly given as lists, this takes polynomial time.
Similarly, for each x ∈ P2 we check whether x also belongs to P1A∗. Thus, we have computed the set
Π1 = (P1 ∩ P2A∗) ∪ (P2 ∩ P1A∗). Now, Π is obtained from Π1 by eliminating every word that has
another word of Π1 as a prefix. Since Π1 is explicitly listed, this takes just polynomial time.
Algorithm for Question 2: We first compute Π by the previous algorithm. Next, we check whether
every p1 ∈ P1 is a prefix of some r ∈ Π; since P1 and Π are given by explicit lists, this takes just
polynomial time. For P2 it is similar. ✷
Lemma 4.10 The following input-output problem has a deterministic polynomial-time algorithm.
• Input: A finite set S ⊂ A∗, and m right-ideal morphisms ψj for j = 1, . . . ,m, where S is given by
an explicit list of words, and each ψj is given explicitly by the list of pairs of words {(x, ψj(x)) : x ∈
domC(ψj)}.
• Output: The finite set ψm . . . ψ1(S), given explicitly by a list of words.
Proof. Let Ψ = ψm ◦ . . . ◦ψ1 ◦ idS. Then ψm . . . ψ1(S) = Ψ(domC(Ψ)). By Theorem 4.5(3) and (5),
ℓ(Ψ(domC(Ψ))) ≤ ℓ(S)+
i=1 ℓ(ψi(domC(ψi))) and |Ψ(domC(Ψ))| ≤ |S|+
i=1 |ψi(domC(ψi))|. So
the size of ψm . . . ψ1(S), in terms of the number of words and their lengths, is polynomially bounded
by the size of the input.
We now compute ψm . . . ψ1(S) by applying ψj to ψj−1 . . . ψ1(S) for increasing j. Since the sizes of
the sets remain polynomially bounded, this algorithm takes polynomial time. ✷
Corollary 4.11 The following input-output problems have deterministic polynomial-time algorithms.
• Input: A list of n right-ideal morphisms ϕi for i = 1, . . . , n, given explicitly by finite tables.
• Output 1: A finite set, as an explicit list of words, that contains ϕn . . . ϕ1(domC(ϕn . . . ϕ1)).
• Output 2: The finite set imC(ϕn . . . ϕ1), as an explicit list of words.
Proof. (1) By Theorem 4.5(5) we have ϕn . . . ϕ1(domC(ϕn . . . ϕ1)) ⊆
i=1 ϕn . . . ϕi(domC(ϕi)). By
Lemma 4.10, each set ϕn . . . ϕi(domC(ϕi)), as well as their union, is computable in polynomial time
(as an explicit list of words).
(2) Let Φ = ϕn . . . ϕ1, Pi = domC(ϕi), and Qi = imC(ϕi). As in the proof of Theorem 4.5(1),
Dom(ϕ2 ◦ ϕ1) = ϕ−11 (Q1A∗ ∩ P2A∗), Im(ϕ2 ◦ ϕ1) = ϕ2(Q1A∗ ∩ P2A∗), and the maps ϕ
1 (Q1A
ϕ1−→ Q1A∗ ∩P2A∗
ϕ2−→ ϕ2(Q1A∗∩P2A∗) are total and onto. By Lemma 3.3 of [4] (mentioned
before Theorem 4.5) we have Q1A
∗ ∩ P2A∗ = S1A∗ for some finite prefix code S1 with S1 ⊆ Q1 ∪ P2.
Moreover, by Lemma 4.3, ϕ2(S1A
∗) = R2A
∗, where imC(ϕ2ϕ1) = R2 ⊆ ϕ2(S1).
By induction, for j ≥ 2 suppose imC(ϕj . . . ϕ1) = Rj ⊆ ϕj(Sj−1), where Rj and Sj−1 are finite
prefix codes such that Sj−1 ⊆ Rj−1 ∪ Pj , Sj−1A∗ = Rj−1A∗ ∩ PjA∗, RjA∗ = Im(ϕj . . . ϕ1) =
ϕj(Sj−1A
∗), and the maps ϕ−1j (RjA
∗ ∩Pj+1A∗)
ϕj−→ RjA∗ ∩Pj+1A∗
ϕj+1−→ ϕj+1(RjA∗ ∩Pj+1A∗) are
total and onto. Then by Lemma 3.3 of [4] we again have RjA
∗ ∩Pj+1A∗ = SjA∗ for some finite prefix
code Sj with Sj ⊆ Rj∪Pj+1; and by Lemma 4.3, ϕj+1(SjA∗) = Rj+1A∗ for some finite prefix code Rj+1
such that imC(ϕj+1ϕj . . . ϕ1) = Rj+1 ⊆ ϕj+1(Sj). Applying Theorem 4.5 to Ri = imC(ϕi . . . ϕ1) for
any i ≥ 2 we have
|Ri| ≤ |ϕi(Pi)|+ . . . + |ϕ2(P2)|+ |imC(ϕ1)|, and
ℓ(Ri) ≤ ℓ(ϕi(Pi)) + . . . + ℓ(ϕ2(P2)) + ℓ(imC(ϕ1)).
Since Sj ⊆ Pj ∪Rj−1, we have |Sj | ≤ |Pj |+ |Rj−1| ≤ |Pj |+ |ϕj−1(Pj−1)|+ . . . + |ϕ2(P2)|+ |imC(ϕ1)|,
and ℓ(Sj) ≤ ℓ(Pj)+ ℓ(Rj−1) ≤ ℓ(Pj)+ ℓ(ϕj−1(Pj−1))+ . . . + ℓ(ϕ2(P2))+ ℓ(imC(ϕ1)). Thus, the size
of each Ri and Sj is less than the input size; by input size we mean the total length of all the words
in the input lists.
By Lemma 4.9, the prefix code Sj is computed from Rj and Pj+1, as an explicit list, in time
≤ Tj(|Pj |+ ℓ(Pj) + |Rj−1|+ ℓ(Rj−1)), for some polynomial Tj(.). And Rj+1 is computed from Sj by
applying ϕj+1 to Sj, and then keeping the elements that do not have a prefix in ϕj+1(Sj). Computing
ϕj+1(Sj) takes at most quadratic time, and finding the prefix code in ϕj+1(Sj) also takes at most
quadratic time.
In the end we obtain Rn = imC(ϕn . . . ϕ1) as an explicit list of words. ✷
When we consider the word problem of Mk,1 over a finite generating set, we measure the input
size by the length of input word (with each generator having length 1). But for the word problem
of Mk,1 over the infinite generating set Γk,1 ∪ {τi−1,i : i > 1} we count the length of the position
transpositions τi−1,i as i, in the definition of the input size of the word problem. Indeed, at least log2 i
bits are needed to describe the subscript i of τi−1,i. Moreover, in the connection between Mk,1 (over
Γk,1∪{τi−1,i : i > 1}) and circuits, τi−1,i is interpreted as the wire-crossing operation of wire number i
and wire number i− 1; this suggests that viewing the size of τi−1,i as i is more natural than log2 i. In
any case, we will see next that the word problem of Mk,1 over Γk,1 ∪ {τi−1,i : i > 1} is coNP-complete,
even if the size of τi−1,i is more generously measured as i; this is a stronger result than if log2 i were
used.
Theorem 4.12 (coNP-complete word problem). The word problem of Mk,1 over the infinite
generating set Γk,1 ∪ {τi−1,i : i > 1} is coNP-complete, where Γk,1 is any finite generating set of Mk,1.
Proof. In [5] (see also [3]) it was shown that the word problem of the Thompson-Higman group Gk,1
over ΓGk,1 ∪ {τi−1,i : i > 1} is coNP-complete, where ΓGk,1 is any finite generating set of Gk,1. Hence,
since the elements of the finite set ΓGk,1 can be expressed by a finite set of words over Γk,1, it follows
that the word problem of Mk,1 over Γk,1 ∪ {τi−1,i : i > 1} is coNP-hard.
We will prove now that the word problem of Mk,1 over Γk,1 ∪ {τi−1,i : i > 1} belongs to coNP. The
input of the problem consists of two words (ρm, . . . , ρ1) and (σn, . . . , σ1) over Γk,1 ∪ {τi−1,i : i > 1}.
The input size is the weighted length of the words (ρm, . . . , ρ1) and (σn, . . . , σ1), where each generator
in Γk,1 has weight 1, and each generator of the form τi−1,i has weight i. For every right-ideal morphism
ϕ we abbreviate ℓ(domC(ϕ) ∪ϕ(domC(ϕ))) by ℓ(ϕ); recall that for a finite set X ⊂ A∗, ℓ(X) denotes
the length of a longest word in X.
Since Γk,1 is finite there is a constant c > 0 such that c ≥ ℓ(γ) for all γ ∈ Γk,1; also, for each τi−1,i
we have ℓ(τi−1,i) = i. By Theorem 4.5, the table of σn ◦ . . . ◦ σ1 (and more generally, the table of
σj ◦ . . . ◦ σ1 for any j with n ≥ j ≥ 1) contains only words of length ≤
j=1 ℓ(σj), and similarly for
ρm ◦ . . . ◦ρ1 (and for ρi ◦ . . . ◦ρ1, m ≥ i ≥ 1). So all the words in the tables for any σj ◦ . . . ◦σ1 and any
ρi ◦ . . . ◦ρ1 have lengths that are linearly bounded by the size of the input
(ρm, . . . , ρ1), (σn, . . . , σ1)
Claim. Let N = max{
i=1 ℓ(ρi),
j=1 ℓ(σj)}. Then ρm · . . . · ρ1 6= σn · . . . · σ1 in Mk,1 iff there
exists x ∈ AN such that ρm ◦ . . . ◦ ρ1(x) 6= σn ◦ . . . ◦ σ1(x).
Proof of the Claim: As we saw above, the tables of ρm ◦ . . . ◦ ρ1 and σn ◦ . . . ◦ σ1 only contain words of
length ≤ N . Thus, restricting ρm ◦ . . . ◦ ρ1 and σn ◦ . . . ◦ σ1 to ANA∗ is an essential restriction, and
the resulting tables have domain codes in AN . Therefore, ρm · . . . · ρ1 and σn · . . . · σ1 are equal (as
elements of Mk,1) iff ρm ◦ . . . ◦ ρ1 and σn ◦ . . . ◦ σ1 are equal on AN . [End, Proof of Claim]
The number N in the Claim is immediately obtained form the input. Based on the Claim, we
obtain a nondeterministic polynomial-time algorithm which decides (nondeterministically) whether
there exists x ∈ AN such that ρm ◦ . . . ◦ ρ1(x) 6= σn ◦ . . . ◦ σ1(x), as follows:
The algorithm guesses x ∈ AN , computes ρm ◦ . . . ◦ ρ1(x) and σn ◦ . . . ◦ σ1(x), and checks that
they are different words (∈ A∗) or that one is undefined and the other is a word. Applying Theorem
4.5 to ρm ◦ . . . ◦ ρ1 ◦ idAN and to σn ◦ . . . ◦ σ1 ◦ idAN shows that |ρm ◦ . . . ◦ ρ1(x)| ≤ 2N and
|σn ◦ . . . ◦ σ1(x)| ≤ 2N ; here |ρm ◦ . . . ◦ ρ1(x)| denotes the length of the word ρm ◦ . . . ◦ ρ1(x) ∈ A∗,
and similarly for σn ◦ . . . ◦ σ1(x). Also by Theorem 4.5, all intermediate results (as we successively
apply ρi for i = 1, . . . ,m, or σj for j = 1, . . . , n) are words of length ≤ 2N . These successive words
are computed by applying the table of ρi or σj (when ρi or σj belong to Γk,1), or by directly applying
the position permutation τh,h−1 (if ρi or σj is τh,h−1). Thus, the output ρm ◦ . . . ◦ ρ1(x) (and similarly,
σn ◦ . . . ◦ σ1(x)) can be computed in polynomial time. ✷
4.3 The word problem of Mk,1 is in P
We now move ahead with the the proof of our main result.
Theorem 4.13 (Word problem in P). The word problem of the Thompson-Higman monoids Mk,1,
over any finite generating set, can be decided in deterministic polynomial time.
We assume that a fixed finite generating set Γk,1 of Mk,1 has been chosen. The input consists of
two sequences (ρm, . . . , ρ1) and (σn, . . . , σ1) over Γk,1, and the input size is m+ n; since Γk,1 is finite
and fixed, it does not matter whether we choose m+ n as input size, or the sum of the lengths of all
the words in the tables of the elements of Γk,1. We want to decide in deterministic polynomial time
whether, as elements of Mk,1, the products ρm · . . . · ρ1 and σn · . . . · σ1 are equal.
Overview of the proof:
• We compute the finite sets imC(ρm ◦ . . . ◦ ρ1), imC(σn ◦ . . . ◦ σ1) ⊂ A∗, explicitly described by
lists of words. By Corollary 4.11 (Output 2) this can be done in polynomial time, and these sets have
polynomial size. (Note however that by Proposition 4.2, the table sizes of ρm ◦ . . . ◦ ρ1 or σn ◦ . . . ◦ σ1
could be exponential in m or n.)
• We check whether Im(ρm ◦ . . . ◦ ρ1) ∩ Im(σn ◦ . . . ◦ σ1) is essential in Im(ρm ◦ . . . ◦ ρ1) and in
Im(σn ◦ . . . ◦ σ1). By Lemma 4.9 (Question 2) this can be done in polynomial time. If the answer
is “no” then ρm · . . . · ρ1 6= σn · . . . · σ1 in Mk,1, since they don’t have a common maximum essential
extension. Otherwise, the computation continues.
• We compute the finite prefix code Π ⊂ A∗ such that ΠA∗ = Im(ρm ◦ . . . ◦ ρ1) ∩ Im(σn ◦ . . . ◦ σ1).
By Lemma 4.9 (Output 1) this can be done in polynomial time, and Π has polynomial size. Hence,
the table of idΠA∗ can be computed in polynomial time.
• We restrict ρm ◦ . . .◦ρ1 and σn ◦ . . . ◦σ1 in such a way that their images are in ΠA∗. In other words,
we replace them by ρ = idΠA∗ ◦ρm ◦ . . .◦ρ1, respectively σ = idΠA∗ ◦σn ◦ . . .◦σ1. Since ΠA∗ is essential
in Im(ρm ◦ . . . ◦ ρ1) and in Im(σn ◦ . . . ◦ σ1), we have ρ = ρm · . . . · ρ1 in Mk,1, and σ = σn · . . . · σ1 in
Mk,1. So, ρm · . . . · ρ1 = σn · . . . · σ1 in Mk,1 iff ρ = σ in Mk,1.
• We compute finite sets R1, R2 ⊂ A∗, such that ρ(domC(ρ)) ⊆ R1 and σ(domC(σ)) ⊆ R2. Since
ρ(domC(ρ)) ∪ σ(domC(σ)) ⊆ ΠA∗, we can pick R1, R2 so that R1 ∪ R2 ⊆ ΠA∗. By Corollary 4.11
(Output 1), the sets R1, R2 can be computed as explicit lists in polynomial time. Let R = R1 ∪R2.
• We note that ρ = σ in Mk,1 iff for all r ∈ ρ(domC(ρ)) ∪ σ(domC(σ)): ρ−1(r) = σ−1(r). This holds
iff for all r ∈ R: ρ−1(r) = σ−1(r).
• For every r ∈ R we construct a deterministic finite automaton (DFA) accepting the finite set
ρ−1(r) ⊂ A∗, and a DFA accepting the finite set σ−1(r) ⊂ A∗. By Corollary 4.15 this can be done in
polynomial time, and the DFAs have polynomial size. (The finite sets ρ−1(r) and σ−1(r) themselves
could have exponential size.) Note that domC(ρ) ⊆ ρ−1(ρ(domC(ρ))) ⊆ ρ−1(R), and similarly for σ.
Note that usually, domC(ρ) 6⊆ ρ−1(imC(ρ)) (since ρ is not normal in general), and similarly for σ; so
we need to use ρ(domC(ρ)), and not just imC(ρ).
• For every r ∈ R we check whether the DFA for ρ−1(r) and the DFA for σ−1(r) are equivalent. By
classical automata theory, equivalence of DFAs can be checked in polynomial time.
[End of Overview.]
Automata – notation and facts: In the following, DFA stands for deterministic finite automaton.
The language accepted by a DFA A is denoted by L(A). A DFA is a structure (S,A, δ, s0, F ) where
S is the set of states, A is the input alphabet, s0 ∈ S is the start state, F ⊆ S is the set of accept
states, and δ : S ×A→ S is the next-state function; in general, δ is a partial function (by “function”
we always mean partial function). We extend the definition of δ to a function S×A∗ → S by defining
δ(s,w) to be the state that the DFA reaches from s after reading w (for any w ∈ A∗ and s ∈ S). See
[21, 24] for background on finite automata. A DFA is called acyclic iff its underlying directed graph
has no directed cycle. It is easy to prove that a language L ⊆ A∗ is finite iff L is accepted by an
acyclic DFA. Moreover, L is a finite prefix code iff L is accepted by an acyclic DFA that has a single
accept state (take the prefix tree of the prefix code, with the leaves as accept states, then glue all the
leaves together into a single accept state). By the size of a DFA A we mean the number of states, |S|;
we denote this by size(A). For a finite set P ⊆ A∗ we denote the length of the longest words in P by
ℓ(P ), and we define the total length of P by Σ(P ) =
x∈P |x|; obviously, Σ(P ) ≤ |P | · ℓ(P ).
For a language L ⊆ A∗ and a partial function Φ : A∗ → A∗, we define the inverse image of L under
Φ by Φ−1(L) = {x ∈ A∗ : Φ(x) ∈ L}.
For L ⊆ A∗ we denote the set of all strict prefixes of the words in L by spref(L); precisely,
spref(L) = {x ∈ A∗ : (∃w ∈ L)[x ≤pref w and x 6= w ]}.
The reason why we use acyclic DFAs to describe finite sets is that a finite set can be exponentially
larger than the number of states of a DFA that accepts it; e.g., An is accepted by an acyclic DFA
with n+1 states. This conciseness plays a crucial role in our polynomial-time algorithm for the word
problem of Mk,1.
Lemma 4.14 Let A be an acyclic DFA with a single accept state. Let ϕ be a normal right-ideal
morphism, with domC(ϕ) 6= {ε} and imC(ϕ) 6= {ε}.
Then ϕ−1(L(A)) is accepted by a one-accept-state acyclic DFA ϕ−1(A) whose number of states is
size(ϕ−1(A)) < size(A) + Σ(domC(ϕ)). The transition table of the DFA ϕ−1(A) can be constructed
deterministically in polynomial time, based on the transition table of A and the table of ϕ.
Proof. If ϕ−1(L(A)) = ∅ then size(ϕ−1(A)) = 0, so the result is trivial. Let us assume now that
ϕ−1(L(A)) 6= ∅. Let A = (S,A, δ, s0, {sA}) where sA is the single accept state; sA has no out-going
edges (they would be useless). For any set X ⊆ A∗ and any state s ∈ S we denote {δ(s, x) : x ∈ X}
by δ(s,X). Let P = domC(ϕ) and Q = imC(ϕ). Since A is acyclic, its state set S can be partitioned
into δ(s0, spref(Q)) and δ(s0, QA
∗). Since Q 6= {ε}, the block δ(s0, spref(Q)) contains s0, so the block
is non-empty. The block δ(s0, QA
∗) is non-empty because of the assumption ϕ−1(L(A)) 6= ∅, which
implies L(A) ∩QA∗ 6= ∅.
Since L(A) is a prefix code and ϕ is a right-ideal morphism, ϕ−1(L(A)) is a prefix code. To accept
ϕ−1(L(A)) we define an acyclic DFA, called ϕ−1(A), as follows:
• State set of ϕ−1(A): spref(P ) ∪ δ(s0, QA∗);
start state: ε, i.e., the root of the prefix tree of P (since P 6= {ε}, ε ∈ spref(P ));
accept state: the accept state sA of A.
• State-transition function δ1 of ϕ−1(A):
For every r ∈ spref(P ) and a ∈ A such that ra ∈ spref(P ): δ1(r, a) = ra.
For every r ∈ spref(P ) and a ∈ A such that ra ∈ P : δ1(r, a) = δ(s0, ϕ(ra)).
For every s ∈ δ(s0, QA∗): δ1(s, a) = δ(s, a).
It follows immediately from this definition that for all p ∈ P : δ1(ε, p) = δ(s0, ϕ(p)). The construction
of ϕ−1(A) assumes that ϕ maps P onto Q, i.e., it uses the assumption that ϕ is normal. As usual,
“function” means partial function, so δ(., .) and δ1(., .) need not be defined on every state-letter pair.
The DFA ϕ−1(A) can be pictured as being constructed as follows: The DFA has two parts. The
first part is the prefix tree of P , but with the leaves left out (and with edges to leaves left dangling). The
second part is the DFA A restricted to the state subset δ(s0, QA∗). The two parts are glued together by
connecting any dangling edge, originally pointing to a leaf p ∈ P , to the state δ(s0, ϕ(p)) ∈ δ(s0, QA∗).
The description of ϕ−1(A) constitutes a deterministic polynomial time algorithm for constructing
the transition table of ϕ−1(A), based on the transition table of A and on the table of ϕ. By the
construction, the number of states of ϕ−1(A) is < size(A) + Σ(P ) We will prove now that the DFA
ϕ−1(A) accepts exactly ϕ−1(L(A)); i.e., ϕ−1(L(A)) = L(ϕ−1(A)).
[⊆] Consider any y ∈ L(A) such that ϕ−1(y) 6= ∅. We want to show that ϕ−1(A) accepts all the words
in ϕ−1(y). Since ϕ−1(y) 6= ∅ we have y ∈ Im(ϕ), hence y = qw for some strings q ∈ Q = imC(ϕ) and
w ∈ A∗. Since Q is a prefix code, q and w are uniquely determined by y. Moreover, since y ∈ L(A) it
follows that y has an accepting path in A of the form
q−→ δ(s0, q)
w−→ sA.
For every x ∈ ϕ−1(y) we have x ∈ Dom(ϕ) = PA∗, hence x = pv for some strings p ∈ P and v ∈ A∗.
So ϕ(x) = ϕ(p) v. We also have ϕ(x) = y = qw, hence ϕ(p) and q are prefix-comparable. Therefore,
ϕ(p) = q, since Q is a prefix code and since ϕ(p) ∈ Q (by normality of ϕ); hence v = w. Thus
every x ∈ ϕ−1(y) has the form pw for some string p ∈ ϕ−1(q). Now in ϕ−1(A) there is the following
accepting path on input x = pw ∈ ϕ−1(y):
p−→ δ1(ε, p) = δ(s0, ϕ(p))
w−→ sA.
Thus ϕ−1(A) accepts x = pw = pv.
[⊇] Suppose ϕ−1(A) accepts x. Then, because of the prefix tree of P at the beginning of ϕ−1(A), x
has the form x = pw for some strings p ∈ P and w ∈ A∗. The accepting path in ϕ−1(A) on input pw
has the form
p−→ δ1(ε, p) = δ(s0, ϕ(p))
w−→ sA.
Also, ϕ(x) = qw where q = ϕ(p) ∈ Q (here we use normality of ϕ). Hence A has the following
computation path on input qw:
q−→ δ(s0, q) = δ(s0, ϕ(p))
w−→ sA.
So, ϕ(x) = ϕ(p)w = qw ∈ L(A). Hence, x ∈ ϕ−1(qw) ⊆ ϕ−1(L(A)). Thus L(ϕ−1(A)) ⊆ ϕ−1(L(A)).
Corollary 4.15 Let A be an acyclic DFA with a single accept state. For i = 1, . . . , n, let Pi, Qi ⊂ A∗
be finite prefix codes, and let ϕi : PiA
∗ → QiA∗ be normal right-ideal morphisms. We assume that
Pi 6= {ε} and Qi 6= {ε}.
Then (ϕn ◦ . . .◦ϕ1)−1(L(A)) is accepted by an acyclic DFA with size < size(A)+
i=1 Σ(Pi), with
one accept state. The transition table of this DFA can be constructed deterministically in polynomial
time, based on the transition table of A and the tables of ϕi (for i = 1, . . . , n).
Proof. We assume that (ϕn ◦ . . . ◦ ϕ1)−1(L(A)) 6= ∅ (since the empty set is accepted by a DFA of
size 0). We use induction on n. For n = 1 the Corollary is just Lemma 4.14.
Let n ≥ 1, assume the Corollary holds for n normal morphisms, and consider one more normal right-
ideal morphism ϕ0 : P0A
∗ → Q0A∗, where P0, Q0 ⊂ A∗ are finite prefix codes with P0 6= {ε} 6= Q0.
And assume (ϕn ◦ . . . ◦ ϕ1 ◦ ϕ0)−1(L(A)) 6= ∅.
Since (ϕn ◦ . . . ◦ ϕ1◦ ϕ0)−1(L(A)) = ϕ−10 ◦ (ϕn ◦ . . . ◦ ϕ1)−1(L(A)), let us apply Lemma 4.14 to
ϕ0 and the acyclic DFA (ϕn ◦ . . . ◦ ϕ1)−1(A). We have ε 6∈ Dom(ϕn . . . ϕ1ϕ0); indeed, Pi 6= {ε}
is equivalent to ε 6∈ Dom(ϕi); moreover we have ε 6∈ Dom(ϕ0), and Dom(ϕn . . . ϕ1ϕ0) ⊆ Dom(ϕ0).
Similarly, Qi 6= {ε} is equivalent to ε 6∈ Im(ϕi); and ε 6∈ Im(ϕn) implies ε 6∈ Im(ϕn . . . ϕ1ϕ0).
The conclusion of Lemma 4.14 is then that (ϕn◦. . .◦ϕ1 ◦ ϕ0)−1(L(A)) is accepted by an acyclic DFA
(ϕn◦. . .◦ϕ1◦ϕ0)−1(A) whose size is < size((ϕn◦. . .◦ϕ1)−1(A)) + Σ(P0) < size(A)+
i=1 Σ(Pi)+Σ(P0)
= size(A) +
i=0Σ(Pi). ✷
Proof of Theorem 4.13:
Let (ρm, . . . , ρ1) and (σn, . . . , σ1) be two sequences of generators from the finite generating set Γk,1.
The elements of Γk,1 can be chosen so that the assumptions of Corollary 4.15 hold; see Section 3 of
[1], where such a generating set is given. We want to decide in deterministic polynomial time whether
the products ρm · . . . · ρ1 and σn · . . . · σ1 are the same, as elements of Mk,1.
First, by Corollary 4.11 (Output 2) we can compute the sets imC(ρm◦. . .◦ρ1) and imC(σn◦. . .◦σ1),
explicitly described by lists of words, in polynomial time. By Lemma 4.9 (Question 2) we can check in
polynomial time whether the right ideal Im(ρm◦. . .◦ρ1) ∩ Im(σn◦. . .◦σ1) is essential in Im(ρm◦. . .◦ρ1)
and in Im(σn ◦ . . . ◦ σ1). If it is not essential we immediately conclude that ρm · . . . · ρ1 6= σn · . . . · σ1.
On the other hand, if it is essential, Lemma 4.9 (Output 1) lets us compute a generating set Π for
the right ideal Im(ρm ◦ . . . ◦ ρ1) ∩ Im(σn ◦ . . . ◦ σ1), in deterministic polynomial time; the generating
set Π is a finite prefix code, given explicitly by a list of words. By Corollary 4.7 and because Π ⊆
imC(ρm ◦ . . .◦ρ1) ∪ imC(σn ◦ . . .◦σ1), Π has linearly bounded cardinality and the length of the longest
words in Π is linearly bounded in terms of n+m.
We restrict ρm ◦ . . . ◦ ρ1 and σn ◦ . . . ◦ σ1 in such a way that their images are ΠA∗; i.e., we replace
them by ρ = idΠA∗ ◦ ρm ◦ . . . ◦ ρ1, respectively σ = idΠA∗ ◦ σn ◦ . . . ◦ σ1. So, Im(ρ) = ΠA∗ = Im(σ).
Also, since ΠA∗ is essential in Im(ρm ◦ . . .◦ρ1) and in Im(σn ◦ . . .◦σ1) we have: ρ is equal to ρm · . . . ·ρ1
in Mk,1, and σ is equal to σn · . . . · σ1 in Mk,1. So for deciding the word problem it is enough to check
whether ρ = σ in Mk,1.
By the next Claim, the sets ρ(domC(ρ)) and σ(domC(σ)) play a crucial role. However, instead
of directly computing ρ(domC(ρ)) and σ(domC(σ)), we compute finite sets R1, R2 ⊂ A∗ such that
ρ(domC(ρ)) ⊆ R1 and σ(domC(σ)) ⊆ R2 . Moreover, since ρ(domC(ρ))∪σ(domC(σ)) ⊆ ΠA∗, we can
pick R1, R2 so that R1 ∪R2 ⊆ ΠA∗. By Corollary 4.11 (Output 1), the sets R1, R2 can be computed
in polynomial time as explicit lists of words. Let R = R1 ∪R2.
Claim. ρ = σ in Mk,1 iff ρ
−1(r) = σ−1(r) for every r ∈ ρ(domC(ρ)) ∪ σ(domC(σ)). The latter is
equivalent to ρ−1(r) = σ−1(r) for every r ∈ R.
Proof of the Claim. If ρ = σ in Mk,1 then ρ
−1(r) = σ−1(r) for every r ∈ ΠA∗ = Im(ρ) = Im(σ). Hence
this holds in particular for all r ∈ ρ(domC(ρ)) ∪ σ(domC(σ)) and for all r ∈ R, since ρ(domC(ρ)) ∪
σ(domC(σ)) ⊆ R ⊂ ΠA∗. Conversely, if ρ−1(r) = σ−1(r) for every r ∈ ρ(domC(ρ)) ∪ σ(domC(σ)),
then for all x ∈ ρ−1(r) = σ−1(r): ρ(x) = r = σ(x). Since domC(ρ) ⊆ ρ−1(ρ(domC(ρ))) and
domC(σ) ⊆ σ−1(σ(domC(σ))), it follows that ρ and σ are equal on domC(ρ) ∪ domC(σ), and it
follows that domC(ρ) = domC(σ). Hence ρ and σ are equal as right-ideal morphisms, and hence as
elements of Mk,1. [This proves the Claim.]
Recall that |R| and ℓ(R), and hence Σ(R), are polynomially bounded in terms of the input size. To
check for each r ∈ R whether ρ−1(r) = σ−1(r), we apply Corollary 4.15, which constructs an acyclic
DFA Aρ for ρ−1(r) from a DFA for {r}; this is done deterministically in polynomial time. Similarly,
an acyclic DFA Aσ for σ−1(r) is constructed. Thus, ρ−1(r) = σ−1(r) iff Aρ and Aσ accept the same
language.
Checking whether Aρ and Aσ accept the same language is an instance of the equivalence problem
for DFAs that are given explicitly by transition tables. It is well known (see e.g., [21], or [24] p. 103)
that the equivalence problem for DFAs is decidable deterministically in polynomial time. This proves
Theorem 4.13. ✷
Acknowledgement. I would like to thank John Meakin for many discussions over the years concern-
ing the Thompson groups and generalizations to inverse monoids.
References
[1] J.C. Birget, “Monoid generalizations of the Richard Thompson groups”, J. of Pure and Applied Algebra,
213(2) (Feb. 2009) 264-278. (Preprint: http://arxiv.org/abs/0704.0189, v1 April 2007, v2 April 2008.)
[2] J.C. Birget, “One-way permutations, computational asymmetry and distortion”, J. of Algebra 320(11)
(Dec. 2008) 4030-4062.
[3] J.C. Birget, “Factorizations of the Thompson-Higman groups, and circuit complexity”, International J. of
Algebra and Computation, 18.2 (March 2008) 285-320.
[4] J.C. Birget, “The groups of Richard Thompson and complexity”, International J. of Algebra and Compu-
tation 14(5,6) (Dec. 2004) 569-626.
[5] J.C. Birget, “Circuits, coNP-completeness, and the groups of Richard Thompson”, International J. of
Algebra and Computation, 16(1) (Feb. 2006) 35-90.
[6] J.C. Birget, “Bernoulli measure on strings, and Thompson-Higman monoids”, Semigroup Forum 83.1 (Aug.
2011) 1-32.
[7] J.C. Birget, “Polynomial-time right-ideal morphisms and congruences”.
Preprint: http://arxiv.org/abs/1511.02056 (Nov. 2015)
[8] M. Brin, C. Squier, “Groups of piecewise linear homeomorphisms of the real line”, Inventiones Mathemat-
icae 79 (1985) 485-498.
[9] M. Brin, “The Chameleon Groups of Richard J. Thompson: Automorphisms and Dynamics”, Publications
Math. de l’IHES 84 (1997) 5-33.
[10] K. Brown, R. Geoghegan, “An infinite-dimensional torsion-free FP∞ group”, Inventiones Mathematicae 77
(1984) 367-381.
[11] J. Burillo, S. Cleary, M. Stein, J. Taback, “Combinatorial and metric properties of Thompson’s group T ”,
Trans. Amer. Math. Soc. 361(2) (2009) 631-652. Preprint: http://arxiv.org/pdf/math/0503670
[12] J. W. Cannon, W. J. Floyd, W. R. Parry, “Introductory notes on Richard Thompson’s groups”,
L’Enseignement Mathématique 42 (1996) 215-256.
[13] A.H. Clifford, G.B. Preston, The Algebraic Theory of Semigroups, Vol. 1 (Mathematical Survey, No 7 (I))
American Mathematical Society, Providence (1961).
[14] J. Cuntz, “Simple C∗-algebras”, Communications in Mathematical Physics 57 (1977) 173-185.
[15] P. Dehornoy, “Geometric presentations for Thompson’s groups”, J. of Pure and Applied Algebra 203 (2005)
1-44.
[16] J. Dixmier, “Traces sur les C∗-algèbres II”, Bulletin des Sciences Mathématiques 88 (1964) 39-57.
[17] E. Ghys, V. Sergiescu, “Sur un groupe remarquable de difféomorphismes du cercle”, Commentarii Mathe-
matici Helvetici 62(2) (1987) 185-239.
[18] V. Guba, M.V. Sapir, “Diagram groups”, Memoirs American Math. Soc., 130 no. 620 (1997), viii+117
pages.
[19] P.A. Grillet, Semigroups, An Introduction to the Structure Theory, Marcel Dekker, New York (1995).
http://arxiv.org/abs/0704.0189
http://arxiv.org/abs/1511.02056
http://arxiv.org/pdf/math/0503670
[20] G. Higman, “Finitely presented infinite simple groups”, Notes on Pure Mathematics 8, The Australian
National University, Canberra (1974).
[21] J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley
(1979).
[22] B. Hughes, “Trees, Ultrametrics, and Noncommutative Geometry”,
http://arxiv.org/pdf/math/0605131v2.pdf
[23] M.V. Lawson, “Orthogonal completions of the polycyclic monoids”, Communications in Algebra, 35 (2007)
1651-1660.
[24] H. Lewis, Ch. Papadimitriou, Elements of the Theory of Computation, 2nd ed., Prentice Hall (1998).
[25] J. Lehnert, P. Schweitzer, “The co-word problem for the Higman-Thompson group is context-free”, Bulletin
of the London Mathematical Society, 39 (April 2007) 235-241.
[26] R. McKenzie, R. J. Thompson, “An elementary construction of unsolvable word problems in group theory”,
in Word Problems, (W. W. Boone, F. B. Cannonito, R. C. Lyndon, editors), North-Holland (1973) pp.
457-478.
[27] V.V. Nekrashevych, “Cuntz-Pimsner algebras of group actions”, J. Operator Theory 52(2) (2004) 223-249.
[28] Elizabeth A. Scott, “A construction which can be used to produce finitely presented infinite simple groups”,
J. of Algebra 90 (1984) 294-322.
[29] Richard J. Thompson, Manuscript (1960s).
[30] Richard J. Thompson, “Embeddings into finitely generated simple groups which preserve the word prob-
lem”, in Word Problems II, (S. Adian, W. Boone, G. Higman, editors), North-Holland (1980) pp. 401-441.
J.C. Birget
Dept. of Computer Science
Rutgers University – Camden
Camden, NJ 08102
birget@camden.rutgers.edu
http://arxiv.org/pdf/math/0605131v2.pdf
	1 Thompson-Higman monoids
	1.1 Definition of the Thompson-Higman groups and monoids
	1.2 Other Thompson-Higman monoids
	1.3 Cuntz algebras and Thompson-Higman monoids
	2 Structure and simplicity of the Thompson-Higman monoids
	2.1 Group of units, J-relation, simplicity
	2.2 D-relation
	3 Finite generating sets
	4 The word problem of the Thompson-Higman monoids
	4.1 The image code formula
	4.2 Some algorithmic problems about right-ideal morphisms
	4.3 The word problem of Mk,1 is in P
