A generalized ultrametric space is an ordinary ultrametric space in which the distance need not be symmetric, and where different elements may have distance 0. Our interest in generalized ultrametric spaces is primarily motivated by the following observations: 1. (possibly nondeterministic) transition systems can be naturally endowed with a generalized ultrametric that captures their operational behavior in terms of simulations; 2. the category of generalized ultrametric spaces contains both the categories of preorders and of ordinary ultrametric spaces as full subcategories. A theory of generalized ultrametric spaces is developed along the lines of the work by Smyth and Plotkin (1982) and America and Rutten (1989), such that its restriction to preorders and ordinary ultrametric spaces yields (more and less) familiar facts. Our work has in common with other recent work along the same lines---by Flagg and Kopperman, and Wagner---that it is directly based on Lawvere's V-categorical interpretation of metric spaces, and uses results on quasimetrics by Smyth. It is different in being far less general, and consequently a number of new results, specific for generalized ultrametric spaces, is obtained. In particular, domain equations are solved by means of metric adjoint pairs, and the notions of (generalized) totally-boundedness and bifinite (or `SFU') domain are introduced and characterized.

, ,
,
CWI
Department of Computer Science [CS]
Computational models

Rutten, J. (1995). Elements of generalized ultrametric domain theory. Department of Computer Science [CS]. CWI.