Generalized ultrametric spaces : completion, topology, and powerdomains via the Yoneda embedding
Generalized ultrametric spaces are a common generalization of preorders and ordinary ultrametric spaces (Lawvere 1973, Rutten 1995). Combining Lawvere's (1973) enriched-categorical and Smyth' (1987, 1991) topological view on generalized (ultra)metric spaces, it is shown how to construct 1. completion, 2. topology, and 3. powerdomains for generalized ultrametric spaces. Restricted to the special cases of preorders and ordinary ultrametric spaces, these constructions yield, respectively: 1. chain completion and Cauchy completion; 2. the Alexandroff and the Scott topology, and the epsilon-ball topology; 3. lower, upper, and convex powerdomains, and the powerdomain of compact subsets. Interestingly, all constructions are formulated in terms of (an ultrametric version of) the Yoneda (1954) lemma.
|Formal Definitions and Theory (acm D.3.1), Modes of Computation (acm F.1.2), Semantics of Programming Languages (acm F.3.2)|
|Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (msc 68Q10), Semantics (msc 68Q55)|
|Department of Computer Science [CS]|
Bonsangue, M.M, van Breugel, F, & Rutten, J.J.M.M. (1995). Generalized ultrametric spaces : completion, topology, and powerdomains via the Yoneda embedding. Department of Computer Science [CS]. CWI.