A stability theorem in rewriting theory
Paul-André Melliès · 2002
One key property of the /spl lambda/-calculus is that there exists a minimal computation (the head-reduction) M/spl rarr//sup e/V from a /spl lambda/-term M to the set of its head-normal forms. Minimality here means categorical "reflectivity" i.e. that every reduction path M/spl rarr//sup f/W to a head-normal form W factors (up to redex permutation) to a path M/spl rarr//sup e/V/spl rarr//sup h/W. This paper establishes a stability a la Berry or poly-reflectivity theorem [D, La, T] which extends the minimality property to rewriting systems with critical pairs. The theorem is proved in the setting of axiomatic rewriting systems where sets of head-normal forms are characterised by their frontier property in the spirit of J. Glauert and Z. Khasidashvili (1996).