We study the monoid generalization Mk, 1 of the ThompsonHigman groups, and we characterize the R- and the L-order of Mk,1. Although Mk,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 Mk,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 Mk,1 is Π2 P-complete, whereas the L-order decision problem is coNP-complete. Similarly, for acyclic circuits the surjectiveness problem is Π2P-complete, whereas the injectiveness problem is coNP-complete.
All Science Journal Classification (ASJC) codes
- Green relations
- ThompsonHigman monoids