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:
“This is what the Church is said to want, not party men, but sensible, temperate, sober, well-judging persons, to guide it through the channel of no-meaning, between the Scylla and Charybdis of Aye and No.”
—Cardinal John Henry Newman (1801–1890)