On Banach fixed point theorems for partial metric spaces

Given a partial metric space (X,p), we use (BX, ⊑_dp) to denote the poset of formal balls of the associated quasi-metric space (X,d_p). We obtain characterisations of complete partial metric spaces and sup-separable complete partial metric spaces in terms of domain-theoretic properties of (BX, ⊑_dp). In particular, we prove that a partial metric space (X,p) is complete if and only if the poset (BX, ⊑_dp) is a domain. Furthermore, for any complete partial metric space (X,p), we construct a Smyth complete quasi-metricqonBXthat extends the quasi-metricd_psuch that both the Scott topology and the partial order ⊑_dpare induced byq. This is done using the partial quasi-metric concept recently introduced and discussed by H. P. Künzi, H. Pajoohesh and M. P. Schellekens (Künziet al. 2006). Our approach, which is inspired by methods due to A. Edalat and R. Heckmann (Edalat and Heckmann 1998), generalises to partial metric spaces the constructions given by R. Heckmann (Heckmann 1999) and J. J. M. M. Rutten (Rutten 1998) for metric spaces.

We characterise those quasi-metric spaces (X, d) whose poset BX of formal balls satisfies the condition (*) From this characterisation, we then deduce that a quasi-metric space (X, d) is Smyth-complete if and only if BX is a dcpo satisfying condition (*). We also give characterisations in terms of formal balls for sequentially Yoneda complete quasi-metric spaces and for Yoneda complete T₁ quasi-metric spaces. Finally, we discuss several properties of the Heckmann quasi-metric on the formal balls of any quasi-metric space.

Multi-robot task allocation is one of the main problems to address in order to design a multi-robot system, very especially when robots form coalitions that must carry out tasks before a deadline. A lot of factors affect the performance of these systems and among them, this paper is focused on the physical interference effect, produced when two or more robots want to access the same point simultaneously. To our best knowledge, this paper presents the first formal description of multi-robot task allocation that includes a model of interference. Thanks to this description, the complexity of the allocation problem is analyzed. Moreover, the main contribution of this paper is to provide the conditions under which the optimal solution of the aforementioned allocation problem can be obtained solving an integer linear problem. The optimal results are compared to previous allocation algorithms already proposed by the first two authors of this paper and with a new method proposed in this paper. The results obtained show how the new task allocation algorithms reach up more than an 80% of the median of the optimal solution, outperforming previous auction algorithms with a huge reduction of the execution time.

In 1994, Matthews introduced the notion of partial metric space with the aim of providing a quantitative mathematical model suitable for program verification. Concretely, Matthews proved a partial metric version of the celebrated Banach fixed point theorem which has become an appropriate quantitative fixed point technique to capture the meaning of recursive denotational specifications in programming languages. In this paper we show that a few assumptions in statement of Matthews fixed point theorem can be relaxed in order to provide a quantitative fixed point technique useful to analyze the meaning of the aforementioned recursive denotational specifications in programming languages. In particular, we prove a new fixed point theorem for self-mappings between partial metric spaces in which the completeness has been replaced by 0-completeness and the contractive condition has been weakened in such a way that the new one best fits the requirements of practical problems in denotational semantics. Moreover, we provide examples that show that the hypothesis in the statement of our new result cannot be weakened. Finally, we show the potential applicability of the developed theory by means of analyzing a few concrete recursive denotational specifications, some of them admitting a unique meaning and others supporting multiple ones.