Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2099.1/19494

Algorithmic problems about subgroups of free groups;
Problemes algorísmics sobre subgrups de grups lliures
Santamaría García, Guillermo
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III; Ventura Capell, Enric
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.
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".
À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
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/bachelorThesis
Universitat Politècnica de Catalunya
         

Mostrar el registro completo del ítem