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:
“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)
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)
“According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
—Ana Castillo (b. 1953)