A string rewriting system (SRS), also known as semi-Thue system, exploits the free monoid structure of the strings (words) over an alphabet to extend a rewriting relation, formula_65, to "all" strings in the alphabet that contain left- and respectively right-hand sides of some rules as substrings. Formally a semi-Thue system is a tuple formula_66 where formula_67 is a (usually finite) alphabet, and formula_65 is a binary relation between some (fixed) strings in the alphabet, called rewrite rules. The one-step rewriting relation relation <math>\xrightarrowinduced by formula_65 on formula_70 is defined as: for any strings formula_71 formula_72 if and only if there exist formula_73 such that formula_74, formula_75, and formula_76. Since <math>\xrightarrowis a relation on formula_70, the pair formula_78 fits the definition of an abstract rewriting system. Obviously formula_65 is a subset of formula_80. If the relation formula_65 is symmetric, then the system is called a Thue system.