DocumentCode :
1956063
Title :
A stability theorem in rewriting theory
Author :
Mellies, Paul-Andre
Author_Institution :
Dept. of Comput. Sci., Edinburgh Univ., UK
fYear :
1998
fDate :
21-24 Jun 1998
Firstpage :
287
Lastpage :
298
Abstract :
One key property of the λ-calculus is that there exists a minimal computation (the head-reduction) M→eV from a λ-term M to the set of its head-normal forms. Minimality here means categorical “reflectivity” i.e. that every reduction path M→fW to a head-normal form W factors (up to redex permutation) to a path M→eV→hW. 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)
Keywords :
lambda calculus; rewriting systems; stability; axiomatic rewriting systems; head-normal forms; minimal computation; minimality; poly-reflectivity theorem; reduction path; rewriting theory; stability theorem; Calculus; Carbon capture and storage; Computational modeling; Computer science; Concrete; Petri nets; Stability; Turing machines;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Logic in Computer Science, 1998. Proceedings. Thirteenth Annual IEEE Symposium on
Conference_Location :
Indianapolis, IN
ISSN :
1043-6871
Print_ISBN :
0-8186-8506-9
Type :
conf
DOI :
10.1109/LICS.1998.705665
Filename :
705665
Link To Document :
بازگشت