Semi-Thue system

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 R {displaystyle R} between fixed strings over the alphabet, called rewrite rules, denoted by s → t {displaystyle s ightarrow 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 u s v → u t v {displaystyle usv ightarrow utv} , where s {displaystyle s} , t {displaystyle t} , u {displaystyle u} , and v {displaystyle v} are strings. 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 R {displaystyle R} between fixed strings over the alphabet, called rewrite rules, denoted by s → t {displaystyle s ightarrow 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 u s v → u t v {displaystyle usv ightarrow utv} , where s {displaystyle s} , t {displaystyle t} , u {displaystyle u} , and v {displaystyle v} are strings. The notion of a semi-Thue system essentially coincides with the presentation of a monoid. Thus they constitute a natural framework for solving the word problem for monoids and groups. An SRS can be defined directly as an abstract rewriting system. It can also be seen as a restricted kind of a term rewriting system. As a formalism, string rewriting systems are Turing complete. The semi-Thue name comes from the Norwegian mathematician Axel Thue, who introduced systematic treatment of string rewriting systems in a 1914 paper. Thue introduced this notion hoping to solve the word problem for finitely presented semigroups. It wasn't until 1947 the problem was shown to be undecidable— this result was obtained independently by Emil Post and A. A. Markov Jr. A string rewriting system or semi-Thue system is a tuple ( Σ , R ) {displaystyle (Sigma ,R)} where If the relation R is symmetric, then the system is called a Thue system. The rewriting rules in R can be naturally extended to other strings in Σ ∗ {displaystyle Sigma ^{*}} by allowing substrings to be rewritten according to R. More formally, the one-step rewriting relation relation → R {displaystyle {xrightarrow{}}} induced by R on Σ ∗ {displaystyle Sigma ^{*}} for any strings s , t ∈ Σ ∗ {displaystyle s,tin Sigma ^{*}} : Since → R {displaystyle {xrightarrow{}}} is a relation on Σ ∗ {displaystyle Sigma ^{*}} , the pair ( Σ ∗ , → R ) {displaystyle (Sigma ^{*},{xrightarrow{}})} fits the definition of an abstract rewriting system. Obviously R is a subset of → R {displaystyle {xrightarrow{}}} . Some authors use a different notation for the arrow in → R {displaystyle {xrightarrow{}}} (e.g. → R {displaystyle {xrightarrow{}}} ) in order to distinguish it from R itself ( → {displaystyle ightarrow } ) because they later want to be able to drop the subscript and still avoid confusion between R and the one-step rewrite induced by R. Clearly in a semi-Thue system we can form a (finite or infinite) sequence of strings produced by starting with an initial string s 0 ∈ Σ ∗ {displaystyle s_{0}in Sigma ^{*}} and repeatedly rewriting it by making one substring-replacement at a time: A zero-or-more-steps rewriting like this is captured by the reflexive transitive closure of → R {displaystyle {xrightarrow{}}} , denoted by → R ∗ {displaystyle {xrightarrow{*}}} (see abstract rewriting system#Basic notions). This is called the rewriting relation or reduction relation on Σ ∗ {displaystyle Sigma ^{*}} induced by R.