THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY

DOI10.1142/S0218196704001980zbMath1088.20016arXivmath/0204292OpenAlexW2071283394MaRDI QIDQ4658702

Jean-Camille Birget

Publication date: 18 March 2005

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

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

zbMATH Keywords

word problemdistortionsinfinite simple groupscomplexitiesDehn functionsThompson groupsCuntz algebrasfinitely presented simple groupsword-lengths

Mathematics Subject Classification ID

Selfadjoint operator algebras ((C^*)-algebras, von Neumann ((W^*)-) algebras, etc.) (46L99) Simple groups (20E32) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Orthogonal Completions of the Polycyclic Monoids ⋮ Subgroups of the group of homeomorphisms of the Cantor space and a duality between a class of inverse monoids and a class of Hausdorff étale groupoids ⋮ Higher dimensional generalizations of the Thompson groups ⋮ Compact presentability of tree almost automorphism groups ⋮ The action of the Thompson group \(F\) on infinite trees ⋮ Conjugator length in Thompson's groups ⋮ New embeddings between the Higman-Thompson groups ⋮ FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY ⋮ UNDECIDABILITY AND THE DEVELOPABILITY OF PERMUTOIDS AND RIGID PSEUDOGROUPS ⋮ Pseudogroups and their étale groupoids. ⋮ THE THOMPSON–HIGMAN MONOIDS M_k,i: THE ${\mathcal J}$-ORDER, THE ${\mathcal D}$-RELATION, AND THEIR COMPLEXITY ⋮ Partial category actions on sets and topological spaces ⋮ NON-COMMUTATIVE STONE DUALITY: INVERSE SEMIGROUPS, TOPOLOGICAL GROUPOIDS AND C*-ALGEBRAS ⋮ Monoid generalizations of the Richard Thompson groups. ⋮ One-way permutations, computational asymmetry and distortion. ⋮ Recent developments around partial actions ⋮ THE ${\mathcal R}$- AND ${\mathcal L}$-ORDERS OF THE THOMPSON–HIGMAN MONOID M_{k, 1} AND THEIR COMPLEXITY ⋮ Infinitely generated semigroups and polynomial complexity ⋮ The Polycyclic MonoidsP_nand the Thompson GroupsV_n,1 ⋮ Polynomial-time right-ideal morphisms and congruences ⋮ A dynamical definition of f.g. virtually free groups ⋮ Embeddings into Thompson's groups from quasi-median geometry ⋮ The universal Boolean inverse semigroup presented by the abstract Cuntz-Krieger relations ⋮ The Booleanization of an inverse semigroup ⋮ CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS ⋮ The word problem of the Brin-Thompson group is \textsf{coNP}-complete ⋮ Divergence functions of Thompson groups ⋮ Monoids that map onto the Thompson-Higman groups ⋮ Bernoulli measure on strings, and Thompson-Higman monoids. ⋮ Representations of Higman-Thompson groups from Cuntz algebras ⋮ Semigroups and one-way functions ⋮ A CORRESPONDENCE BETWEEN BALANCED VARIETIES AND INVERSE MONOIDS ⋮ The Polycyclic Inverse Monoids and the Thompson Groups Revisited ⋮ Compression techniques in group theory

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
• A finitely presented simple group with unsolvable conjugacy problem
• The complexity of Grigorchuk groups with application to cryptography
• Simple \(C^*\)-algebras generated by isometries
• Constructing inverse semigroups from category actions
• An application of polycyclic monoids to rings
• Constructing finitely presented simple groups that contain Grigorchuk groups
• Isoperimetric and isodiametric functions of groups
• Isoperimetric functions of groups and computational complexity of the word problem
• Word Problems Solvable in Logspace
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS