The R- and L-orders of the thompson-higman monoid M_k,1 and their complexity

We study the monoid generalization M_{k, 1} of the ThompsonHigman 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 Π₂ ^P-complete, whereas the L-order decision problem is coNP-complete. Similarly, for acyclic circuits the surjectiveness problem is Π₂^P-complete, whereas the injectiveness problem is coNP-complete.