Solving the Word Problem

We left off our discussion of regular languages with dashed hopes when we learned that $\textrm{Null} (G)$ is a regular language if and only if $G$ is finite. This means that dealing with $\textrm{Null} (G)$ , the set of words on the generators of $G$ which are trivial in $G$ , will never help us resolve the word problem because if $G$ is finite, we already know we can solve the word problem with the Cayley graph!

Fortunately all is not lost. The new plan of attack is to identify the situations in which a normal form for some group $G$ is also a regular language. In these cases we may be able to use some set of FSA’s to relate a word on the set of group generators to the normal form for the group element that the word reduces to (although ultimately, as we will see, we won’t even need an FSA that accepts a normal form for $G$ ).

First we should see an example of a group with a normal form which is also a regular language.

Definition: A regular normal form of a group $G$ is a normal form which is also a regular language.

Example:

Let $G = \mathbb{Z} \times \mathbb{Z} = \langle a, b | ab = ba \rangle.$ We can set a normal form for this group, namely

$NF = \{ a^n b^m | n , m \in \mathbb{Z} \}.$

It is possible to build an FSA that accepts exactly this set as its language, illustrated below.

With this concept in hand, we can formulate a few interesting results.

Theorem: If $G$ and $H$ both have a regular normal form then so do $G \times H$ and $G * H$ .

The proof will be assigned, so suffice it to say that it involves some ideas about combining regular languages that we’ve seen before. Before moving on to the word problem, we can squeeze a little more juice out of the concept of a regular normal form. A regular language is, for lack of a more appropriate phrase, a set of words which has a high degree of structural regularity. For this reason we suspect that a group which permits a normal form with this structure is “nice” in some basic way. For one thing, the set of nodes and edges in an FSA is finite, so every regular language will be finite or will have to somehow make use of cycles in the graph of its FSA. To put this into rigorous terms, we recall the pumping lemma.

Theorem (The Pumping Lemma): Let $\mathcal{L }$ be regular, then there exists $n \geq 1$ such that for all words $x \in \mathcal{L}$ with $|x| > n$ , we can find $u, v, w$ with $|u|, |w| < n$ such that $x = uvw$ and $u v^i w \in \mathcal{L}$ for all $i \in \mathbb{N}$ .

The proof worked via pigeonhole by setting $n = \left| v( \mathcal{M} ) \right|$ , where $\mathcal{M}$ is the FSA that accepts $\mathcal{L}$ .

With this in mind we note that if $G$ is in infinite group with a regular normal form, then we can use the cycles in the corresponding FSA to generate an element of $G$ with infinite order.

Theorem: If $G$ has a regular normal form and $G$ is infinite, then $G$ contains an element of infinite order.

Let $\mathcal{M}$ be the FSA representing $G$ . Let $g \in G$ satisfy $| g | > | v ( \mathcal{M} ) |$ . Here the absolute value sign denotes the word length of the representative of $g$ in the regular normal form. We may take a word whose word length is greater than any integer, specifically $| v ( \mathcal{M} ) |$ , because $G$ is infinite and therefore its normal form is infinite. Let $\pi: S^* \to G$ be the natural transformation that sends words to group elements. By an argument much like the proof of the pumping lemma, we note that the path which yields the word for $g$ must contain a loop, therefore we have

$g = \pi(uvw) .$

Where $u$ is given by a path from the start state to some vertex, $\alpha$ , $v$ is a loop that starts and ends at $\alpha$ , and $w$ is a path that begins at $\alpha$ and ends at some accept state. We can see that $u v^i w$ must also be accepted for all $i \in \mathbb{N}$ , so because this language is a normal form, we have that for $i > 1$ ,

$\pi(uvw) \neq \pi(u v^i w).$

Since $\pi$ is a homomorphism, we then have

$\pi(v) \neq \pi(v^i) = \pi(v)^i .$

This means that the element $\pi(v)$ must have infinite order, which is all to say that if $G$ has a regular normal form, then $G$ is not infinite torsion.

Permitting a regular normal form is a great property for a group to have, but we already get the feeling that it is quite specific, and it is possibly difficult to prove whether a group even has it. We will not use these normal forms explicitly in our solution of the word problem, but we will retain the general idea of making an FSA work for us to produce words with useful properties. This is part of what motivates the following definition.

Definition: Let $G = \langle S | R \rangle$ be a group. We say $G$ has an automatic structure if there exists the following set of FSAs

$\mathcal{M}_G$ where the language $\mathcal{L}_G$ surjects onto $G$ under $\pi$ , namely ever element of $G$ is represented by some word. This is FSA is called the word acceptor.
$\mathcal{M}_{=}$ where $\mathcal{L}_{= } = \{ (u,v) | u,v \in \mathcal{L}_G, \pi(u) = \pi(v) \}$ . This FSA is called the equality checker.
$\mathcal{M}_s$ where $\mathcal{L}_s = \{ (u,v) | u,v \in \mathcal{L}_G, \pi(v) = \pi(us) \}$ . This is the word comparator.

