Abstract rewriting system

Last updated

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 ; this definition can be further refined if we index (label) subsets of the binary relation. Despite its simplicity, an ARS is sufficient to describe important properties of rewriting systems like normal forms, termination, and various notions of confluence.

Contents

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). [1]

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. [2] (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). [3]

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 [2] or just reduction. [3] 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 , the notation used is (A, →1, →2).

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. [4]

Example 1

Suppose the set of objects is T = {a, b, c} and the binary relation is given by the rules ab, ba, ac, and bc. Observe that these rules can be applied to both a and b to get c. Furthermore, 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. [5]

Normal forms and the word problem

Solving the word problem: deciding if
x
-
*
y
{\displaystyle x{\stackrel {*}{\leftrightarrow }}y}
usually requires heuristic search (red, green), while deciding
x
|=
y
|
{\displaystyle x\downarrow =y\downarrow }
is straightforward (grey). For term rewriting systems the Knuth-Bendix completion algorithm enlarges
-
{\displaystyle \rightarrow }
to establish unique normal forms, if possible. Solving the word problem without and with completion svg.svg
Solving the word problem: deciding if usually requires heuristic search (red, green), while deciding is straightforward (grey). For term rewriting systems the Knuth-Bendix completion algorithm enlarges to establish unique normal forms, if possible.

An object x in A is called reducible if there exist some other y in A and ; otherwise it is called irreducible or a normal form. An object y is called a normal form of x if and y is irreducible. If x has a unique normal form, then this is usually denoted with . In example 1 above, c is a normal form, and . If every object has at least one normal form, the ARS is called normalizing.

One of the important problems that may be formulated in an ARS is the word problem: given x and y are they equivalent under ? This is a very general setting for formulating the word problem for the presentation of an algebraic structure. For instance, the word problem for groups is a particular case of an ARS word problem. Central to an "easy" solution for the word problem is the existence of unique normal forms: in this case two objects are equivalent under if and only if they have the same normal form. The word problem for an ARS is undecidable in general.

Joinability and the ChurchRosser 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 . From this definition, it's apparent one may define the joinability relation as , where is the composition of relations. Joinability is usually denoted, somewhat confusingly, also with , but in this notation the down arrow is a binary relation, i.e. we write if x and y are joinable.

An ARS is said to possess the Church-Rosser property if and only if implies for all objects x, y. Equivalently, the Church-Rosser property means that the reflexive transitive symmetric closure is contained in the joinability relation. Alonzo Church and J. Barkley Rosser proved in 1936 that lambda calculus has this property; [6] hence the name of the property. [7] (The fact that lambda calculus has this property is also known as the Church-Rosser theorem.) In an ARS with the Church-Rosser property the word problem may be reduced to the search for a common successor. In a Church-Rosser system, an object has at most one normal form; that is the normal form of an object is unique if it exists, but it may well not exist. In lambda calculus for instance, the expression (λx.xx)(λx.xx) does not have a normal form because there exists an infinite sequence of beta reductions (λx.xx)(λx.xx) → (λx.xx)(λx.xx) → ... [8]

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 is said to be,

Example of a locally-confluent rewrite system not having the Church-Rosser property Cyclic locally, but not globally confluent rewrite system.png
Example of a locally-confluent rewrite system not having the Church-Rosser property

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. [9]

Corollary. [10] In a confluent ARS if then

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. [11] Because of the above corollary, one may define a normal form y of x as an irreducible y with the property that . This definition, found in Book and Otto, is equivalent to common one given here in a confluent system, but it is more inclusive in a non-confluent ARS.

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 , which is locally confluent but not confluent (cf. picture).

Termination and convergence

An abstract rewriting system is said to be terminating or noetherian if there is no infinite chain . (This is just saying that the rewriting relation is a Noetherian relation.) In a terminating ARS, every object has at least one normal form, thus it is normalizing. The converse is not true. In example 1 for instance, there is an infinite rewriting chain, namely , even though the system is normalizing. A confluent and terminating ARS is called canonical, [12] or convergent. In a convergent ARS, every object has a unique normal form. But it is sufficient for the system to be confluent and normalizing for a unique normal to exist for every element, as seen in example 1.

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 is terminating we can apply well-founded induction. [13]

Notes

  1. Book and Otto, p. 9
  2. 1 2 Terese, p. 7,
  3. 1 2 Book and Otto, p. 10
  4. Terese, p. 7-8
  5. Baader and Nipkow, pp. 8-9
  6. Alonzo Church and J. Barkley Rosser. Some properties of conversion. Trans. AMS, 39:472-482, 1936
  7. Baader and Nipkow, p. 9
  8. S.B. Cooper, Computability theory, p. 184
  9. Baader and Nipkow, p. 11
  10. Baader and Nipkow, p. 12
  11. Terese p.11
  12. David A. Duffy (1991). Principles of Automated Theorem Proving. Wiley. Here: sect.7.2.1, p.153
  13. Harrison, p. 260

Further reading

