The groups of Richard Thompson and complexity
| dc.creator | Birget, Jean-Camille | |
| dc.date | 2002-04-24 | |
| dc.date | 2003-10-31 | |
| dc.date.accessioned | 2026-07-07T04:48:03Z | |
| dc.date.available | 2026-07-07T04:48:03Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/math/0204292 | |
| dc.identifier | http://arxiv.org/abs/math/0204292 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/63900 | |
| dc.subject | Group Theory | |
| dc.subject | 20F10, 68Q15 | |
| dc.title | The groups of Richard Thompson and complexity | |
| dc.type | text |