In mathematics, in the area of order theory, Newman's lemma, also commonly called the diamond lemma, states that every preorder with finite chains and possessing the diamond property has a bijection between the graphs of the preorder, and its minimal elements.
Equivalently, as commonly stated in the theory of rewriting systems, 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.
Today, this is seen as a purely combinatorial result based on well-foundedness due to a proof of Gérard Huet in 1980. Newman's original proof was considerably more complicated.
An earlier proof of the theorem was given by Church and Rosser.
Read more about Newman's Lemma: Diamond Lemma
Famous quotes containing the word newman:
“Can you read my mind? Do you know what it is that you do to me?”
—David Newman (b. 1937)