THE THOMPSON–HIGMAN MONOIDS Mk,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY

DOI10.1142/S0218196711006066zbMath1239.20072arXiv0904.2479OpenAlexW2963708351MaRDI QIDQ2996837

Jean-Camille Birget

Publication date: 3 May 2011

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

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

zbMATH Keywords

computational complexitymaximal subgroupsdecision problemsinverse monoidsGreen relationsThompson-Higman groupsThompson-Higman monoids

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Free semigroups, generators and relations, word problems (20M05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Inverse semigroups (20M18)

Related Items

A countable series of bisimple \(\mathcal H\)-trivial finitely presented congruence-free monoids. ⋮ A strong geometric hyperbolicity property for directed graphs and monoids. ⋮ A countable family of finitely presented infinite congruence-free monoids ⋮ A simple non-bisimple congruence-free finitely presented monoid.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• 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.
• On the construction of parallel computers from various basis of Boolean functions
• Subtractive reductions and complete problems for counting complexity classes
• PP is as Hard as the Polynomial-Time Hierarchy
• 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
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• On the power of parity polynomial time