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 sequences, is confluent if it is locally confluent. In fact a terminating ARS is confluent precisely when it is locally confluent.[1]

Equivalently, for every binary relation with no decreasing infinite chains and satisfying a weak version of the diamond property, there is a unique minimal element in every connected component of the relation considered as a graph.

Today, this is seen as a purely combinatorial result based on well-foundedness due to a proof of Gérard Huet in 1980.[2] Newman's original proof was considerably more complicated.[3]

Diamond lemma

In general, Newman's lemma can be seen as a combinatorial result about binary relations → on a set A (written backwards, so that ab means that b is below a) with the following two properties:

If the above two conditions hold, then the lemma states that → is confluent: whenever a b and a c, there is an element d such that b d and c d. In view of the termination of →, this implies that every connected component of → as a graph contains a unique minimal element a, moreover b a for every element b of the component.[4]

Notes

  1. Franz Baader, Tobias Nipkow, (1998) Term Rewriting and All That, Cambridge University Press ISBN 0-521-77920-0
  2. Gérard Huet, "Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems", Journal of the ACM (JACM), October 1980, Volume 27, Issue 4, pp. 797 - 821.
  3. Harrison, p. 260, Paterson(1990), p. 354.
  4. Paul M. Cohn, (1980) Universal Algebra, D. Reidel Publishing, ISBN 90-277-1254-9 (See pp. 25-26)

References

Textbooks

External links

This article is issued from Wikipedia - version of the Tuesday, March 22, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.