Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Reduction and unification in Lambda calculi with subtypes

Tobias NipkowContact Information and Zhenyu QianContact Information

(1)  Institut für Informatik, TU München, Postfach 20 24 20, W-8000 München 2, Germany
(2)  FB Informatik, Universität Bremen, Postfach 330440, W-2800 Bremen 33, Germany
Abstract
Reduction, equality and unification are studied for a family of simply typed lambda-calculi with subtypes. The subtype relation is required to relate base types only to base types and to satisfy some order-theoretic conditions. Constants are required to have a least type, i.e. ldquono overloadingrdquo. We define the usual beta and a subtype-dependent eegr-reduction. These are related to a typed equality relation and shown to be confluent in a certain sense.
A generic algorithm for pre-unification modulo betaeegr-conversion and an arbitrary subtype relation is presented. Furthermore it is shown that unification w.r.t. any subtype relation is universal.
Research supported by ESPRIT BRA 3245, Logical Frameworks, and an SERC Advanced Fellowship.
Research partially supported by ESPRIT Basic Research WG COMPASS 3264.
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: MPWEB25
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)