Towards A Proof Theory Of Rewriting

Abstract: "This paper describes the simply-typed 2-[lambda]- calculus, a language with three levels: types, terms and rewrites. The types and terms are those of the simply-typed [lambda]-calculus, and the rewrites are expressions denoting sequences of [beta]-reductions and [eta]- expansions. An equational theory is imposed on the rewrites, based on 2- categorical justifications, and the word problem for this theory is solved by finding a canonical expression in each equivalence class. The canonical form of rewrites allows us to prove several properties of the calculus, including a strong form of confluence and a classification of the long-[beta]-[eta]-normal forms in terms of their rewrites. Finally we use these properties as the basic definitions of a theory of categorical rewriting, and find that the expected relationships between confluence, strong normalisation and normal forms hold."