On quasi-metric aggregation functions and fixed point theorems
The problem of how to merge, by means of a function, a family of metrics into a single one was studied deeply by J. Borsik and J. Dobos [On a product of metric spaces, Math. Slovaca 31 (1981) 193-205]. Motivated by the utility of quasi-metrics in Computer Science, the Borsik and Dobos study was extended to the quasi-metric context in such a way that a general description of how to combine through a function a family of quasi-metrics in order to obtain a single one as output was provided by G. Mayor and O. Valero [Aggregation of asymmetric distances in Computer Science, Inform. Sci. 180 (2010) 803-812]. In this paper, inspired by the fact that fixed point theory provides an efficient tool in many fields of applied sciences, we have proved fixed point theorems for a new type of contractions, that we have called projective Phi-contractions, defined between quasi-metric spaces that have been obtained via the so-called quasi-metric aggregation functions. Moreover, we show that the new fixed point results are useful to discuss, on the one hand, the complexity of a collection of recursive programs whose running times of computing hold a coupled system of recurrence equations and, on the other hand, to analyze simultaneously the complexity and the correctness of recursive algorithms that perform a computation by means of a recursive denotational specification. (C) 2012 Elsevier B.V. All rights reserved.
quasi-metric aggregation function metric homogeneous function projective contraction projective phi-contraction asymptotic complexity analysis denotational semantics