Hyperspaces of a weightable quasi-metric space: Application to models in the theory of computation

Abstract

It is well known that both weightable quasi-metrics and the Hausdorff distance provide efficient tools in several areas of Computer Science. This fact suggests, in a natural way, the problem of when the upper and lower Hausdorff quasi-pseudo-metrics of a weightable quasi-metric space (X,d) are weightable. Here we discuss this problem. Although the answer is negative in general, we show, however, that it is positive for several nice classes of (nonempty) subsets of X. Since the construction of these classes depends, to a large degree, on the specialization order of the quasi-metric d, we are able to apply our results to some distinguished quasi-metric models that appear in theoretical computer science and information theory, like the domain of words, the interval domain and the complexity space.