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

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)489-524
Number of pages36
JournalInternational Journal of Algebra and Computation
Volume20
Issue number4
DOIs
StatePublished - Jun 2010

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Green relations
  • ThompsonHigman monoids
  • complexity

Fingerprint

Dive into the research topics of 'The R- and L-orders of the thompson-higman monoid M<sub>k,1</sub> and their complexity'. Together they form a unique fingerprint.

Cite this