Geodesic
Computing complexity distances between algorithms
Kybernetika, Tome 39 (2003) no. 5, p. [569]

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

We introduce a new (extended) quasi-metric on the so-called dual p-complexity space, which is suitable to give a quantitative measure of the improvement in complexity obtained when a complexity function is replaced by a more efficient complexity function on all inputs, and show that this distance function has the advantage of possessing rich topological and quasi-metric properties. In particular, its induced topology is Hausdorff and completely regular. Our approach is applied to the measurement of distances between infinite words over the decimal alphabet and some advantages of our computations with respect to the ones that provide the classical Baire metric are discussed. Finally, we show that the application of fixed point methods to the complexity analysis of Divide and Conquer algorithms, presented by M. Schellekens (Electronic Notes in Theoret. Comput. Sci.1(1995)), can be also given from our approach.
Classification : 54E50, 54H25, 54H99, 68Q15, 68Q25
Keywords: invariant extended quasi-metric; complexity function; balanced quasi-metric; infinite word; Baire metric; contraction mapping; Divide & Conquer algorithm 
@article{KYB_2003__39_5_a5,
     author = {Romaguera, S. and S\'anchez-P\'erez, E. A. and Valero, O.},
     title = {Computing complexity distances between algorithms},
     journal = {Kybernetika},
     pages = {[569]},
     publisher = {mathdoc},
     volume = {39},
     number = {5},
     year = {2003},
     mrnumber = {2042342},
     zbl = {1249.54069},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2003__39_5_a5/}
}
TY  - JOUR
AU  - Romaguera, S.
AU  - Sánchez-Pérez, E. A.
AU  - Valero, O.
TI  - Computing complexity distances between algorithms
JO  - Kybernetika
PY  - 2003
SP  - [569]
VL  - 39
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2003__39_5_a5/
LA  - en
ID  - KYB_2003__39_5_a5
ER  - 
%0 Journal Article
%A Romaguera, S.
%A Sánchez-Pérez, E. A.
%A Valero, O.
%T Computing complexity distances between algorithms
%J Kybernetika
%D 2003
%P [569]
%V 39
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2003__39_5_a5/
%G en
%F KYB_2003__39_5_a5
Romaguera, S.; Sánchez-Pérez, E. A.; Valero, O. Computing complexity distances between algorithms. Kybernetika, Tome 39 (2003) no. 5, p. [569]. http://geodesic.mathdoc.fr/item/KYB_2003__39_5_a5/