A category of compositional domain-models for separable Stone spaces

Fabio Alessi (1) - Paolo Baldan (2) - Furio Honsell (1)

(1) Dipartimento di Matematica e Informatica,
Università di Udine (Italy)

(2) Dipartimento di Informatica,
Università di Pisa (Italy)

{alessi,honsell}@dimi.uniud.it             baldan@di.unipi.it

Abstract:

In this paper we introduce SFP^M, a category of SFP domains which provides very satisfactory domain-models, i.e. ``partializations'', of separable Stone spaces (2-Stone spaces). More specifically, SFP<sup>M</sup> is a subcategory of SFP<sup>ep</sup> , closed under direct limits as well as many constructors, such as lifting, sum, product and Plotkin powerdomain.  SFP<sup>M</sup> is ``structurally well behaved'', in the sense that the functor MAX , which associates to each object of SFP^M the Stone space of its maximal elements, is compositional with respect to the constructors above, and -continuous. A correspondence can be established between these constructors over SFP^M and appropriate constructors on Stone spaces, whereby SFP domain-models of Stone spaces defined as solutions of a vast class of recursive equations in 2-Stone , can be obtained simply by solving the corresponding equations in  SFP^M. Moreover any continuous function between two 2-Stone spaces can be extended to a continuous function between any two SFP^M domain-models of the original spaces. The category SFP^M does not include all the SFP's with a 2-Stone space of maximal elements (CSFP's). We show that the CSFP's can be characterized precisely as suitable retracts of SFP^M objects. Then the results proved for SFP^M easily extends to the wider category having CSFP's as objects.

Using SFP^M , we explain two classical ``partializations'' of the space of finitary hypersets (the hyperuniverse  [3]) based on SFP domains (see [1, 2], [4]). We also show that these two domains are not isomorphic, thus providing a negative answer to a problem raised in [4].

Keywords. Denotational semantics, domain theory, domain models, Stone spaces.
 
 

References

1

 S. Abramsky. A cook's tour of the finitary non-well-founded sets. Unpublished Manuscript, 1988.

2

 S. Abramsky. A domain equation for bisimulation. Information and Computation, 92(2):161-218, 1991.

3

 M. Forti, F. Honsell, and M. Lenisa. Axiomatic characterization of hyperuniverses and applications.

Annals of the New York Academy of Sciences, 806:140-163, 1996.

4

 M.W. Mislove, L.S. Moss, and F.J. Oles. Non-well founded sets modeled as ideal fixed points.

Information and Computation,  93(1):16-54, 1991.