THE ${\mathcal R}$- AND ${\mathcal L}$-ORDERS OF THE THOMPSON–HIGMAN MONOID Mk, 1 AND THEIR COMPLEXITY
| Autor: | Jean-Camille Birget |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Zdroj: | International Journal of Algebra and Computation. 20:489-524 |
| ISSN: | 1793-6500 0218-1967 |
| DOI: | 10.1142/s0218196710005741 |
| Popis: | We study the monoid generalization Mk, 1 of the Thompson–Higman groups, and we characterize the [Formula: see text]- and the [Formula: see text]-order of Mk, 1. Although Mk, 1 has only one nonzero [Formula: see text]-class and k-1 nonzero [Formula: see text]-classes, the [Formula: see text]- and the [Formula: see text]-order are complicated; in particular, [Formula: see text] is dense (even within an [Formula: see text]-class), and [Formula: see text] is dense (even within an [Formula: see text]-class). We study the computational complexity of the [Formula: see text]- and the [Formula: see text]-order. When inputs are given by words over a finite generating set of Mk, 1, the [Formula: see text]- and the [Formula: see text]-order decision problems are in P. However, over a "circuit-like" generating set the [Formula: see text]-order decision problem of Mk, 1 is [Formula: see text]-complete, whereas the [Formula: see text]-order decision problem is coNP-complete. Similarly, for acyclic circuits the surjectiveness problem is [Formula: see text]-complete, whereas the injectiveness problem is coNP-complete. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|