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

Abstract

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

How to cite

top

Romaguera, 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
  1. 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
  2. Ćirić L., 10.1017/S1446788700036995, J. Austral. Math. Soc. Ser. A 54 (1993), 80–85 (1993) Zbl0765.54040MR1195660DOI10.1017/S1446788700036995
  3. Doitchinov D., 10.1016/0166-8641(88)90012-0, Topology Appl. 30 (1988), 127–148 (1988) Zbl0668.54019MR0967750DOI10.1016/0166-8641(88)90012-0
  4. Engelking R., General Topology, Polish Sci. Publ., Warsaw 1977 Zbl0684.54001MR0500780
  5. Fletcher P., Lindgren W. F., Quasi–Uniform Spaces, Marcel Dekker, 1982 Zbl0583.54017MR0660063
  6. 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
  7. Giles J. R., Introduction to the Analysis of Metric Spaces, (Austral. Math. Soc. Lecture Series no. 3.) Cambridge Univ. Press, Cambridge 1987 Zbl0645.46001MR0913302
  8. Hicks T. L., Fixed point theorems for quasi-metric spaces, Math. Japon. 33 (1988), 231–236 (1988) Zbl0642.54047MR0944022
  9. Jachymski J., A contribution to fixed point theory in quasi-metric spaces, Publ. Math. Debrecen 43 (1993), 283–288 (1993) Zbl0814.47061MR1269955
  10. 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
  11. Keimel K., Roth W., Ordered Cones and Approximation, Springer–Verlag, Berlin 1992 Zbl0752.41033MR1176514
  12. Kopperman R. D., 10.1007/BF02573609, Semigroup Forum 25 (1982), 345–360 (1982) Zbl0502.22002MR0679288DOI10.1007/BF02573609
  13. 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
  14. Künzi H. P. A., Ryser C., The Bourbaki quasi-uniformity, Topology Proc. 20 (1995), 161–183 (1995) Zbl0876.54022MR1429179
  15. Lecomte P., Rigo M., On the representation of real numbers using regular languages, Theory Comput. Systems 35 (2002), 13–38 Zbl0993.68050MR1879170
  16. 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
  17. Reilly I. L., Subrahmanyam P. V., 10.1017/S144678870003648X, J. Austral. Math. Soc. Ser. A 53 (1992), 304–312 (1992) Zbl0772.54041MR1187850DOI10.1017/S144678870003648X
  18. Reilly I. L., Subrahmanyam P. V., Vamanamurthy M. K., 10.1007/BF01301400, Monatsh. Math. 93 (1982), 127–140 (1982) Zbl0472.54018MR0653103DOI10.1007/BF01301400
  19. Romaguera S., Sanchis M., 10.1006/jath.1999.3439, J. Approx. Theory 103 (2000), 292–301 Zbl0980.41029MR1749967DOI10.1006/jath.1999.3439
  20. 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
  21. Romaguera S., Schellekens M., Duality and quasi-normability for complexity spaces, Appl. Gen. Topology 3 (2002), 91–112 Zbl1022.54018MR1931256

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.