The largest Cartesian closed category of domains. (English) Zbl 0556.68017

Most of the studies in semantics of programming languages use ’domains’, i.e. \(\omega\)-algebraic cpo’s; the corresponding category \(\omega\) ACPO should be closed under function-space formation, reasonably. This is not true however. One does obtain Cartesian closure (the technical name of what we want) by considering the category \(\omega\) ACPO-CC of consistently complete domains, but now the powerdomain construction takes us outside the category.
Plotkin has conjectured that the category SFP which is an extension of consistently complete domains while still a subcategory of that of domains (and which is closed under powerdomain and function-space formation) is the largest category of domains closed under the constructions aforementioned. The paper under review proves this, making extensive use of the set of finite elements of a domain and of the set of minimal bounds of a poset. Finally some extensions are considered in case the notion of ’domain’ is modified either to effectively given domains or to continuous domains: the author conjectures some of the results to be still true.
Reviewer: M.Eytan


68Q99 Theory of computing
18D15 Closed categories (closed monoidal and Cartesian closed categories, etc.)
06B23 Complete lattices, completions
68Q55 Semantics in the theory of computing
Full Text: DOI


[1] Berry, G., Modéles complètement adéquates et stables des lambda-calculs typés, ()
[2] Hennessy, M.; Plotkin, G., Full abstraction for a simple parallel programming language, (), 108-120 · Zbl 0457.68006
[3] Markowsky, G., A motivation and generalization of Scott’s notion of a continuous lattice, (), 298-307
[4] Markowsky, G.; Rosen, B., Bases for chain-continuous posets, IBM J. res. develop, 20, 138-147, (1976) · Zbl 0329.06001
[5] Plotkin, G., A powerdomain construction, SIAM J. comput., 5, 452-488, (1976) · Zbl 0355.68015
[6] Scott, D., Cotinuous lattices, (), 97-136
[7] Smyth, M.B., Effectively given domains, Theoret. comput. sci., 5, 257-274, (1977) · Zbl 0429.03028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.