↑ arvau

Wikipedia / Rewriting

In mathematics, linguistics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduction systems). In their most basic form, they consist of a set of objects, plus relations on how to transform those objects.

Rewriting can be non-deterministic. One rule to rewrite a term could be applied in many different ways to that term, or more than one rule could be applicable. Rewriting systems then do not provide an algorithm for changing one term to another, but a set of possible rule applications. When combined with an appropriate algorithm, however, rewrite systems can be viewed as computer programs, and several theorem proverss and declarative programming languages are based on term rewriting.

Example cases

Logic

In logic, the procedure for obtaining the conjunctive normal form (CNF) of a formula can be implemented as a rewriting system. For example, the rules of such a system would be:

  1. (double negation elimination)

  2. (De Morgan's laws)

  3. (distributivity)

For each rule, each variable) indicates that an expression matching the left hand side of it can be rewritten to one matching the right hand side of it. In such a system, each rule is a logical equivalence, so performing a rewrite on an expression by these rules does not change the truth value of it. Other useful rewriting systems in logic may not preserve truth values, see e.g. equisatisfiability.

Arithmetic

Term rewriting systems can be employed to compute arithmetic operations on natural numbers. To this end, each such number has to be encoded as a term. The simplest encoding is the one used in the Peano axioms, based on the constant (zero) and the successor function . For example, the numbers 0, 1, 2, and 3 are represented by the terms , , , and , respectively. The following term rewriting system can then be used to compute sum and product of given natural numbers.

For example, the computation of to result in can be duplicated by term rewriting as follows:

where the notation above each arrow indicates the rule used for each rewrite.

As another example, the computation of looks like:

where the last step comprises the previous example computation.

Linguistics

In linguistics, phrase structure rules, also called rewrite rules, are used in some systems of generative grammar,, where A is a syntactic category label, such as noun phrase or sentence, and X is a sequence of such labels or morphemes means that a sentence can consist of a noun phrase (NP) followed by a verb phrase (VP); further rules will specify what sub-constituents a noun phrase and a verb phrase can consist of, and so on.

Abstract rewriting systems

From the above examples, it is clear that we can think of rewriting systems in an abstract manner. We need to specify a set of objects and the rules that can be applied to transform them. The most general (unidimensional) setting of this notion is called an abstract reduction system or abstract rewriting system (abbreviated ARS). An ARS is simply a set A of objects, together with a binary relation → on A called the reduction relation, rewrite relation or just reduction.

is the reflexive transitive closure is the symmetric closure is the reflexive transitive symmetric closure. The word problem for an ARS is determining, given x and y. An object x in A is called reducible if there exists some other y in A; otherwise it is called irreducible or a normal form. An object y is called a "normal form of x, and y is irreducible. If the normal form of x. If every object has at least one normal form, the ARS is called normalizing or x and y are said to be joinable if there exists some z. An ARS is said to possess the Church–Rosser property. An ARS is confluent if for all w, x, and y in A. An ARS is locally confluent if and only if for all w, x, and y in A. An ARS is said to be terminating or noetherian. A confluent and terminating ARS is called convergent or canonical.

Important theorems for abstract rewriting systems are that an ARS is confluent iff it has the Church–Rosser property, Newman's lemma (a terminating ARS is confluent if and only if it is locally confluent), and that the word problem for an ARS is undecidable in general.

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 all strings in the alphabet that contain left- and respectively right-hand sides of some rules as substrings. Formally a semi-Thue system is a tuple is a binary relation between some (fixed) strings in the alphabet, called the set of rewrite rules. The one-step rewriting relation is symmetric, then the system is called a Thue system.

, is a congruence, meaning it is an equivalence relation is called the Thue congruence.

The notion of a semi-Thue system essentially coincides with the presentation of a monoid is a congruence, we can define the factor monoid is isomorphic is called a monoid presentation.

is the empty string, is a presentation of the free group, then we obtain a presentation of the bicyclic monoid. Thus semi-Thue systems constitute a natural framework for solving the word problem, i.e. it may 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.

Term rewriting systems

A term rewriting system (TRS) is a rewriting system whose objects are terms, which are expressions with nested sub-expressions. For example, the system shown under . Also present in the rules are variables, which represent any possible term (though a single variable always represents the same term throughout a single rule).

In contrast to string rewriting systems, whose objects are sequences of symbols, the objects of a term rewriting system form a term algebra. A term can be visualized as a tree of symbols, the set of admitted symbols being fixed by a given signature. As a formalism, term rewriting systems have the full power of Turing machines, that is, every computable function can be defined by a term rewriting system.

Some programming languages are based on term rewriting. One such example is Pure, a functional programming language for mathematical applications.

Formal definition

A rewrite rule is a pair of terms, to indicate that the left-hand side can be replaced by the right-hand side . A term rewriting system is a set can be applied to a term if the left term matches some subterm of , that is, if there is some substitution rooted at some position to the term . The subterm matching the left hand side of the rule is called a redex or reducible expression. The result term of this rule application is then the result of replacing the subterm at position in is said to be rewritten in one step, or rewritten directly by some authors.

is said to be rewritten is the transitive closure is used to denote the reflexive-transitive closure or of rules can be viewed as an abstract rewriting system as defined above as its rewrite relation.

, see picture 2..

Termination

Termination issues of rewrite systems in general are handled in Abstract rewriting system#Termination and convergence. For term rewriting systems in particular, the following additional subtleties are to be considered.

Termination even of a system consisting of one rule with a linear left-hand side is undecidable. Termination is also undecidable for systems using only unary function symbols; however, it is decidable for finite ground systems.

The following term rewrite system is normalizing, but not terminating, and not confluent:

The following two examples of terminating term rewrite systems are due to Toyama:

and

Their union is a non-terminating system, since

This result disproves a conjecture of Dershowitz, are linear, and there are no "overlaps. All these properties are satisfied by Toyama's examples.

See Rewrite order and Path ordering (term rewriting) for ordering relations used in termination proofs for term rewriting systems.

Higher-order rewriting systems

Higher-order rewriting systems are a generalization of first-order term rewriting systems to lambda terms, allowing higher order functions and bound variables. Various results about first-order TRSs can be reformulated for HRSs as well.

Graph rewriting systems

Graph rewrite systems are another generalization of term rewrite systems, operating on graphs instead of (ground-) terms / their corresponding tree representation.

Trace rewriting systems

Trace theory provides a means for discussing multiprocessing in more formal terms, such as via the trace monoid and the history monoid. Rewriting can be performed in trace systems as well.

See also

Notes

Further reading

References