Thue System

An associative calculus, named after A. Thue, who first formulated the problem of recognizing equality of words in associative systems (the Thue problem, see [1]). If in a given Thue system the only admissible substitutions are taken to be substitutions of right-hand sides of relations into the left-hand sides (that is, the reverse substitutions are excluded), then one obtains a Thue semi-system (or semi-Thue system, or system of substitutions). These systems in fact coincide with local canonical Post systems. Every Thue system can be regarded as a Thue semi-system, but the converse is false.

References[edit]