  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 another paper). 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.
  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.
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.
