String Rewriting Systems
A string rewriting system (SRS), also known as semi-Thue system, exploits the free monoid structure of the strings (words) over an alphabet to extend a rewriting relation, R to all strings in the alphabet that contain left- and respectively right-hand sides of some rules as substrings. Formally a semi-Thue systems is a tuple where is a (usually finite) alphabet, and R is a binary relation between some (fixed) strings in the alphabet, called rewrite rules. The one-step rewriting relation relation induced by R on is defined as: 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 u R v. Since is a relation on, the pair fits the definition of an abstract rewriting system. Obviously R is subset of . If the relation is symmetric, then the system is called a Thue system.
In a SRS, the reduction relation is compatible with the monoid operation, meaning that implies for all strings x, y, u, v in . Similarly, the reflexive transitive symmetric closure of, denoted, is a congruence, meaning it is an equivalence relation (by definition) and it is also compatible with string concatenation. The relation is called the Thue congruence generated by R. In a Thue system, i.e. if R is symmetric, the rewrite relation coincides with the Thue congruence .
The notion of a semi-Thue system essentially coincides with the presentation of a monoid. Since is a congruence, we can define the factor monoid of the free monoid by the Thue congruence in the usual manner. If a monoid is isomorphic with, then the semi-Thue system is called a monoid presentation of .
We immediately get some very useful connections with other areas of algebra. For example, the alphabet {a, b} with the rules { ab → ε, ba → ε }, where ε is the empty string, is a presentation of the free group on one generator. If instead the rules are just { ab → ε }, then we obtain a presentation of the bicyclic monoid. Thus semi-Thue systems constitute a natural framework for solving the word problem for monoids and groups. In fact, every monoid has a presentation of the form, i.e. it may be always be presented by a semi-Thue system, possibly over an infinite alphabet.
The word problem for a semi-Thue system is undecidable in general; this result is sometimes known as the Post-Markov theorem.
Read more about this topic: Reduction Systems
Famous quotes containing the words string and/or systems:
“Amongst the learned the lawyers claim first place, the most self-satisfied class of people, as they roll their rock of Sisyphus and string together six hundred laws in the same breath, no matter whether relevant or not, piling up opinion on opinion and gloss on gloss to make their profession seem the most difficult of all. Anything which causes trouble has special merit in their eyes.”
—Desiderius Erasmus (c. 1466–1536)
“The only people who treasure systems are those whom the whole truth evades, who want to catch it by the tail. A system is just like truth’s tail, but the truth is like a lizard. It will leave the tail in your hand and escape; it knows that it will soon grow another tail.”
—Ivan Sergeevich Turgenev (1818–1883)