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

DOI10.1142/S0218196711006066zbMATH Open1239.20072arXiv0904.2479OpenAlexW2963708351MaRDI QIDQ2996837FDOQ2996837

Authors: J.-C. Birget 

Publication date: 3 May 2011

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0904.2479

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

zbMATH Keywords

computational complexitymaximal subgroupsdecision problemsGreen relationsinverse monoidsThompson-Higman groupsThompson-Higman monoids

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Generators, relations, and presentations of groups (20F05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) 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)

Cites Work

• Title not available (Why is that?)
• The complexity of computing the permanent
• Subtractive reductions and complete problems for counting complexity classes
• Title not available (Why is that?)
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• PP is as Hard as the Polynomial-Time Hierarchy
• Title not available (Why is that?)
• On the construction of parallel computers from various basis of Boolean functions
• On the power of parity polynomial time
• The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• A construction which can be used to produce finitely presented infinite simple groups
• Monoid generalizations of the Richard Thompson groups.
• One-way permutations, computational asymmetry and distortion.
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection

Cited In (11)

• A countable series of bisimple \(\mathcal H\)-trivial finitely presented congruence-free monoids.
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• A simple non-bisimple congruence-free finitely presented monoid.
• A countable family of finitely presented infinite congruence-free monoids
• A strong geometric hyperbolicity property for directed graphs and monoids.
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• Bernoulli measure on strings, and Thompson-Higman monoids.
• Monoids that map onto the Thompson-Higman groups
• Monoid generalizations of the Richard Thompson groups.
• 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

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)