Thue system


A semi-Thue system 𝔖=(Σ,R) is said to be a Thue system if R is a symmetric relationMathworldPlanetmath on Σ*. In other words, if xy is a defining relation in R, then so is yx.

Like a semi-Thue system, we can define the conceptsMathworldPlanetmath of immediately derivable and derivable pairs. Let R and R′′ be the respective collectionsMathworldPlanetmath of these pairs. Since R is symmetric, so is R and consequently R′′. Similarly, the notations are: for elements (a,b)R, we write ab, and for elements (c,d)R′′, we write a*b.

If we regard Σ* as a free monoid with concatenationMathworldPlanetmath as multiplicationPlanetmathPlanetmath and the empty wordPlanetmathPlanetmath λ as the multiplicative identityPlanetmathPlanetmath, then * is a congruence relationPlanetmathPlanetmath on Σ*: it is an equivalence relationMathworldPlanetmath and respects concatenation, meaning that if a*b and c*d, then ac*bd. Therefore, we can take the quotent Σ*/* and the resulting set of equivalence classesMathworldPlanetmath is again a monoid with [λ] as the multiplicative identity. It is a monoid generated by [a] whenever aΣ with relationsMathworldPlanetmathPlanetmath [u]=[v] whenever uv is a defining relation in R. Thus, two elements are in the same equivalence class if one is derivable from another. Let us denote this monoid by [Σ]𝔖.

Now let 𝔖=(Σ,R) be a Thue system. Then 𝔖 is called a group system if there exists an involutionPlanetmathPlanetmath -1 on Σ given by aa-1, and that for every aΣ, aa-1λ is a defining relation in R. Since -1 is an involution, if b is the symbol in Σ such that b=a-1, then b-1=a. So a-1a=ba=bb-1λ also. In fact, it is not hard to see that for a group system 𝔖, [Σ]𝔖 is the group with generators [a] whenever aΣ and with relators [u][v]-1 whenever uv is a defining relation in R. Every non-trivial element in [Σ]𝔖 has an expression [a1]p1[an]pn, where each ai is a letter in Σ such that it is distinct from its neighbors (aiai+1), and pi 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 semigroupsPlanetmathPlanetmath and for groups are also unsolvable.

References

  • 1 M. Davis, Computability and Unsolvability. Dover Publications, New York (1982).
  • 2 H. Hermes, Enumerability, Decidability, Computability: An Introduction to the Theory of Recursive FunctionsMathworldPlanetmath. 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).
Title Thue system
Canonical name ThueSystem
Date of creation 2013-03-22 17:33:19
Last modified on 2013-03-22 17:33:19
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 12
Author CWoo (3771)
Entry type Definition
Classification msc 03D03
Classification msc 03D40
Classification msc 68Q42
Classification msc 20M35
Related topic SemigroupWithInvolution
Defines group system