Like a semi-Thue system, we can define the concepts of immediately derivable and derivable pairs. Let and be the respective collections of these pairs. Since is symmetric, so is and consequently . Similarly, the notations are: for elements , we write , and for elements , we write .
If we regard as a free monoid with concatenation as multiplication and the empty word as the multiplicative identity, then is a congruence relation on : it is an equivalence relation and respects concatenation, meaning that if and , then . Therefore, we can take the quotent and the resulting set of equivalence classes is again a monoid with as the multiplicative identity. It is a monoid generated by whenever with relations whenever is a defining relation in . Thus, two elements are in the same equivalence class if one is derivable from another. Let us denote this monoid by .
Now let be a Thue system. Then is called a group system if there exists an involution on given by , and that for every , is a defining relation in . Since is an involution, if is the symbol in such that , then . So also. In fact, it is not hard to see that for a group system , is the group with generators whenever and with relators whenever is a defining relation in . Every non-trivial element in has an expression , where each is a letter in such that it is distinct from its neighbors (), and are non-zero integers. This expression is unique in the sense that it is “reduced”. See reduced words for more detail.
Remark. Like the word problem for semi-Thue systems, the word problem for Thue systems and group systems can be similarly posed. It can be shown that the word problem for Thue systems and group systems are both unsolvable. As a result, the corresponding word problems for semigroups and for groups are also unsolvable.
- 1 M. Davis, Computability and Unsolvability. Dover Publications, New York (1982).
- 2 H. Hermes, Enumerability, Decidability, Computability: An Introduction to the Theory of Recursive Functions. Springer, New York, (1969).
- 3 H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
- 4 P.S. Novikov, On the algorithmic unsolvability of the word problem in group theory, Trudy Mat. Inst. Steklov 44, 1-143 (1955).
|Date of creation||2013-03-22 17:33:19|
|Last modified on||2013-03-22 17:33:19|
|Last modified by||CWoo (3771)|