# Finitely generated subgroups of free groups

[tag:code-golf] [tag:mathematics] [tag:abstract-algebra] [tag:decision-problem]

Suppose you are given the free group \$F_n\$ on \$n\$ generators\${}^1\$, a finite subset \$S\$ of \$F_n\$, and an element \$x \in F_n\$.  Then there is an algorithm to determine whether \$x\$ is in the subgroup generated\${}^2\$ by \$S\$, as follows:

* Start with a directed graph with a single "base" vertex, and no edges.
* For each element of \$S\$, add a cycle to the graph according to the corresponding free group word.  Start at the base vertex; for each generator \$g_n\$ in the word, add an arrow labelled by \$n\$; for each inverse of a generator \$g_n^{-1}\$ in the word, add an arrow in the opposite direction labelled by \$n\$; and end at the base vertex.
* If there is a pair of edges with the same label and with either the same source or the same destination, merge those two edges and the two vertices at the other end.  (Except that merging two vertices is not necessary if the two edges have the same source and the same destination.)
* Iterate the previous step until there is no such pair of edges left.
* Now follow the graph from the base vertex, according to the reduced free group word corresponding to \$x\$.  For each generator \$g_n\$ in the word, look for an edge with source at the current vertex and label \$n\$, and move to the destination of that edge.  For each generator \$g_n^{-1}\$ in the word, look for an edge with target at the current vertex and label \$n\$, and move to the source of that edge.
  * If at any point, you do not find such an edge, then \$x \notin \langle S \rangle\$.
  * If at the end, you end up back at the base vertex, then \$x \in \langle S \rangle\$; otherwise, \$x \notin \langle S \rangle\$.

(I plan to give an example of the operation of this algorithm; but I do not have time at the moment to generate the required graph diagrams.)

## Task

Your task is: given a finite subset \$S\$ of a free group \$F_n\$ and an element \$x \in F_n\$, determine whether \$x\$ is in the subgroup generated by \$S\$.  (Note: we are *not* asking to determine whether \$x\$ is in the *normal* subgroup generated by \$S\$; that problem is undecidable in general.)

You are not required to use the above algorithm.  On the other hand, your program or function must always terminate in finite time; so for example, that rules out a naive algorithm just taking all possible products of elements of \$S\$ and their inverses and determining whether you eventually find \$x\$ in the output.

## Input

You will be given a list of free group elements, and a second input giving another free group element.  Possible input formats for free group elements include:
* An element of a built-in free group type.
* A string in the form `abCbcA` where the generators are `a` through `z` and for example `C` represents the inverse of the generator `c`.  You may assume the string is in reduced form, so for example it will not contain either `Cc` or `cC`.

If you like, you could also take a single list of free group elements, and use the first element as \$x\$ and the rest of the list as \$S\$.

If it is useful, you may assume the list of subgroup generators is nonempty, and also that \$x\$ and each element of the list is not the empty word.

## Output

A truthy/falsey value according to whether or not \$x \in \langle S \rangle\$, where \$S\$ is the set of elements of the list for the first input and \$x\$ is the second input.

## Examples

```
[aa, ab], a -> False
[aa, ab], ba -> False
[aa, ab], Ba -> True
[aBc, bc], aBBCbA -> True
[aBc, bc], abc -> False
[aaaaa, aaa], a -> True
```
## Score

This is [tag:code-golf]: the shortest code in bytes for any given programming language wins.

---

\${}^1\$ The free group \$F_n\$ on \$n\$ generators can be described as the reduced words in the alphabet consisting of formal symbols \$g_1, g_1^{-1}, g_2, g_2^{-1}, \ldots, g_n, g_n^{-1}\$.  Here, "reduced" means that \$g_i\$ and \$g_i^{-1}\$ never appear next to each other in the word.  To multiply two words, concatenate them and then iteratively cancel out pairs \$g_i g_i^{-1}\$ or \$g_i^{-1} g_i\$ in the middle.  This has the empty word as an identity element, and to find the inverse of a reduced word, reverse the order and transform each \$g_i\$ into \$g_i^{-1}\$ and vice versa.

\${}^2\$ The subgroup of \$F_n\$ generated by a subset \$S \subseteq F_n\$ is the smallest subset of \$F_n\$ which contains \$S\$, also contains the identity element, and is closed under multiplication and inverses.  This can alternately be described as the set of elements of \$F_n\$ which can be formed as the product of some finite sequence of elements of \$S\$, and/or their inverses.