Newman's lemma

The lemma is purely combinatorial and applies to any relation. Owing to the context where it is commonly applied, it is stated below in the terminology of abstract rewriting systems (this is simply a set whose elements are called terms, equipped with a relation \to called reduction, and see the corresponding article for definitions of termination, confluence, local confluence and normal forms). == Eriksson's polygon property lemma ==

A related result was shown by Kimmo Eriksson in 1993. Recall that an abstract rewriting system is locally confluent if for any two reductions a \to b and a \to c, there exists d such that b \to^* d and c \to^* d. If additionally it is required that the reduction chains b \to^* d and c \to^* d have the same length, then the system is said to have the polygon property. Examples of rewriting systems with the polygon property include bubble sort and the chip-firing game. == References ==