Word problem for semigroups

In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation ${\displaystyle R}$ between fixed strings over the alphabet, called rewrite rules, denoted by ${\displaystyle s\rightarrow t}$, an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is ${\displaystyle usv\rightarrow utv}$, where ${\displaystyle s}$, ${\displaystyle t}$, ${\displaystyle u}$, and ${\displaystyle v}$ are strings.

...
Wikipedia