![]() | ||
In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviation ARS) is a formalism that captures the quintessential notion and properties of rewriting systems. In its simplest form, an ARS is simply a set (of "objects") together with a binary relation, traditionally denoted with
Contents
- Definition
- Example 1
- Basic notions
- Normal forms and the word problem
- Joinability and the ChurchRosser property
- Notions of confluence
- Termination and convergence
- References
Historically, there have been several formalizations of rewriting in an abstract setting, each with its idiosyncrasies. This is due in part to the fact that some notions are equivalent, see below in this article. The formalization that is most commonly encountered in monographs and textbooks, and which is generally followed here, is due to Gérard Huet (1980).
Definition
Abstract reduction system, (abbreviated ARS) is the most general (unidimensional) notion about specifying a set of objects and rules that can be applied to transform them. 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 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.
In some contexts it may be beneficial to distinguish between some subsets of the rules, i.e. some subsets of the reduction relation →, e.g. the entire reduction relation may consist of associativity and commutativity rules. Consequently, some authors define the reduction relation → as the indexed union of some relations; for instance if
As a mathematical object, an ARS is exactly the same as an unlabeled state transition system, and if the relation is considered as an indexed union, then an ARS is the same as a labeled state transition system with the indices being the labels. The focus of the study, and the terminology are different however. In a state transition system one is interested in interpreting the labels as actions, whereas in an ARS the focus is on how objects may be transformed (rewritten) into others.
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 to get c. Note also, that c is, in a sense, a "simplest" object in the system, since nothing can be applied to c to transform it any further. Such a property is clearly an important one.
Basic notions
Example 1 leads us to define some important notions in the general setting of an ARS. First we need some basic notions and notations.
Normal forms and the word problem
An object x in A is called reducible if there exist some other y in A and
One of the important problems that may be formulated in an ARS is the word problem: given x and y are they equivalent under
Joinability and the Church–Rosser property
A related, but weaker notion than the existence of normal forms is that of two objects being joinable: x and y are said joinable if there exists some z with the property that
An ARS is said to possess the Church-Rosser property if and only if
Notions of confluence
Various properties, simpler than Church-Rosser, are equivalent to it. The existence of these equivalent properties allows one to prove that a system is Church-Rosser with less work. Furthermore, the notions of confluence can be defined as properties of a particular object, something that's not possible for Church-Rosser. An ARS
Theorem. For an ARS the following three conditions are equivalent: (i) it has the Church-Rosser property, (ii) it is confluent, (iii) it is semi-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 Terese 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, 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 typical counterexample is
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.
The original 1942 proof of this result by Newman was rather complicated. It wasn't until 1980 that Huet published a much simpler proof exploiting the fact that when