A few examples are in order to unpack this definition. First we draw out all the FSA’s for the example $G = \mathbb{Z}$ .

We have only drawn $\mathcal{M}_a$ since $\mathcal{M}_{a^{-1}}$ would look very similar. In general we do not necessarily have that the language given by $\mathcal{M}_G$ is necessarily a normal form for $G$ , but in this case we do, which means that drawing $\mathcal{M}_{=}$ is easy as we can replace every edge $a$ with the edge $(a,a)$ and so on, since every word uniquely represents a group element, so $\pi(u) = \pi(w)$ implies that $u$ and $w$ are the same word. We will see this at play in the next example, where $G = F_2$ . Here we will omit $\mathcal{M}_{=}$ since we understand it’s structure, and again only draw $\mathcal{M}_{a}$ for reasons of symmetry.

Drawing $\mathcal{M}_{a}$ once we have $\mathcal{M}_{=}$ is not too large a task. In the above example, the orange part of the graph is exactly what $\mathcal{M}_{=}$ would be, where the purple arrows turn this graph into the graph of $\mathcal{M}_{a}$ . Further examples of groups with automatic structure include all free groups and all free abelian groups, all finite groups, many coxeter groups, all braid groups, hyperbolic groups, and the special linear group over $\mathbb{Z}$ for $n = 2$ . A few groups which do not have automatic structure are infinite torsion groups, special linear groups over $\mathbb{Z}$ with $n \geq 3$ , and most Baumslag-Solitar groups.

We are now in a position to exhibit the crown jewel of our discussion.

Theorem: If $G$ is automatic then $G$ has solvable word problem.

Let $G = \langle S | R \rangle$ . Pick some accepted word $u$ . For each letter $x \in S$ , we will use the automata that make $G$ automatic to find an accepted word for $\pi(ux)$ .

We take the word comparator automaton $\mathcal{M}_x$ and observe that we can take it to have no two edges leaving the same vertex with the same label by arguments we’ve made before. By definition $\mathcal{M}_x$ accepts pairs $(v, u)$ such that $\pi(u) = \pi(vx)$ . Sweeping a few things under the rug, we argue that we can follow the path that gives $(v, u)$ in $\mathcal{M}_x$ and read off the word word $v$ , where we are guaranteed $\pi(v) = \pi(ux)$ . This is an algorithm which gives us an accepted word for $\pi(ux )$ .

The key idea is that we can use this algorithm generate an accepted word for every element of $G$ . There is some word in the language $\mathcal{L}_G$ which is the identity in $G$ , so just take $u$ to be this word. Now we can express every element of $G$ as $u x_1 \cdots x_n$ where $x_i \in S$ are letters in our generating set. Note that $\pi(u x_1 \cdots x_n ) = \pi(u) \pi( x_1 \cdots x_n ) = \pi(x_1 \cdots x_n )$ . We can apply the above algorithm iteratively, first to get an accepted word for the element $\pi(u x_1 )$ , and after $n$ repetitions to get the element $\pi( u x_1 \cdots x_n ) = \pi(x_1 \cdots x_n )$ . Call this accepted word $\omega$ . Since we know $\pi(u) = e \in G$ , to solve the word problem we need to know if $\pi(u) = \pi( \omega )$ . Fortunately we have a finite state automaton that tells us exactly this! We simply follow the path for $(u , \omega )$ and see if the pair is accepted.

3 Responses to Solving the Word Problem

Shuhang Xue says:

October 25, 2022 at 12:20 am

I like your post! It helped me understand using FSA to solve the world problem. I have a heuristic understanding of the automatic structure. Indeed, we recall that to solve a word problem, we need a Cayley graph to tell how to relate different combinations of generators and use the path to test out things. Thus, the FSA m_G plays the role of vertices of the Cayley graph but allows extra elements. Then, the FSA m_a’s tells us how to travel from one vertex to another. I always imagine them playing the rule of gluing things together into a “graph,” like Cayley graphs. Finally, the FSA m_= tells what paths are “equivalent.”

Osip Surdutovich says:

October 27, 2022 at 7:10 pm

Horace, this is a wonderful post and it helped me a ton when I was trying to understand automatic structure for the recent problem set! I wonder if we ever actually need to represent the word comparator and equality checker FSAs for every element of the language or is that simply the formal definition of the automatic structure and it is always OK to just show everything for a single element.

Michaela Polley says:

November 2, 2022 at 4:39 am

Great post! Your pictures are large enough to be very clear, which I know is not always easy to do. I’m still not quite clear on how we generate the different FSAs to show that a group is automatic. How do we get from the first one to the other ones?

3 Responses to Solving the Word Problem

Leave a Reply to Michaela Polley Cancel reply

Recent Posts

Recent Comments