I'd appreciate it if someone could offer a schematic explanation of the word problem from group theory in terms which someone at a calculus III level (but without any background in group theory or abstract algebra) could understand. If you are going to use "generators" in your explanation, please explain what a generator is.

  • 2
    $\begingroup$ it is like explaining the colors to the one who can not see. At least you should learn what group is and some basic defination in my opinion. $\endgroup$ – mesel Mar 31 '14 at 20:31
  • 1
    $\begingroup$ If you have no background at all in abstract algebra and group theory then I can't see how can a not-so-basic issue in group theory can be explained... $\endgroup$ – DonAntonio Mar 31 '14 at 20:32
  • 1
    $\begingroup$ I gave a lengthy explanation of the word problem here. $\endgroup$ – user1729 Mar 31 '14 at 20:45
  • $\begingroup$ It is a challenge to try and explain the algebra. In the case of braid groups a somewhat pictorial explanation is possible. Basically the word problem there asks that if you are given two sequences of elementary braid moves (these are the moves of crossing two adjacent braids), whether the resulting braids look the same. The catch is the some different sequences of moves do lead to identical braids, and you need to take that into account. $\endgroup$ – Jyrki Lahtonen Mar 31 '14 at 20:45

Consider a finite alphabet $\Sigma$, i.e. a finite set of letters. For every letter $x$, call $x'$ another letter (not yet in $\Sigma$) and let $\Pi$ denote $\Sigma \cup \{ x' \mid x \in \Sigma \}$, i.e. all letters with and without prime.

A word is just a finite sequence of letters in $\Pi$; the set of all words is denoted by $\Pi^*$. The empty word is also a word; it is written as $\epsilon$.

Now you're given a finite set of rules that allow you to change a word into another word. There are always rules that allows you to remove or add occurences of $xx'$ and $x'x$ (with $x \in \Sigma$) from a word. Furthermore, there is a finite set of rules $R$ that tells you that you can replace a certain subsequence of a word by another subsequence. That is, $R$ is a finite set of pairs $(s_1,s_2)$ with $s_1, s_2 \in \Pi^*$; it means that you can replace an occurence of $s_1$ by $s_2$ or visa versa.

The word problem is: given such a $\Sigma$,a set of rules $R$, is there an algorithm that takes as input two words $w_1$ and $w_2$, and decides whether or not it is possible to change $w_1$ into word $w_2$ by applying the rules?

Example. Consider the letters $a$ and $b$ (and $a'$ and $b'$) and the rules $(aaaa,\epsilon)$, $(bb,\epsilon)$, $(b'ab,a')$. Then it is possible to transform $ab$ into $baaa$ (via $ab \to bb'ab \to ba' \to ba'aaaa \to baaa$), but it is not possible to transform $ab$ into $ba$. (If you know some group theory, you'll recognize this as a presentation of the dihedral group $D_4$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.