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:
“... 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)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)