Semi-Thue System - Thue Congruence

Thue Congruence

In general, the set of strings on an alphabet forms a free monoid together with the binary operation of string concatenation (denoted as and written multiplicatively by dropping the symbol). In a SRS, the reduction relation is compatible with the monoid operation, meaning that implies for all strings x, y, u, v in . Since is by definition a preorder, forms a preordered monoid.

Similarly, the reflexive transitive symmetric closure of, denoted (see abstract rewriting system#Basic notions), is a congruence, meaning it is an equivalence relation (by definition) and it is also compatible with string concatenation. The relation is called the Thue congruence generated by R. In a Thue system, i.e. if R is symmetric, the rewrite relation coincides with the Thue congruence .