In
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
and
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated ARS) is a
formalism
Formalism may refer to:
* Form (disambiguation)
* Formal (disambiguation)
* Legal formalism, legal positivist view that the substantive justice of a law is a question for the legislature rather than the judiciary
* Formalism (linguistics)
* Scient ...
that captures the quintessential notion and properties of
rewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a well-formed formula, formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewr ...
systems. In its simplest form, an ARS is simply a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
(of "objects") together with a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
, 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
Termination may refer to:
Science
*Termination (geomorphology), the period of time of relatively rapid change from cold, glacial conditions to warm interglacial condition
*Termination factor, in genetics, part of the process of transcribing RNA ...
, and various notions of
confluence
In geography, a confluence (also: ''conflux'') occurs where two or more flowing bodies of water join to form a single channel. A confluence can occur in several configurations: at the point where a tributary joins a larger river (main stem); o ...
.
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
Gérard Pierre Huet (; born 7 July 1947) is a French computer scientist, linguist and mathematician. He is senior research director at INRIA and mostly known for his major and seminal contributions to type theory, programming language theory and ...
(1980).
Definition
An ''abstract reduction system'' (''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 the term ''abstract rewriting system'' as well.
[Terese, p. 7,] (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).
[Book and Otto, p. 10]
An ARS is a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
''A'', whose elements are usually called objects, together with a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
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
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
and commutativity
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
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
In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled with ...
, 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
In theoretical computer science, a transition system is a concept used in the study of computation. It is used to describe the potential behavior of discrete systems. It consists of states and transitions between states, which may be labeled with ...
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'' = 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''. Furthermore, nothing can be applied to ''c'' to transform it any further. Such a property is clearly an important one.
Basic notions
First define some basic notions and notations.
* is the transitive closure
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite s ...
of .
* is the reflexive transitive closure
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but ...
of , i.e. the transitive closure
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite s ...
of , where = is the identity relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
. Equivalently, is the smallest preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
containing .
* is the symmetric closure In mathematics, the symmetric closure of a binary relation R on a set X is the smallest symmetric relation on X that contains R.
For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the ...
of , that is, i.e. the union of the relation → with its converse relation
In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent& ...
.
* is the reflexive transitive symmetric closure
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but n ...
of , i.e. the transitive closure
In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite s ...
of . Equivalently, is the smallest equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
containing .
Normal forms
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''.
Joinability
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 . From this definition, it's apparent one may define the joinability relation as , where is the composition of relations
In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the calculus of relations, the composition of relations is called relative multiplica ...
. 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.
The Church–Rosser property and notions of confluence
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
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scienc ...
and J. Barkley Rosser
John Barkley Rosser Sr. (December 6, 1907 – September 5, 1989) was an American logician, a student of Alonzo Church, and known for his part in the Church–Rosser theorem, in lambda calculus. He also developed what is now called the "Rosser siev ...
proved in 1936 that lambda calculus
Lambda calculus (also written as ''λ''-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 ...
has this property; hence the name of the property. 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.
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,
* ''confluent'' if and only if for all ''w'', ''x'', and ''y'' in ''A'', implies . Roughly speaking, confluence says that no matter how two paths diverge from a common ancestor (''w''), the paths are joining at ''some'' common successor. This notion may be refined as property of a particular object ''w'', and the system called confluent if all its elements are confluent.
* ''semi-confluent'' if and only if for all ''w'', ''x'', and ''y'' in ''A'', implies . This differs from confluence by the single step reduction from ''w'' to ''x''.
* ''locally confluent'' if and only if for all ''w'', ''x'', and ''y'' in ''A'', implies . This property is sometimes called ''weak confluence''.
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 then
* If both ''x'' and ''y'' are normal forms, then ''x'' = ''y''.
* If ''y'' is a normal form, 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. 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 the 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 mathematics, the adjective Noetherian is used to describe objects that satisfy an ascending or descending chain condition on certain kinds of subobjects, meaning that certain ascending or descending sequences of subobjects must have finite lengt ...
.) 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, 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 In mathematics, in the theory of rewriting systems, Newman's lemma, also commonly called the diamond lemma, states that a terminating (or strongly normalizing) abstract rewriting system (ARS), that is, one in which there are no infinite reduction ...
): 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
In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s  ...
.[Harrison, p. 260]
See also
* Word problem (mathematics)
In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other ...
- particularly the section on abstract rewriting systems
Notes
Further reading
* A textbook suitable for undergraduates.
* Nachum Dershowitz
Nachum Dershowitz is an Israeli computer scientist, known e.g. for the Dershowitz–Manna ordering and the multiset path ordering used to prove termination of term rewrite systems.
He obtained his B.Sc. summa cum laude in 1974 in Computer Scie ...
and Jean-Pierre Jouannaud
Jean-Pierre Jouannaud is a French computer scientist, known for his work in the area of term rewriting.
He was born on 21 May 1947 in Aix-les-Bains (France).
From 1967 to 1969 he visited the Ecole Polytechnique (Paris).
In 1970, 1972, and 1977, ...
br>''Rewrite Systems''
Chapter 6 in Jan van Leeuwen
Jan van Leeuwen (born December 17, 1946, in Waddinxveen) is a Dutch computer scientist and Emeritus professor of computer science at the Department of Information and Computing Sciences at Utrecht University. (Ed.), ''Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics.'', Elsevier and MIT Press, 1990, , pp. 243–320. The preprint
In academic publishing, a preprint is a version of a scholarly or scientific paper that precedes formal peer review and publication in a peer-reviewed scholarly or scientific journal. The preprint may be available, often as a non-typeset versio ...
of this chapter is freely available from the authors, but it misses the figures.
* Ronald V. Book
Ronald Vernon Book (March 5 1937 – May 28, 1997 in Santa Barbara, California) was a theoretical computer scientist. He published more than 150 papers in scientific journals.
His papers are of great impact for computational complexity theory
In ...
and Friedrich Otto, ''String-rewriting Systems'', Springer (1993), . Chapter 1, "Abstract reduction systems"
* Marc Bezem Marc or MARC may refer to:
People
* Marc (given name), people with the first name
* Marc (surname), people with the family name
Acronyms
* MARC standards, a data format used for library cataloging,
* MARC Train, a regional commuter rail system o ...
, Jan Willem Klop
Jan Willem Klop (born 1945) is a professor of applied logic at Vrije Universiteit in Amsterdam. He holds a Ph.D. in mathematical logic from Utrecht University. Klop is known for his work on the Algebra of Communicating Processes, co-author of ''T ...
, Roel de Vrijer Roel son of almighty Zeus and beautiful mortal Alcmene, was the strongest man who ever lived. Now when Roel was eight months old, he woke one night to find a monstrous snake had coiled itself around him. Instead of crying out, baby Roel wrapped his ...
("Terese"), ''Term rewriting systems'', Cambridge University Press, 2003, , Chapter 1. This is a comprehensive monograph. It uses, however, a fair deal of notations and definitions not commonly encountered elsewhere. For instance the Church–Rosser property is defined to be identical with confluence.
* John Harrison
John Harrison ( – 24 March 1776) was a self-educated English Carpentry, carpenter and clockmaker who invented the marine chronometer, a long-sought-after device for solving the History of longitude, problem of calculating longitude while at s ...
, ''Handbook of Practical Logic and Automated Reasoning'', Cambridge University Press, 2009, {{ISBN, 978-0-521-89957-4, chapter 4 "Equality". Abstract rewriting from the practical perspective of solving problems in equational logic First-order equational logic consists of quantifier-free terms of ordinary first-order logic, with equality as the only predicate symbol. The model theory of this logic was developed into universal algebra by Birkhoff, Grätzer, and Cohn. It was l ...
.
* Gérard Huet
Gérard Pierre Huet (; born 7 July 1947) is a French computer scientist, linguist and mathematician. He is senior research director at INRIA and mostly known for his major and seminal contributions to type theory, programming language theory and ...
, ''Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems'', Journal of the ACM (JACM
The ''Journal of the ACM'' is a Peer review, peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is ...
), October 1980, Volume 27, Issue 4, pp. 797–821. Huet's paper established many of the modern concepts, results and notations.
* Sinyor, J.
"The 3x+1 Problem as a String Rewriting System"
''International Journal of Mathematics and Mathematical Sciences'', Volume 2010 (2010), Article ID 458563, 6 pages.
Formal languages
Logic in computer science
Rewriting systems