Problemes algorísmics sobre subgrups de grups lliures
Santamaría García, Guillermo · UPCommons institutional repository (Universitat Politècnica de Catalunya) · 2013
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.