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 between fixed strings over the alphabet, called
rewrite rules, denoted by
, 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
, where
,
,
, and
are strings.