The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity

Details The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity

2008-12-23

arxiv.org/abs/0812.4434v1

Mathematics

Group Theory

36 pages

Scientific paper

We study the monoid generalization M_{k,1} of the Thompson-Higman groups, and we characterize the R- and the L-preorder of M_{k,1}. Although M_{k,1} has only one non-zero J-class and k-1 non-zero D-classes, the R- and the L-preorder 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-preorder. When inputs are given by words over a finite generating set of M_{k,1}, the R- and the L-preorder decision problems are in P. The main result of the paper is that over a "circuit-like" generating set, the R-preorder decision problem of M_{k,1} is Pi_2^P-complete, whereas the L-preorder decision problem is coNP-complete. We also prove related results about circuits: For combinational circuits, the surjectiveness problem is Pi_2^P-complete, whereas the injectiveness problem is coNP-complete.

Affiliated with

Also associated with

No associations

Rating

The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-606394