Basic Normalization

Nao Hirokawa

(JAIST, Naomi, Kanazawa)

The Normalization Theorem (O'Donnell 1977) states that for every left-normal orthogonal rewrite system, the leftmost outermost strategy reduces any term to the normal form if it exists. Although the theorem ensures the normalization property of important systems such as Combinatory Logic, the left-normality condition rules out most of functional programs. We revisit the problem to seek a solution for normalization of the leftmost outermost strategy. This work is based on joint work with Aart Middeldorp and Georg Moser.

Thursday 17th March 2016, 15:00
The Board Room
Department of Computer Science