The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity
| dc.creator | Birget, Jean-Camille | |
| dc.date | 2008-12-23 | |
| dc.date.accessioned | 2026-07-07T12:21:37Z | |
| dc.date.available | 2026-07-07T12:21:37Z | |
| dc.description | 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. | |
| dc.description | 36 pages | |
| dc.identifier | https://arxiv.org/abs/0812.4434 | |
| dc.identifier | http://arxiv.org/abs/0812.4434 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/213393 | |
| dc.subject | Group Theory | |
| dc.subject | 20F10, 20F05, 20M05, 68Q17 | |
| dc.title | The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity | |
| dc.type | text |