THE ${\mathcal R}$- AND ${\mathcal L}$-ORDERS OF THE THOMPSON–HIGMAN MONOID Mk, 1 AND THEIR COMPLEXITY

DOI10.1142/S0218196710005741zbMath1206.20064arXiv0812.4434MaRDI QIDQ3580222

Jean-Camille Birget

Publication date: 11 August 2010

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

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

zbMATH Keywords

computational complexity; decision problems; Green relations; finite generating sets; Thompson-Higman monoids

Mathematics Subject Classification ID

20M05: Free semigroups, generators and relations, word problems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

A strong geometric hyperbolicity property for directed graphs and monoids., Monoids that map onto the Thompson-Higman groups, A countable series of bisimple \(\mathcal H\)-trivial finitely presented congruence-free monoids., THE THOMPSON–HIGMAN MONOIDS M_k,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY, ON THE CIRCUIT-SIZE OF INVERSES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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.
• Groups of piecewise linear homeomorphisms of the real line
• The Chameleon groups of Richard J. Thompson: Automorphisms and dynamics
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• The Ubiquity of Thompson's Group F in Groups of Piecewise Linear Homeomorphisms of the Unit Interval
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS