Normalization, approximation, and semantics for combinator systems

✍ Scribed by Steffen van Bakel; Maribel Fernández

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 400 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00548-0

✦ Synopsis

This paper studies normalization of typeable terms and the relation between approximation semantics and ÿlter 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 deÿned and compared, and it is shown that the approximants semantics is fully abstract but the ÿlter semantics is not.