Article
Full entry |
PDF
(1.5 MB)
Feedback
PDF
(1.5 MB)
Feedback
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; contraction mapping; Divide & Conquer algorithm
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.
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 DOI 10.1016/S0166-8641(97)00140-5 | MR 1617453 | Zbl 0933.68086
[2] Ćirić L.: Periodic and fixed point theorems in a quasi-metric space. J. Austral. Math. Soc. Ser. A 54 (1993), 80–85 DOI 10.1017/S1446788700036995 | MR 1195660 | Zbl 0765.54040
[3] Doitchinov D.: On completeness in quasi-metric spaces. Topology Appl. 30 (1988), 127–148 DOI 10.1016/0166-8641(88)90012-0 | MR 0967750 | Zbl 0668.54019
[4] Engelking R.: General Topology. Polish Sci. Publ., Warsaw 1977 MR 0500780 | Zbl 0684.54001
[6] Fletcher P., Lindgren W. F.: Quasi–Uniform Spaces. Marcel Dekker, 1982 MR 0660063 | Zbl 0583.54017
[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 10.1016/S0895-7177(02)00100-0 | MR 1925055 | Zbl 1063.68057
[8] Giles J. R.: Introduction to the Analysis of Metric Spaces. (Austral. Math. Soc. Lecture Series no. 3.) Cambridge Univ. Press, Cambridge 1987 MR 0913302 | Zbl 0645.46001
[9] Hicks T. L.: Fixed point theorems for quasi-metric spaces. Math. Japon. 33 (1988), 231–236 MR 0944022 | Zbl 0642.54047
[10] Jachymski J.: A contribution to fixed point theory in quasi-metric spaces. Publ. Math. Debrecen 43 (1993), 283–288 MR 1269955 | Zbl 0814.47061
[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
[12] Keimel K., Roth W.: Ordered Cones and Approximation. Springer–Verlag, Berlin 1992 MR 1176514 | Zbl 0752.41033
[13] Kopperman R. D.: Lengths on semigroups and groups. Semigroup Forum 25 (1982), 345–360 DOI 10.1007/BF02573609 | MR 0679288 | Zbl 0502.22002
[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
[15] Künzi H. P. A., Ryser C.: The Bourbaki quasi-uniformity. Topology Proc. 20 (1995), 161–183 MR 1429179 | Zbl 0876.54022
[16] Lecomte P., Rigo M.: On the representation of real numbers using regular languages. Theory Comput. Systems 35 (2002), 13–38 MR 1879170 | Zbl 0993.68050
[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 10.1111/j.1749-6632.1994.tb44144.x | MR 1467773 | Zbl 0911.54025
[18] Reilly I. L., Subrahmanyam P. V.: Some fixed point theorems. J. Austral. Math. Soc. Ser. A 53 (1992), 304–312 DOI 10.1017/S144678870003648X | MR 1187850 | Zbl 0772.54041
[19] Reilly I. L., Subrahmanyam P. V., Vamanamurthy M. K.: Cauchy sequences in quasi-pseudo-metric spaces. Monatsh. Math. 93 (1982), 127–140 DOI 10.1007/BF01301400 | MR 0653103 | Zbl 0472.54018
[20] Romaguera S., Sanchis M.: Semi-Lipschitz functions and best approximation in quasi-metric spaces. J. Approx. Theory 103 (2000), 292–301 DOI 10.1006/jath.1999.3439 | MR 1749967 | Zbl 0980.41029
[21] Romaguera S., Schellekens M.: Quasi-metric properties of complexity spaces. Topology Appl. 98 (1999), 311–322 DOI 10.1016/S0166-8641(98)00102-3 | MR 1720009 | Zbl 0941.54028
[22] Romaguera S., Schellekens M.: Duality and quasi-normability for complexity spaces. Appl. Gen. Topology 3 (2002), 91–112 MR 1931256 | Zbl 1022.54018
Search
Partner of
