Stable Results and Relative Normalisation

J. R. W. Glauert, J. R. Kennaway, Z. Khasidashvili

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

In orthogonal expression reduction systems, a common generalization of term rewriting and ?-calculus, we extend the concepts of normalization and needed reduction by considering, instead of the set of normal forms, a set S of 'results'. When S satisfies some simple axioms which we call stability, we prove the corresponding generalizations of some fundamental theorems: the existence of needed redexes, that needed reduction is normalizing, the existence of minimal normalizing reductions, and the optimality theorem.
Original languageEnglish
Pages (from-to)323-348
Number of pages26
JournalJournal of Logic and Computation
Volume10
Issue number3
DOIs
Publication statusPublished - 2000

Cite this