Norm-weightable riesz spaces and the dual complexity space

The theory of complexity spaces has been introduced in [Sch95], where the applicability to the complexity analysis of Divide & Conquer algorithms has been discussed. This analysis has been based on the Banach Fixed Point Theorem, which has led to the study of biBanach spaces in [RS98]. In [RS96] we have introduced the dual complexity space as a convenient tool to carry out a mathematical analysis of complexity spaces (cf. also [RS98]). We recall that the complexity space as well as its dual are weightable quasi-metric spaces or, equivalently, partial metric spaces (cf. [Sch95], [RS96] as well as [Kün93], [KV94] and [Mat94]. Recently it has been shown in [Sch02a] that partial metric spaces correspond dually, in the context of Domain Theory, to semivaluation spaces. Here, we show that the dual complexity space is the negative cone of a biBanach norm-weightable Riesz space (e.g. [BOU52] and [RS98]) and characterize the class of norm-weightable Riesz spaces in terms of semivaluation spaces. In particular, we show that the quasi-norm of an element of such a Riesz space is the quasi-norm of its projection on the negative cone. Hence, quasi-norms are completely determined by partial metrics, justifying, in this context, O' Neill's analogy between these notions. In [Sch02a], it is shown that quasi-uniform semilattices arise naturally in Domain Theory, which motivates a generalization of our characterization to the context of norm-weightable quasi-uniform Riesz spaces.