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