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 and 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. We recall that the complexity space as well as its dual are weightable quasi-metric spaces or, equivalently, partial metric spaces. Recently it has been shown 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 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. It has been 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.