Related Research Articles

Lambda calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics.

Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages. It is based on combinators which were introduced by Schönfinkel in 1920 with the idea of providing an analogous way to build up functions - and to remove any mention of variables - particularly in predicate logic. A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.

Church–Rosser theorem theorem

In mathematics and theoretical computer science, the Church–Rosser theorem states that, when applying reduction rules to terms in some typed variants of the lambda calculus, the ordering in which the reductions are chosen does not make a difference to the eventual result. More precisely, if there are two distinct reductions or sequences of reductions that can be applied to the same term, then there exists a term that is reachable from both results, by applying sequences of additional reductions. The theorem was proved in 1936 by Alonzo Church and J. Barkley Rosser, after whom it is named.

In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. The objects of focus for this article include rewriting systems. In their most basic form, they consist of a set of objects, plus relations on how to transform those objects.

The Knuth–Bendix completion algorithm is a semi-decision algorithm for transforming a set of equations into a confluent term rewriting system. When the algorithm succeeds, it effectively solves the word problem for the specified algebra.

Predicate transformer semantics were introduced by Edsger Dijkstra in his seminal paper "Guarded commands, nondeterminacy and formal derivation of programs". They define the semantics of an imperative programming paradigm by assigning to each statement in this language a corresponding predicate transformer: a total function between two predicates on the state space of the statement. In this sense, predicate transformer semantics are a kind of denotational semantics. Actually, in guarded commands, Dijkstra uses only one kind of predicate transformer: the well-known weakest preconditions.

The Kripke–Platek set theory with urelements (KPU) is an axiom system for set theory with urelements, based on the traditional (urelement-free) Kripke–Platek set theory. It is considerably weaker than the (relatively) familiar system ZFU. The purpose of allowing urelements is to allow large or high-complexity objects to be included in the theory's transitive models without disrupting the usual well-ordering and recursion-theoretic properties of the constructible universe; KP is so weak that this is hard to do by traditional means.

The simply typed lambda calculus, a form of type theory, is a typed interpretation of the lambda calculus with only one type constructor: that builds function types. It is the canonical and simplest example of a typed lambda calculus. The simply typed lambda calculus was originally introduced by Alonzo Church in 1940 as an attempt to avoid paradoxical uses of the untyped lambda calculus, and it exhibits many desirable and interesting properties.

Tarski's axioms, due to Alfred Tarski, are an axiom set for the substantial fragment of Euclidean geometry that is formulable in first-order logic with identity, and requiring no set theory. Other modern axiomizations of Euclidean geometry are Hilbert's axioms and Birkhoff's axioms.

In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a alphabet. Given a binary relation between fixed strings over the alphabet, called rewrite rules, denoted by , an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is , where , , , and are strings.

Confluence (abstract rewriting) property of abstract rewriting systems

In computer science, confluence is a property of rewriting systems, describing which terms in such a system can be rewritten in more than one way, to yield the same result. This article describes the properties in the most abstract setting of an abstract rewriting system.

In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements is the algorithmic problem of deciding whether two given representatives represent the same element of the set. The problem is commonly encountered in abstract algebra, where given a presentation of an algebraic structure by generators and relators, the problem is to determine if two expressions represent the same element; a prototypical example is the word problem for groups. Less formally, the word problem in an algebra is: given a set of identities E, and two expressions x and y, is it possible to transform x into y using the identities in E as rewriting rules in both directions? While answering this question may not seem hard, the remarkable result that emerges, in many important cases, is that the problem is undecidable.

In abstract rewriting, an object is in normal form if it cannot be rewritten any further. Depending on the rewriting system and the object, several normal forms may exist, or none at all.

Orthogonality as a property of term rewriting systems describes where the reduction rules of the system are all left-linear, that is each variable occurs only once on the left hand side of each reduction rule, and there is no overlap between them.

In mathematics, in the theory of rewriting systems, Newman's lemma, also commonly called the diamond lemma, states that a terminating abstract rewriting system (ARS), that is, one in which there are no infinite reduction sequences, is confluent if it is locally confluent. In fact a terminating ARS is confluent precisely when it is locally confluent.

The Abstract Rewriting Machine (ARM) is a virtual machine which implements term rewriting for minimal term rewriting systems.

In category theory, a span, roof or correspondence is a generalization of the notion of relation between two objects of a category. When the category has all pullbacks, spans can be considered as morphisms in a category of fractions.

Monoidal t-norm based logic, the logic of left-continuous t-norms, is one of t-norm fuzzy logics. It belongs to the broader class of substructural logics, or logics of residuated lattices; it extends the logic of commutative bounded integral residuated lattices by the axiom of prelinearity.

In mathematical logic, the ancestral relation of a binary relation R is its transitive closure, however defined in a different way, see below.

In computer science, a computation is said to diverge if it does not terminate or terminates in an exceptional state. Otherwise it is said to converge. In domains where computations are expected to be infinite, such as process calculi, a computation is said to diverge if it fails to be productive.