In abstract rewriting, a normal form is an element of the system which cannot be rewritten any further. Stated formally, for some reduction relation ⋅ → ⋅ over X a term t in X is a normal form if there does not exist a term t′ in X such that t → t′.
Consider the basic term rewriting system with reduction rule ρ : g(x, y) → x. The term g(g(4, 2), g(3, 1)) has the following reduction sequence, according to the usual outermost strategy, that is, if the reduction rule is applied to each outermost occurrence of g:
There is no rule that permits us to rewrite 4, so 4 is a normal form for this term rewriting system.
Related concepts refer to the possibility of rewriting an element into normal form. Weak normalization means that some element can be rewritten into a normal form. Strong normalization means that any reduction sequence starting from some element terminates. We say that the system is weakly normalizing (or strongly normalizing) if all elements are weakly normalizing (resp. strongly normalizing).
Newman's lemma states that if an abstract reduction system A is strongly normalizing and is weakly confluent, then A is in fact confluent. The result enables us to further generalize the critical pair lemma.
Famous quotes containing the words normal and/or form:
“Cant is always rather nauseating; but before we condemn political hypocrisy, let us remember that it is the tribute paid by men of leather to men of God, and that the acting of the part of someone better than oneself may actually commit one to a course of behaviour perceptibly less evil than what would be normal and natural in an avowed cynic.”
—Aldous Huxley (1894–1963)
“I don’t think of form as a kind of architecture. The architecture is the result of the forming. It is the kinesthetic and visual sense of position and wholeness that puts the thing into the realm of art.”
—Roy Lichtenstein (b. 1923)