Title:
|
Algorithmic problems about subgroups of free groups; Problemes algorísmics sobre subgrups de grups lliures
|
Author:
|
Santamaría García, Guillermo
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III; Ventura Capell, Enric |
Abstract:
|
The study of the lattice of subgroups of $F_{k}$ changed completely when J.Stallings published a paper that developed some special graphs in order to solve several algorithmic problems about subgroups like the membership or the intersection problem. The eficient and nice solution using this machinery contrasted with the complex methods developed before. Stallings constructed his theory using an algebraic topology but in this paper we are going to use purely graph theory: this kind of approach needs its own definitions and sometimes could be rambling but it's really useful when talking about algorithms. So, in the first chapter we develop Stallings theory from the beginning and in the second one we explain several algorithmic applications and present some examples. |
Abstract:
|
El reticle de subgrups d'un grup lliure F_n és força interesant des del punt de vista algorísmic. Un article de J. Stallings de l'any 1983 va revolucionar el seu estudi introduint uns grafs especials que han permès resoldre molts problemes algorísmics sobre subgrups, de forma senzilla, clara i eficient. El treball consisteix en entendre bé la teoria dels grafs de Stallings, fer una llista de les aplicacions que se'n coneixen actualment, i buscar-ne de noves. Hi ha la possibilitat de programar alguns dels algorismes estudiats i fer una "calculadora de subgrups de F_n". |
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Àlgebra::Teoria de grups -Semigroups -Free groups -Graph theory -Stallings -Membership problem -Semigrups -Classificació AMS::20 Group theory and generalizations::20N Other generalizations of groups |
Rights:
|
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
Document type:
|
Bachelor Thesis |
Published by:
|
Universitat Politècnica de Catalunya
|
Share:
|
|