Retour à la page du séminaire

16/04/99: Vincent van Oostrom (CWI et Utrecht University) Normalization in weakly orthogonal rewriting.

abstract

A rewrite sequence is said to be outermost-fair if every outermost redex is eventually eliminated. Outermost-fair rewriting is known to be (head-)normalising for almost orthogonal rewrite systems. We study (head-)normalisation for the larger class of weakly orthogonal rewrite systems. (Infinitary) normalisation is established and a counter-example against head-normalisation is given.