## Abstract

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 Π_{2} ^{P}-complete, whereas the L-order decision problem is coNP-complete. Similarly, for acyclic circuits the surjectiveness problem is Π_{2}^{P}-complete, whereas the injectiveness problem is coNP-complete.

Original language | English (US) |
---|---|

Pages (from-to) | 489-524 |

Number of pages | 36 |

Journal | International Journal of Algebra and Computation |

Volume | 20 |

Issue number | 4 |

DOIs | |

State | Published - Jun 2010 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Keywords

- Green relations
- ThompsonHigman monoids
- complexity