About Thue systems

This is from Lewis & Papadimitriou, Elements of the Theory of Computation, 6.4.2. Thue Systems.

A Thue system is a finite set of unordered pairs of strings that determines an equivalence relation on strings thusly: two strings are equivalent under the system if one can be transformed into the other by successively replacing substrings that are found as one member of some pair with the other member of that pair.

The word problem for Thue systems is the problem of determining, given a Thue system J and two strings x and y, whether or not x and y are equivalent.

The word problem for Thue systems is unsolvable. Moreover, there is a fixed Thue system J₀ and a string w₀ such that the problem of determining whether w is equivalent to w₀ by J₀ for an abritrary string w is also unsolvable.

Thue systems are bidirectional in this sense: for every u → w, there is also a w ← u. A system which is unidirectional, in which the replacements only occur in one direction, is called a semi-Thue system.