| Title:
|
Computing complexity distances between algorithms (English) |
| Author:
|
Romaguera, S. |
| Author:
|
Sánchez-Pérez, E. A. |
| Author:
|
Valero, O. |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
39 |
| Issue:
|
5 |
| Year:
|
2003 |
| Pages:
|
[569]-582 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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 (Electronic Notes in Theoret. Comput. Sci.1(1995)), can be also given from our approach. (English) |
| Keyword:
|
invariant extended quasi-metric |
| Keyword:
|
complexity function |
| Keyword:
|
balanced quasi-metric |
| Keyword:
|
infinite word |
| Keyword:
|
Baire metric |
| Keyword:
|
contraction mapping |
| Keyword:
|
Divide & Conquer algorithm |
| MSC:
|
54E50 |
| MSC:
|
54H25 |
| MSC:
|
54H99 |
| MSC:
|
68Q15 |
| MSC:
|
68Q25 |
| idZBL:
|
Zbl 1249.54069 |
| idMR:
|
MR2042342 |
| . |
| Date available:
|
2009-09-24T19:56:52Z |
| Last updated:
|
2015-03-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135556 |
| . |
| Reference:
|
[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, MR 1617453, 10.1016/S0166-8641(97)00140-5 |
| Reference:
|
[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, MR 1195660, 10.1017/S1446788700036995 |
| Reference:
|
[3] Doitchinov D.: On completeness in quasi-metric spaces.Topology Appl. 30 (1988), 127–148 Zbl 0668.54019, MR 0967750, 10.1016/0166-8641(88)90012-0 |
| Reference:
|
[4] Engelking R.: General Topology.Polish Sci. Publ., Warsaw 1977 Zbl 0684.54001, MR 0500780 |
| Reference:
|
[6] Fletcher P., Lindgren W. F.: Quasi–Uniform Spaces.Marcel Dekker, 1982 Zbl 0583.54017, MR 0660063 |
| Reference:
|
[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 Zbl 1063.68057, MR 1925055, 10.1016/S0895-7177(02)00100-0 |
| Reference:
|
[8] 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, MR 0913302 |
| Reference:
|
[9] Hicks T. L.: Fixed point theorems for quasi-metric spaces.Math. Japon. 33 (1988), 231–236 Zbl 0642.54047, MR 0944022 |
| Reference:
|
[10] Jachymski J.: A contribution to fixed point theory in quasi-metric spaces.Publ. Math. Debrecen 43 (1993), 283–288 Zbl 0814.47061, MR 1269955 |
| Reference:
|
[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 0426486 |
| Reference:
|
[12] Keimel K., Roth W.: Ordered Cones and Approximation.Springer–Verlag, Berlin 1992 Zbl 0752.41033, MR 1176514 |
| Reference:
|
[13] Kopperman R. D.: Lengths on semigroups and groups.Semigroup Forum 25 (1982), 345–360 Zbl 0502.22002, MR 0679288, 10.1007/BF02573609 |
| Reference:
|
[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 1900267 |
| Reference:
|
[15] Künzi H. P. A., Ryser C.: The Bourbaki quasi-uniformity.Topology Proc. 20 (1995), 161–183 Zbl 0876.54022, MR 1429179 |
| Reference:
|
[16] Lecomte P., Rigo M.: On the representation of real numbers using regular languages.Theory Comput. Systems 35 (2002), 13–38 Zbl 0993.68050, MR 1879170 |
| Reference:
|
[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 Zbl 0911.54025, MR 1467773, 10.1111/j.1749-6632.1994.tb44144.x |
| Reference:
|
[18] Reilly I. L., Subrahmanyam P. V.: Some fixed point theorems.J. Austral. Math. Soc. Ser. A 53 (1992), 304–312 Zbl 0772.54041, MR 1187850, 10.1017/S144678870003648X |
| Reference:
|
[19] 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, MR 0653103, 10.1007/BF01301400 |
| Reference:
|
[20] Romaguera S., Sanchis M.: Semi-Lipschitz functions and best approximation in quasi-metric spaces.J. Approx. Theory 103 (2000), 292–301 Zbl 0980.41029, MR 1749967, 10.1006/jath.1999.3439 |
| Reference:
|
[21] Romaguera S., Schellekens M.: Quasi-metric properties of complexity spaces.Topology Appl. 98 (1999), 311–322 Zbl 0941.54028, MR 1720009, 10.1016/S0166-8641(98)00102-3 |
| Reference:
|
[22] Romaguera S., Schellekens M.: Duality and quasi-normability for complexity spaces.Appl. Gen. Topology 3 (2002), 91–112 Zbl 1022.54018, MR 1931256 |
| . |
