Geodesic
Computing complexity distances between algorithms
Kybernetika, Tome 39 (2003) no. 5, pp. 569-582 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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--582},
     year = {2003},
     volume = {39},
     number = {5},
     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
EP  - 582
VL  - 39
IS  - 5
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-582
%V 39
%N 5
%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, pp. 569-582. http://geodesic.mathdoc.fr/item/KYB_2003_39_5_a5/

[1] Bakker J. W. de, Vink E. P. de: Denotational models for programming languages: applications of Banach’s fixed point theorem. Topology Appl. 85 (1998), 35–52 | DOI | MR | Zbl

[2] Ćirić L.: Periodic and fixed point theorems in a quasi-metric space. J. Austral. Math. Soc. Ser. A 54 (1993), 80–85 | DOI | MR | Zbl

[3] Doitchinov D.: On completeness in quasi-metric spaces. Topology Appl. 30 (1988), 127–148 | DOI | MR | Zbl

[4] Engelking R.: General Topology. Polish Sci. Publ., Warsaw 1977 | MR | Zbl

[6] Fletcher P., Lindgren W. F.: Quasi–Uniform Spaces. Marcel Dekker, 1982 | MR | Zbl

[7] García-Raffi L. M., Romaguera, S., Sánchez-Pérez E. A.: Sequence spaces and asymmetric norms in the theory of computational complexity. Math. Comput. Modelling 36 (2002), 1–11 | DOI | MR | Zbl

[8] Giles J. R.: Introduction to the Analysis of Metric Spaces. (Austral. Math. Soc. Lecture Series no. 3.) Cambridge Univ. Press, Cambridge 1987 | MR | Zbl

[9] Hicks T. L.: Fixed point theorems for quasi-metric spaces. Math. Japon. 33 (1988), 231–236 | MR | Zbl

[10] Jachymski J.: A contribution to fixed point theory in quasi-metric spaces. Publ. Math. Debrecen 43 (1993), 283–288 | MR | Zbl

[11] Kahn G.: The semantics of a simple language for parallel processing. In: Proc. IFIP Congress, Elsevier and North-Holland, Amsterdam 1974, pp. 471–475 | MR

[12] Keimel K., Roth W.: Ordered Cones and Approximation. Springer–Verlag, Berlin 1992 | MR | Zbl

[13] Kopperman R. D.: Lengths on semigroups and groups. Semigroup Forum 25 (1982), 345–360 | DOI | MR | Zbl

[14] Künzi H. P. A.: Nonsymmetric distances and their associated topologies: About the origin of basic ideas in the area of asymmetric topology. In: Handbook of the History of General Topology, Volume 3 (C. E. Aull and R. Lowen eds.), Kluwer, Dordrecht 2001, pp. 853–968 | MR

[15] Künzi H. P. A., Ryser C.: The Bourbaki quasi-uniformity. Topology Proc. 20 (1995), 161–183 | MR | Zbl

[16] Lecomte P., Rigo M.: On the representation of real numbers using regular languages. Theory Comput. Systems 35 (2002), 13–38 | MR | Zbl

[17] Matthews S. G.: Partial metric topology. In: Proc. 8th Summer Conference on General Topology and Applications, Ann. New York Acad. Sci. 728 (1994), 183–197 | DOI | MR | Zbl

[18] Reilly I. L., Subrahmanyam P. V.: Some fixed point theorems. J. Austral. Math. Soc. Ser. A 53 (1992), 304–312 | DOI | MR | Zbl

[19] Reilly I. L., Subrahmanyam P. V., Vamanamurthy M. K.: Cauchy sequences in quasi-pseudo-metric spaces. Monatsh. Math. 93 (1982), 127–140 | DOI | MR | Zbl

[20] Romaguera S., Sanchis M.: Semi-Lipschitz functions and best approximation in quasi-metric spaces. J. Approx. Theory 103 (2000), 292–301 | DOI | MR | Zbl

[21] Romaguera S., Schellekens M.: Quasi-metric properties of complexity spaces. Topology Appl. 98 (1999), 311–322 | DOI | MR | Zbl

[22] Romaguera S., Schellekens M.: Duality and quasi-normability for complexity spaces. Appl. Gen. Topology 3 (2002), 91–112 | MR | Zbl