On the completeness of order-theoretic models of the lambda-calculus

Furio Honsell, Gordon D. Plotkin

Research output: Contribution to journalArticlepeer-review

Abstract

Scott discovered his domain-theoretic models of the λ -calculus, isomorphic to their function space, in 1969. A natural completeness problem then arises: whether any two terms equal in all Scott models are convertible. There is also an analogous consistency problem: whether every equation between two terms, consistent with the λ -calculus, has a Scott model. We consider such questions for wider sets of sentences and wider classes of models, the pointed (completely) partially ordered ones. A negative result for a set of sentences shows the impossibility of finding Scott models for that class; a positive result gives evidence that there might be enough Scott models. We find, for example, that the order-extensional pointed ω -cpo models are complete for Π1-sentences with positive matrices, whereas the consistency question for Σ1-sentences with equational matrices depends on the consistency of certain critical sentences asserting the existence of certain functions analogous to the generalized Mal’cev operators first considered in the context of the λ-calculus by Selinger.
Original languageEnglish
Pages (from-to)583-594
Number of pages12
JournalTheoretical Computer Science
Volume207
Issue number5
DOIs
Publication statusPublished - 2009

Fingerprint Dive into the research topics of 'On the completeness of order-theoretic models of the lambda-calculus'. Together they form a unique fingerprint.

Cite this