Departamento de Matemáticas UAM

Resumen: Un grupo libre Φ con una base finita X es un objeto muy fácil de describir grosso modo: sus elementos
están representados por palabras w = y1 · · · yn , donde cada letra yi es bien un elemento de X o bien un sı́mbolo
de la forma x̄, con x ∈ X (el ‘inverso’ de x). Dos palabras se multiplican de forma obvia: concatenándolas.
Dos palabras representan el mismo elemento de Φ si se puede pasar de una a otra insertando o eliminando
expresiones de la forma xx̄ ó x̄x.
En esta charla nos ocupamos del siguiente problema: dado un elemento (representado por una palabra)
w de Φ y un subconjunto S de Φ, ¿existe un algoritmo para decidir si w ∈ S?
Obviamente la respuesta depende en parte de qué sea S y de cómo esté descrito. En esta charla S
será bien un subgrupo H (finitamente generado) de Φ o bien un producto finito H1 · · · Hm de subgrupos
(finitamente generados).
Las herramientas que utilizaremos son muy simples (y fáciles de describir, lo que haremos durante la
charla): (grupos de) permutaciones; el grupo fundamental de un haz de circunferencias; autómatas (con un
número finito de estados).
Esta charla es elemental: no se requieren muchos más conocimientos de los que he indicado en este
resumen.