Rewriting - String Rewriting Systems

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:  Rewriting

Famous quotes containing the words string and/or systems:

    First you find a little thread, a little thread leads you to a string, and the string leads you to a rope. And from the rope you hang by the ... neck.
    —A.I. (Albert Isaac)

    Not out of those, on whom systems of education have exhausted their culture, comes the helpful giant to destroy the old or to build the new, but out of unhandselled savage nature, out of terrible Druids and Berserkirs, come at last Alfred and Shakespeare.
    Ralph Waldo Emerson (1803–1882)