Show simple item record

dc.contributor.advisorPlotkin, Gordon
dc.contributor.authorMoggi, Eugenio
dc.date.accessioned2004-03-08T10:26:59Z
dc.date.available2004-03-08T10:26:59Z
dc.date.issued1988-07
dc.identifier.urihttp://hdl.handle.net/1842/419
dc.description.abstractThis thesis investigates various formal systems for reasoning about partial functions or partial elements, with particular emphasis on lambda calculi for partial functions. Beeson's (intuitionistic) logic of partial terms (LPT) is taken as the basic formal system and some of its metamathematical properties are established (for later application). Three different flavours of Scott's logic of partial elements (LPE) are considered and it is shown that they are conservative extensions of LPT. This result, we argue, corroborates the choice of LPT as the basic formal system. Variants of LPT are introduced for reasoning about partial terms with a restriction operator ↾, monotonic partial functions (monLPT), lambda-terms λ_p-calculus) and λY-terms λ_pμY-calculus). The expressive powers of some (in)equational fragments are compared in LPT and its variants. Two equational formal systems are related to some of the logics above: Obtulowicz's p-equational logic is related to LPT+↾ and Plotkin's λ_v-calculus is related to one flavour of LPE. The deductive powers of LPT and its variants are compared, using various techniques (among them logical relations). The main conclusion drawn from this comparison is that there are four different lambda calculi for partial functions: intuitionistic or classical, partial or monotonic partial functions. An (in)equational presentation of the intuitionistic lambda calculus for (monotonic) partial functions is given as an extension of p-equational logic. We conjecture that there is no equational presentation of the classical λ_p-calculus. Via a special kind of diamond property, the (in)equational formal system is characterized in terms of β-reduction for partial functions and some decidability problems are solved.en
dc.contributor.sponsorUniversity of Edinburghen
dc.format.extent15554037 bytes
dc.format.extent1795183 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen
dc.publisherUniversity of Edinburgh. College of Science and Engineering. School of Informatics.en
dc.titleThe Partial Lambda Calculusen
dc.typeThesis or Dissertation
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD Doctor of Philosophyen


Files in this item

This item appears in the following Collection(s)

Show simple item record