Computing complexity distances between algorithms. (English) Zbl 1249.54069

Romaguera, S.; Sánchez-Pérez, E. A.; Valero, O.

Kybernetika 39, No. 5, 569-582 (2003).

Summary: 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 [in: S. Brookes (ed.) et al., Mathematical foundations of programming semantics. Proceedings of the 11th conference (MFPS), Tulane Univ., New Orleans. Amsterdam: Elsevier, Electronic Notes in Theoretical Computer Science. 1, 22 p. (1995; Zbl 0910.68135)], can be also given from our approach.

MSC:

54E50	Complete metric spaces
54H25	Fixed-point and coincidence theorems (topological aspects)
54H99	Connections of general topology with other structures, applications
68Q25	Analysis of algorithms and problem complexity

Keywords:

invariant extended quasi-metric; complexity function; balanced quasi-metric; infinite word; Baire metric

Citations:

Zbl 0910.68135

References:

[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 · Zbl 0933.68086 · doi:10.1016/S0166-8641(97)00140-5
[2]	Ćirić L.: Periodic and fixed point theorems in a quasi-metric space. J. Austral. Math. Soc. Ser. A 54 (1993), 80-85 · Zbl 0765.54040 · doi:10.1017/S1446788700036995
[3]	Doitchinov D.: On completeness in quasi-metric spaces. Topology Appl. 30 (1988), 127-148 · Zbl 0668.54019 · doi:10.1016/0166-8641(88)90012-0
[4]	Engelking R.: General Topology. Polish Sci. Publ., Warsaw 1977 · Zbl 0684.54001
[5]	Fletcher P., Lindgren W. F.: Quasi-Uniform Spaces. Marcel Dekker, 1982 · Zbl 0583.54017 · doi:10.1017/S0017089500006303
[6]	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 · Zbl 1063.68057 · doi:10.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 · Zbl 0645.46001
[8]	Hicks T. L.: Fixed point theorems for quasi-metric spaces. Math. Japon. 33 (1988), 231-236 · Zbl 0642.54047
[9]	Jachymski J.: A contribution to fixed point theory in quasi-metric spaces. Publ. Math. Debrecen 43 (1993), 283-288 · Zbl 0814.47061
[10]	Kahn G.: The semantics of a simple language for parallel processing. Proc. IFIP Congress, Elsevier and North-Holland, Amsterdam 1974, pp. 471-475
[11]	Keimel K., Roth W.: Ordered Cones and Approximation. Springer-Verlag, Berlin 1992 · Zbl 0752.41033
[12]	Kopperman R. D.: Lengths on semigroups and groups. Semigroup Forum 25 (1982), 345-360 · Zbl 0502.22002 · doi:10.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. Handbook of the History of General Topology, Volume 3 (C. E. Aull and R. Lowen, Kluwer, Dordrecht 2001, pp. 853-968 · Zbl 1002.54002
[14]	Künzi H. P. A., Ryser C.: The Bourbaki quasi-uniformity. Topology Proc. 20 (1995), 161-183 · Zbl 0876.54022
[15]	Lecomte P., Rigo M.: On the representation of real numbers using regular languages. Theory Comput. Systems 35 (2002), 13-38 · Zbl 0993.68050 · doi:10.1007/s00224-001-1007-5
[16]	Matthews S. G.: Partial metric topology. Proc. 8th Summer Conference on General Topology and Applications, Ann. New York Acad. Sci. 728 (1994), 183-197 · Zbl 0911.54025 · doi:10.1111/j.1749-6632.1994.tb44144.x
[17]	Reilly I. L., Subrahmanyam P. V.: Some fixed point theorems. J. Austral. Math. Soc. Ser. A 53 (1992), 304-312 · Zbl 0772.54041 · doi:10.1017/S144678870003648X
[18]	Reilly I. L., Subrahmanyam P. V., Vamanamurthy M. K.: Cauchy sequences in quasi-pseudo-metric spaces. Monatsh. Math. 93 (1982), 127-140 · Zbl 0472.54018 · doi:10.1007/BF01301400
[19]	Romaguera S., Sanchis M.: Semi-Lipschitz functions and best approximation in quasi-metric spaces. J. Approx. Theory 103 (2000), 292-301 · Zbl 0980.41029 · doi:10.1006/jath.1999.3439
[20]	Romaguera S., Schellekens M.: Quasi-metric properties of complexity spaces. Topology Appl. 98 (1999), 311-322 · Zbl 0941.54028 · doi:10.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 · Zbl 1022.54018