The Thompson-Higman monoids Mk,i: The J-order, the D-relation, and their complexity

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


The Thompson-Higman groups Gk,i have a natural generalization to monoids, called Mk,i, and inverse monoids, called Invk,i. We study some structural features of Mk,i and Invk,i and investigate the computational complexity of related decision problems. The main interest of these monoids is their close connection with circuits and circuit complexity. The maximal subgroups of Mk,1 and Invk,1 are isomorphic to the groups Gk,j (1 ≤ j ≤ k - 1); so we rediscover all the Thompson-Higman groups within Mk,1. Deciding the Green relations ≤J and ≡D of Mk,1, when the inputs are words over a finite generating set of Mk,1, is in P. When a circuit-like generating set is used for Mk,1 then deciding ≤ J is coDP-complete (where DP is the complexity class consisting of differences of sets in NP). The multiplier search problem for ≤ J is xNPsearch-complete, whereas the multiplier search problems of ≤ R and ≤ L are not in xNPsearch unless NP = coNP. The class of search problems xNPsearch is introduced as a slight generalization of NPsearch. Deciding ≡ D for Mk,1 when the inputs are words over a circuit-like generating set, is ⊕ k-1•NP-complete; for any h < 2, ⊕h•NP is a modular counting complexity class, whose verification problems are in NP. Related problems for partial circuits are the image size problem (which is # • NP-complete), and the image size modulo h problem (which is ⊕h•NP-complete). For Invk,1 over a circuit-like generating set, deciding ≡ D is ⊕k-1P-complete. It is interesting that the little known complexity classes coDP and ⊕k-1•NP play a central role in Mk,1.

Original languageEnglish (US)
Pages (from-to)1-34
Number of pages34
JournalInternational Journal of Algebra and Computation
Issue number1-2
StatePublished - Feb 2011

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


  • Green relations
  • Thompson-Higman monoids
  • complexity


Dive into the research topics of 'The Thompson-Higman monoids Mk,i: The J-order, the D-relation, and their complexity'. Together they form a unique fingerprint.

Cite this