Rewriting
The term rewriting systems (TES ) is a formal computation model in theoretical computer science. In particular, they form the basis of logic and functional programming. They also play an important role in the word problem and the termination analysis.
Term Rewriting Systems are sets of so-called term rewriting rules. These quantities you can imagine how systems of equations between terms, in which the equations may only be used from left to right.
Plus (0, y) → y plus succ ( succ (x ), y ) → (plus (x, y)) The above rules constitute a term rewriting system, which can be understood as the addition of two natural numbers. This requires that the number 0 1 represented by the term 0, the number with the term succ ( 0), the number 2 with the term succ ( succ (0)) and so on. The rules state that, for example, each occurrence of a term must be in replaced. It can even be any term, so it must not constitute a natural number in particular.
Term rewriting systems are Turing -complete, so what are the computational power in terms other formalisms such as the Turing machine, the lambda calculus, or register machine in every way. Since they are relatively simple in structure and can be handled well by computers that provide term rewriting systems an important tool in the computer-assisted analysis of algorithms dar.
- 2.1 Descriptive Description
- 2.2 Formal Definition
- 3.1 scheduling
- 3.2 confluence
- 4.1 decision procedure for the word problem
- 4.2 termination analysis
Definitions
In order to build a term rewriting system, one first needs a clear understanding of the underlying concepts.
Terme
For a set of function symbols, and a ( infinite) set of variables we define the set of terms inductively as follows:
- Each variable and each zero ary function symbol (ie, any constant) is a Term
- Are Terme and is an n- ary function symbol, is also a Term
Note that this definition corresponds exactly to the denition of a mathematical Termes.
Without formal definition of the following terms still be mentioned:
- A substitution assigns some variables to new terms. A substitution applied to a term, by each occurrence of a variable is replaced by the term set by the substitution. Is the substitution, for example, and is a term, as is the term which is formed by applying on.
- A term matcht a term if there is a substitution, so that is true. For example matcht the term.
Term Rewriting rules
A term rewrite rule is a pair of two terms, which may be a variable and also may occur in any variable that does not occur in. The reason for this limitation is related to the termination of a term rewriting system and is explained in more detail in the appropriate section.
The term rewrite relation
The "How " of a term rewriting system is defined by the so-called term rewriting relation.
Descriptive Description
Fits to a term or a subterm of the left-hand side of a rule, so you can replace them left in through the right side of the corresponding rule, and so acquire a new term. This will be illustrated by some examples. For this we consider the simple term rewriting system
F ( x, y) → X The term can be evaluated with this rule. can evaluate to. you can in one step both to and to also evaluate.
Formal definition
A term evaluates to, written, if the following applies:
- There is a substitution and
- A rule in so
- The term includes and
- At the same location containing the term, but otherwise with matches.
Issues
Depending on the application of a rewriting system, there are several problems which are of interest. These include:
Termination
This one raises the question of whether there is a term rewriting system terms that allow an infinite chain of evaluations, or whether all derivatives of all terms are always finite. In the latter case, also called terminating or sound.
Although the question of the termination in any Turing complete computational systems is undecidable. However, there are a lot of advanced techniques to automatically prove the termination of many term rewriting systems. A general approach is to find a well-founded order with, such that for all rules of the TES. In addition, this order must be preserved, if you are on substitutions and applies ( the order must be stable ) or if and occur as subterms of another term ( the order must be monotonic ). There are numerous other methods. One can interpret the terms, for example as polynomials or matrices, and perform a more detailed analysis of the dependencies of function symbols with each other. For this purpose, we refer to the further reading.
Confluence
Starting from a term, there may be several possible derivations. With confluence, we define the properties of a term rewriting system, that two terms that emerge in several steps in different ways from one output term, can be merged again to a term always. A related question is whether the described by a term rewriting system calculation for the same input always the same result (unique normal form ) comes. Confluence is undecidable in general, as well as scheduling.
A term rewriting system which is confluent and terminates, also referred to as convergent. For such systems exist to each term a unique normal form. It is decidable whether a terminating term rewriting system is confluent.
Applications
As a mathematical construct is relatively easy to handle term rewriting systems are suitable for computer-based treatment of problems in theoretical computer science. Some applications are:
Decision procedure for the word problem
A term system of equations is a set of equations between terms. The word problem for one understands the question whether an equation shall apply on condition that the equations are true. As an example, you could encode in the group axioms:
F (x, f ( y, z) ) = f (f ( x, y), z) f (x, s) = x f (x, i (x) ) = e Here, the binary function symbol is the group link, the unary function returns the inverse elements, and the constant denotes the identity element; , And are variables. It now looks for a method to automatically check equations as or on their veracity.
To this end, we construct the system of equations equivalent and convergent term rewriting system. Equivalent here means that if and only if. The notation means that the term rewriting relation can be applied here as often and in both directions.
If one has now been such a convergent TES, can be solved by evaluating simple and means as long as in any manner until no further evaluation is no longer possible, the word problem. Since the TES is convergent, by assumption, there are no infinite evaluation. The process itself terminated so. Since the TES is also confluent, it does not matter which one chooses the possible analyzes. Now performs the evaluation of the two terms to the same term, then for the equations of.
Since the word problem is undecidable, can not always find a convergent term rewriting system, which makes the word problem for the corresponding system of equations decidable. A method to construct convergent term rewriting systems is the Knuth - Bendix completion procedure .. It is calculated in case of success for a given set of equations and a well-founded term ordering an equivalent and convergent term rewriting system. However, neither the termination nor the success of the Knuth - Bendix completion procedure is guaranteed. For the case of the group axioms above the Knuth - Bendix completion procedure computes eg the following convergent term rewriting system:
F (x, s) - > x f (s, x) -> x f ( x, i ( x)) - > e f (i (x), x) - > e f ( f ( x, y), z) -> f (x, f ( y, z) ) f (x, f (i (x), y)) -> y f (i (x ), f ( x, y)) -> y i ( e) - > e i (i (x)) -> x i (f (x, y)) -> f (i (Y), i ( x)) termination analysis
As for term rewriting systems so many powerful techniques exist which can prove the termination, transforming programs of higher programming in term rewriting systems and applies these techniques to it. The tool aprove, which is developed at the RWTH Aachen, this has been implemented for the programming languages Prolog and Haskell.
The treatment of imperative and object-oriented languages such as Java, is the subject of current research.