Abstract
The groups
G
k
,
1
of Richard Thompson and Graham Higman can be generalized in a natural way to monoids, that we call
M
k
,
1
, and to inverse monoids, called
Inv
k
,
1
; this is done by simply generalizing bijections to partial functions or partial injective functions. The monoids
M
k
,
1
have connections with circuit complexity (studied in other papers). Here we prove that
M
k
,
1
and
Inv
k
,
1
are congruence-simple for all
k
. Their Green relations
J
and
D
are characterized:
M
k
,
1
and
Inv
k
,
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
O
k
. 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.