We prove two theorems regarding the algorithmic theory of groups. First, that the compressed word problem in every finitely generated fully residually free group can be decided in polynomial time. As a corollary, the word problem in the automorphism group of such a group has a polynomial time solution. Second, for any torsion-free hyperbolic group H and any group G that is finitely generated and fully residually H, we construct a finite collection of homomorphisms, at least one of which is injective, from G to groups obtained from H by extensions of centralizers. As corollaries, we obtain an effective embedding of any finitely generated residually H group into a finite direct product of groups obtained from H by extensions of centralizers, and we prove that the word problem in any finitely generated residually H group can be decided in polynomial time. / On prouve deux théorèmes dans le domaine de la théorie algorithmique des groupes. D'abord on démontre que le problème de l'identité des mots compressés est soluble en temps polynomial dans tout groupe de type fini et discriminé par un groupe libre. Il s'en suit que le problème de l'identité de mots dans le groupe d'automorphismes d'un tel groupe est soluble en temps polynomial. Ensuite, pour tout groupe hyperbolique sans torsion H et tout groupe G de type fini qui est discriminé par H, on construit une collection finie d'homomorphismes, au moins un desquels est injective, entre G et des groupes obtenus de H par des extensions des centralisateurs. De ce fait, on obtient une inclusion algorithmique de tout groupe de type fini et séparé par H dans un produit direct fini de groupes obtenus de H par extensions des centralisateurs et on démontre que le problème de l'identité dans tout groupe de type fini et séparé par H est soluble en temps polynomial.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.106347 |
| Date | January 2012 |
| Creators | Macdonald, Jeremy |
| Contributors | Olga Kharlampovich (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (Department of Mathematics and Statistics) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0013 seconds