Definition
A string rewriting system or semi-Thue system is a tuple where
- is an alphabet, usually assumed finite. The elements of the set (* is the Kleene star here) are finite (possibly empty) strings on, sometimes called words in formal languages; we will simply call them strings here.
- is a binary relation on strings from, i.e., Each element is called a (rewriting) rule and is usually written .
If the relation is symmetric, then the system is called a Thue system.
The rewriting rules on R can be naturally extended to other strings in by allowing substrings to be rewritten according to R. More formally, the one-step rewriting relation relation induced by R on for any strings s, and t in :
- if and only if there exist x, y, u, v in such that s = xuy, t = xvy, and .
Since is a relation on, the pair fits the definition of an abstract rewriting system. Obviously R is a subset of . Some authors use a different notation for the arrow in (e.g. ) in order to distinguish it from R itself 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 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, denoted by (see abstract rewriting system#Basic notions). This is called the rewriting relation or reduction relation on induced by R.
Read more about this topic: Semi-Thue System
Famous quotes containing the word definition:
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)