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.
|
 |
Reduction and unification in Lambda calculi with subtypes
| |
|
Reduction and unification in Lambda calculi with subtypes
Tobias Nipkow1 and Zhenyu Qian2 
| (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  -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.  no overloading  . We define the usual  and a subtype-dependent  -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   -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)
 References secured to subscribers.
|
|
|
|
|
|