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.