Abstract
We study the monoid generalization M(k,1) of the Thompson-Higman groups, and we characterize the R- and the L-order of M(k,1). Although M(k,1) has only one nonzero J-class and k-1 nonzero D-classes, the R- and the L-order are complicated; in particular, <R is dense (even within an L-class), and <L is dense (even within an R-class). We study the computational complexity of the R- and the L-order. When inputs are given by words over a finite generating set of M(k,1), the R- and the L-order decision problems are in P. However, over a 'circuit-like' generating set the R-order decision problem of M(k,1) is capital pi (2)(P)-complete, whereas the L-order decision problem is coNP-complete. Similarly, for acyclic circuits the surjectiveness problem is capital pi (2)(P)-complete, whereas the injectiveness problem is coNP-complete.