Computing Publications

Publications Home » Normalization, Approximation, and...

Normalization, Approximation, and Semantics for Combinator Systems

Steffen van Bakel, Maribel

Journal Article
Theoretical Computer Science
Volume 290
pp.975–1019
January, 2003
Elsevier
DOI 10.1016/S0304-3975(02)00548-0
Abstract

This paper studies normalization of typeable terms and the relation between approximation semantics and filter models for Combinator Systems. It presents notions of approximants for terms, intersection type assignment, and reduction on type derivations; the last will be proved to be strongly normalizable. With this result, it is proved that every typeable term has an approximant with the same type, and a characterization of the normalization behaviour of terms using their assignable types is given. Then the two semantics are defined and compared, and it is shown that the approximants semantics is fully abstract but the filter semantics is not.

PDF of full publication (289 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (184 kilobytes)
(need help viewing GZipped Postscript files?)
BibTEX file for the publication
N.B.
Conditions for downloading publications from this site.
 

pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.