In mathematics, computer science, and logic, rewriting covers a wide range of (potentially non-deterministic) methods of replacing subterms of a formula with other terms. What is considered are 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.
Contents
- Logic
- Linguistics
- Abstract rewriting systems
- Normal forms joinability and the word problem
- The ChurchRosser property and confluence
- Termination and convergence
- String rewriting systems
- Term rewriting systems
- Formal definition
- Termination
- Graph rewriting systems
- Trace rewriting systems
- Philosophy
- References
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 declarative programming languages are based on term rewriting.
Logic
In logic, the procedure for obtaining the conjunctive normal form (CNF) of a formula can be conveniently written as a rewriting system. The rules of such a system would be:
where the symbol (
Linguistics
In linguistics, rewrite rules, also called phrase structure rules, are used in some systems of generative grammar, as a means of generating the grammatically correct sentences of a language. Such a rule typically takes the form A → X, where A is a syntactic category label, such as noun phrase or sentence, and X is a sequence of such labels and/or morphemes, expressing the fact that A can be replaced by X in generating the constituent structure of a sentence. For example, the rule S → NP VP means that a sentence can consist of a noun phrase followed by a verb phrase; 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's 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, (abbreviated ARS), although more recently authors use abstract rewriting system as well. (The preference for the word "reduction" here instead of "rewriting" constitutes a departure from the uniform use of "rewriting" in the names of systems that are particularizations of ARS. Because the word "reduction" does not appear in the names of more specialized systems, in older texts reduction system is a synonym for ARS).
An ARS is simply a set A, whose elements are usually called objects, together with a binary relation on A, traditionally denoted by →, and called the reduction relation, rewrite relation or just reduction. This (entrenched) terminology using "reduction" is a little misleading, because the relation is not necessarily reducing some measure of the objects; this will become more apparent when we discuss string rewriting systems further in this article.
Example 1. Suppose the set of objects is T = {a, b, c} and the binary relation is given by the rules a → b, b → a, a → c, and b → c. Observe that these rules can be applied to both a and b in any fashion to get the term c. Such a property is clearly an important one. Note also, that c is, in a sense, a "simplest" term in the system, since nothing can be applied to c to transform it any further. This example leads us to define some important notions in the general setting of an ARS. First we need some basic notions and notations.
Normal forms, joinability and the word problem
An object x in A is called reducible if there exists some other y in A such that
A related, but weaker notion than the existence of normal forms is that of two objects being joinable: x and y are said to be joinable if there exists some z with the property that
One of the important problems that may be formulated in an ARS is the word problem: given x and y, are they equivalent under
The Church–Rosser property and confluence
An ARS is said to possess the Church–Rosser property if and only if
Several different properties are equivalent to the Church–Rosser property, but may be simpler to check in some particular setting. In particular, confluence is equivalent to Church–Rosser. An ARS
Theorem. For an ARS the following conditions are equivalent: (i) it has the Church–Rosser property, (ii) it is confluent.
Corollary. In a confluent ARS if
Because of these equivalences, a fair bit of variation in definitions is encountered in the literature. For instance, in Bezem et al. 2003 the Church–Rosser property and confluence are defined to be synonymous and identical to the definition of confluence presented here; Church–Rosser as defined here remains unnamed, but is given as an equivalent property; this departure from other texts is deliberate. Because of the above corollary, in a confluent ARS one may define a normal form y of x as an irreducible y with the property that
Local confluence on the other hand is not equivalent with the other notions of confluence given in this section, but it is strictly weaker than confluence. The relation
Termination and convergence
An abstract rewriting system is said to be terminating or noetherian if there is no infinite chain
Theorem (Newman's Lemma): A terminating ARS is confluent if and only if it is locally confluent.
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,
In a SRS, the reduction relation
The notion of a semi-Thue system essentially coincides with the presentation of a monoid. Since
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
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 where the objects are terms, or expressions with nested sub-expressions. For example, the system shown under Logic above is a term rewriting system. The terms in this system are composed of binary operators
In contrast to string rewriting systems, whose objects are flat sequences of symbols, the objects a term rewriting system works on, i.e. the terms, 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.
Formal definition
A term rewriting rule is a pair of terms, commonly written as
For example,
Termination
Beyond section Termination and convergence, additional subtleties are to be considered for term rewriting systems.
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:
f(x,x) → g(x),f(x,g(x)) → b,h(c,x) → f(h(x,c),h(x,x)).The following two examples of terminating term rewrite systems are due to Toyama:
and
Their union is a non-terminating system, since
See Rewrite order and Path ordering (term rewriting) for ordering relations used in termination proofs for term rewriting systems.
Graph rewriting systems
A generalization of term rewrite systems are graph 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.
Philosophy
Rewriting systems can be seen as programs that infer end-effects from a list of cause-effect relationships. In this way, rewriting systems can be considered to be automated causality provers.