THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY

DOI10.1142/S0218196704001980MaRDI QIDQ4658702zbMATH OpenOpenAlexFDO

Authors J.-C. 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

Dehn functionsword problemThompson groupsdistortionsCuntz algebrascomplexitiesfinitely presented simple groupsinfinite simple groupsword-lengths

Mathematics Subject Classification ID

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) Selfadjoint operator algebras ((C^*)-algebras, von Neumann ((W^*)-) algebras, etc.) (46L99) Simple groups (20E32)

Abstract: We prove new results about the remarkable infinite simple groups introduced by Richard Thompson in the 1960s. We define the groups as partial transformation groups and we give a faithful representation in the Cuntz C*-algebra. For the finitely presented simple group T_fin (also known as V) we show that the word-length and the table size satisfy an n log n relation, just like the symmetric groups. We show that the word problem of T_fin belongs to the parallel complexity class AC^1 (a subclass of plynomial time). We show that the generalized word problem of T_fin is undecidable. We study the distortion functions of T_fin and we show that T_fin contains all finite direct products of finitely generated free groups as subgroups with linear distortion. As a consequence, up to polynomial equivalence of functions, the following three sets are the same: the set of distortions of T_fin, the set of all Dehn functions of finitely presented groups, and the set of time complexity functions of nondeterministic Turing machines.

Recommendations

• Introductory notes on Richard Thompson's groups
• Presentations of higher dimensional Thompson groups.
• Monoid generalizations of the Richard Thompson groups.
• Free products in R. Thompson's group \(V\).
• Higher dimensional Thompson groups.

Cites work

• scientific article; zbMATH DE number 3943051 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3672160 (Why is no real title available?)
• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• A construction which can be used to produce finitely presented infinite simple groups
• A finitely presented simple group with unsolvable conjugacy problem
• An application of polycyclic monoids to rings
• Constructing finitely presented simple groups that contain Grigorchuk groups
• Constructing inverse semigroups from category actions
• Isoperimetric and isodiametric functions of groups
• Isoperimetric functions of groups and computational complexity of the word problem
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• Simple \(C^*\)-algebras generated by isometries
• The complexity of Grigorchuk groups with application to cryptography
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
• Word Problems Solvable in Logspace

Cited in

(40)

• Embeddings into Thompson's groups from quasi-median geometry
• UNDECIDABILITY AND THE DEVELOPABILITY OF PERMUTOIDS AND RIGID PSEUDOGROUPS
• The \(\mathcal R\)- and \(\mathcal L\)-orders of the Thompson-Higman monoid \(M_{k,1}\) and their complexity.
• Compression techniques in group theory
• The Thompson-Higman monoids \(M_{k,i}\): the \(\mathcal J\)-order, the \(\mathcal D\)-relation, and their complexity.
• Metric spaces with complexity of the smallest infinite ordinal number
• CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
• Partial category actions on sets and topological spaces
• Non-commutative Stone duality: inverse semigroups, topological groupoids and \(C^*\)-algebras
• Bernoulli measure on strings, and Thompson-Higman monoids.
• Monoids that map onto the Thompson-Higman groups
• Introductory notes on Richard Thompson's groups
• The Booleanization of an inverse semigroup
• Infinitely generated semigroups and polynomial complexity
• Irreducible Pythagorean representations of R. Thompson's groups and of the Cuntz algebra
• Divergence functions of Thompson groups
• Compact presentability of tree almost automorphism groups
• Some undecidability results for asynchronous transducers and the Brin-Thompson group \(2V\)
• Conjugator length in Thompson's groups
• The action of the Thompson group \(F\) on infinite trees
• Polynomial-time right-ideal morphisms and congruences
• FACTORIZATIONS OF THE THOMPSON–HIGMAN GROUPS, AND CIRCUIT COMPLEXITY
• The polycyclic inverse monoids and the Thompson groups revisited
• The Polycyclic MonoidsP_nand the Thompson GroupsV_n,1
• New embeddings between the Higman-Thompson groups
• The word problem of the Brin-Thompson group is \textsf{coNP}-complete
• Generalizations of free monoids
• Monoid generalizations of the Richard Thompson groups.
• Orthogonal Completions of the Polycyclic Monoids
• One-way permutations, computational asymmetry and distortion.
• Representations of Higman-Thompson groups from Cuntz algebras
• The universal Boolean inverse semigroup presented by the abstract Cuntz-Krieger relations
• Higher dimensional generalizations of the Thompson groups
• Pseudogroups and their étale groupoids.
• Semigroups and one-way functions
• 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
• Recent developments around partial actions
• A dynamical definition of f.g. virtually free groups
• Complexity among the finitely generated subgroups of Thompson's group
• A CORRESPONDENCE BETWEEN BALANCED VARIETIES AND INVERSE MONOIDS

This page was built for publication: THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4658702)