# Computing complexity distances between algorithms

Salvador Romaguera; Enrique A. Sánchez-Pérez; Oscar Valero

Kybernetika (2003)

- Volume: 39, Issue: 5, page [569]-582
- ISSN: 0023-5954

## Access Full Article

top## Abstract

top## How to cite

topRomaguera, Salvador, Sánchez-Pérez, Enrique A., and Valero, Oscar. "Computing complexity distances between algorithms." Kybernetika 39.5 (2003): [569]-582. <http://eudml.org/doc/33666>.

@article{Romaguera2003,

abstract = {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.},

author = {Romaguera, Salvador, Sánchez-Pérez, Enrique A., Valero, Oscar},

journal = {Kybernetika},

keywords = {invariant extended quasi-metric; complexity function; balanced quasi-metric; infinite word; Baire metric; contraction mapping; Divide & Conquer algorithm; invariant extended quasi-metric; complexity function; balanced quasi-metric; infinite word; Baire metric},

language = {eng},

number = {5},

pages = {[569]-582},

publisher = {Institute of Information Theory and Automation AS CR},

title = {Computing complexity distances between algorithms},

url = {http://eudml.org/doc/33666},

volume = {39},

year = {2003},

}

TY - JOUR

AU - Romaguera, Salvador

AU - Sánchez-Pérez, Enrique A.

AU - Valero, Oscar

TI - Computing complexity distances between algorithms

JO - Kybernetika

PY - 2003

PB - Institute of Information Theory and Automation AS CR

VL - 39

IS - 5

SP - [569]

EP - 582

AB - 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.

LA - eng

KW - invariant extended quasi-metric; complexity function; balanced quasi-metric; infinite word; Baire metric; contraction mapping; Divide & Conquer algorithm; invariant extended quasi-metric; complexity function; balanced quasi-metric; infinite word; Baire metric

UR - http://eudml.org/doc/33666

ER -

## References

top- Bakker J. W. de, Vink E. P. de, 10.1016/S0166-8641(97)00140-5, Topology Appl. 85 (1998), 35–52 (1998) Zbl0933.68086MR1617453DOI10.1016/S0166-8641(97)00140-5
- Ćirić L., 10.1017/S1446788700036995, J. Austral. Math. Soc. Ser. A 54 (1993), 80–85 (1993) Zbl0765.54040MR1195660DOI10.1017/S1446788700036995
- Doitchinov D., 10.1016/0166-8641(88)90012-0, Topology Appl. 30 (1988), 127–148 (1988) Zbl0668.54019MR0967750DOI10.1016/0166-8641(88)90012-0
- Engelking R., General Topology, Polish Sci. Publ., Warsaw 1977 Zbl0684.54001MR0500780
- Fletcher P., Lindgren W. F., Quasi–Uniform Spaces, Marcel Dekker, 1982 Zbl0583.54017MR0660063
- García-Raffi L. M., Romaguera, S., Sánchez-Pérez E. A., 10.1016/S0895-7177(02)00100-0, Math. Comput. Modelling 36 (2002), 1–11 Zbl1063.68057MR1925055DOI10.1016/S0895-7177(02)00100-0
- Giles J. R., Introduction to the Analysis of Metric Spaces, (Austral. Math. Soc. Lecture Series no. 3.) Cambridge Univ. Press, Cambridge 1987 Zbl0645.46001MR0913302
- Hicks T. L., Fixed point theorems for quasi-metric spaces, Math. Japon. 33 (1988), 231–236 (1988) Zbl0642.54047MR0944022
- Jachymski J., A contribution to fixed point theory in quasi-metric spaces, Publ. Math. Debrecen 43 (1993), 283–288 (1993) Zbl0814.47061MR1269955
- Kahn G., The semantics of a simple language for parallel processing, In: Proc. IFIP Congress, Elsevier and North-Holland, Amsterdam 1974, pp. 471–475 (1974) MR0426486
- Keimel K., Roth W., Ordered Cones and Approximation, Springer–Verlag, Berlin 1992 Zbl0752.41033MR1176514
- Kopperman R. D., 10.1007/BF02573609, Semigroup Forum 25 (1982), 345–360 (1982) Zbl0502.22002MR0679288DOI10.1007/BF02573609
- 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 MR1900267
- Künzi H. P. A., Ryser C., The Bourbaki quasi-uniformity, Topology Proc. 20 (1995), 161–183 (1995) Zbl0876.54022MR1429179
- Lecomte P., Rigo M., On the representation of real numbers using regular languages, Theory Comput. Systems 35 (2002), 13–38 Zbl0993.68050MR1879170
- Matthews S. G., 10.1111/j.1749-6632.1994.tb44144.x, In: Proc. 8th Summer Conference on General Topology and Applications, Ann. New York Acad. Sci. 728 (1994), 183–197 (1994) Zbl0911.54025MR1467773DOI10.1111/j.1749-6632.1994.tb44144.x
- Reilly I. L., Subrahmanyam P. V., 10.1017/S144678870003648X, J. Austral. Math. Soc. Ser. A 53 (1992), 304–312 (1992) Zbl0772.54041MR1187850DOI10.1017/S144678870003648X
- Reilly I. L., Subrahmanyam P. V., Vamanamurthy M. K., 10.1007/BF01301400, Monatsh. Math. 93 (1982), 127–140 (1982) Zbl0472.54018MR0653103DOI10.1007/BF01301400
- Romaguera S., Sanchis M., 10.1006/jath.1999.3439, J. Approx. Theory 103 (2000), 292–301 Zbl0980.41029MR1749967DOI10.1006/jath.1999.3439
- Romaguera S., Schellekens M., 10.1016/S0166-8641(98)00102-3, Topology Appl. 98 (1999), 311–322 (1999) Zbl0941.54028MR1720009DOI10.1016/S0166-8641(98)00102-3
- Romaguera S., Schellekens M., Duality and quasi-normability for complexity spaces, Appl. Gen. Topology 3 (2002), 91–112 Zbl1022.54018MR1931256

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.