The Thompson-Higman monoids M_k,i: the J-order, the D-relation, and their complexity.
From MaRDI portal
Publication:2996837
computational complexitydecision problemsGreen relationsinverse monoidsmaximal subgroupsThompson-Higman groupsThompson-Higman monoids
Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Inverse semigroups (20M18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Abstract: The Thompson-Higman groups G_{k,i} have a natural generalization to monoids M_{k,i}, and inverse monoids Inv_{k,i}. We study some structural features of M_{k,i} and Inv_{k,i} and investigate the computational complexity of decision problems. The main interest of these monoids is their close connection with circuits and circuit complexity. The maximal subgroups of M_{k,1} are isomorphic to the groups G_{k,j} (1 leq j leq k-1); so we rediscover all the Thompson-Higman groups within M_{k,1}. The Green relations leq_J and equiv_D of M_{k,1} can be decided in deterministic polynomial time when the inputs are words over a finite generating set of M_{k,1}. When a circuit-like generating set is used for M_{k,1} then deciding leq_J is coDP-complete. The multiplier search problem for leq_J is xNPsearch-complete, whereas the multiplier search problems of leq_R and leq_L are not in xNPsearch unless NP = coNP. Deciding equiv_D for M_{k,1} when the inputs are words over a circuit-like generating set, is oplus_{k-1}.NP-complete. For Inv_{k,1} over a circuit-like generating set, deciding equiv_D is oplus_{k-1} P-complete.
Recommendations
- The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
- Monoid generalizations of the Richard Thompson groups.
- Inverse monoids: decidability and complexity of algebraic questions.
- FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
- The membership problem in aperiodic transformation monoids
Cites work
- A construction which can be used to produce finitely presented infinite simple groups
- CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
- FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
- scientific article; zbMATH DE number 47903 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 774488 (Why is no real title available?)
- Monoid generalizations of the Richard Thompson groups.
- On the construction of parallel computers from various basis of Boolean functions
- On the power of parity polynomial time
- One-way permutations, computational asymmetry and distortion.
- PP is as Hard as the Polynomial-Time Hierarchy
- Subtractive reductions and complete problems for counting complexity classes
- The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- The complexity of computing the permanent
- THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
Cited in
(11)- A simple non-bisimple congruence-free finitely presented monoid.
- A countable series of bisimple \(\mathcal H\)-trivial finitely presented congruence-free monoids.
- A countable family of finitely presented infinite congruence-free monoids
- FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
- The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
- Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
- CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
- A strong geometric hyperbolicity property for directed graphs and monoids.
- Monoids that map onto the Thompson-Higman groups
- Bernoulli measure on strings, and Thompson-Higman monoids.
- Monoid generalizations of the Richard Thompson groups.
This page was built for publication: The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2996837)
