×

The complexity probabilistic quasi-metric space. (English) Zbl 1227.54035

A probabilistic complexity quasi-metric space, as a fuzzy extension of the complexity quasi-metric space of M. P. Schellekens [The Smyth completion: A common foundation for denotational semantics and complexity analysis. Elec. Notes Theoret. Comput. Sci. 1, 535–556 (1995; Zbl 0910.68135)] is constructed. This probabilistic complexity quasi-metric space improves Schellekens’ approach by providing an appropriate setting to obtain a suitable measurement of the distance from a complexity function \(f\) to another one \(g\), when \(f\) is asymptotically more efficient than \(g\). A version of V. Gregori and A. Sapena’s fixed point theorem [Fuzzy Sets Syst. 125, No. 2, 245–252 (2002; Zbl 0995.54046)] for quasi-Menger spaces, with applications to functionals associated both to Divide and Conquer algorithms and Quicksort algorithms is also given.

MSC:

54E70 Probabilistic metric spaces
54H25 Fixed-point and coincidence theorems (topological aspects)
68W99 Algorithms in computer science
68W40 Analysis of algorithms
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alegre, C.; Romaguera, S., Characterizations of metrizable topological vector spaces and their asymmetric generalizations in terms of fuzzy (quasi-)norms, Fuzzy Sets and Systems, 161, 2181-2192 (2010) · Zbl 1203.46049
[2] Bag, T.; Samanta, S. K., A comparative study of fuzzy norms on a linear space, Fuzzy Sets and Systems, 159, 670-684 (2008) · Zbl 1178.46074
[3] Bahrami, F., Some topologies on a Šerstnev probabilistic normed space, J. Math. Anal. Appl., 344, 857-868 (2008) · Zbl 1152.46060
[4] Bahrami, F.; Nikfar, M., The topological structure of a certain Menger space, J. Math. Anal. Appl., 334, 172-182 (2007) · Zbl 1129.46065
[5] Cho, Y. J.; Grabiec, M.; Radu, V., On Nonsymmetric Topological and Probabilistic Structures (2006), Nova Science Publisher: Nova Science Publisher New York · Zbl 1219.54001
[6] Fletcher, P.; Lindgren, W. F., Quasi-Uniform Spaces (1982), Marcel Dekker: Marcel Dekker New York · Zbl 0402.54024
[7] George, A.; Veeramani, P., On some results in fuzzy metric spaces, Fuzzy Sets and Systems, 64, 395-399 (1994) · Zbl 0843.54014
[8] George, A.; Veeramani, P., On some results of analysis for fuzzy metric spaces, Fuzzy Sets and Systems, 90, 365-368 (1997) · Zbl 0917.54010
[9] 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, 1-11 (2002) · Zbl 1063.68057
[10] García-Raffi, L. M.; Romaguera, S.; Schellekens, M., Applications of the complexity space to the General Probabilistic Divide and Conquer algorithms, J. Math. Anal. Appl., 348, 346-355 (2008) · Zbl 1149.68080
[11] Gregori, V.; Romaguera, S., Fuzzy quasi-metric spaces, Appl. Gen. Topol., 5, 129-136 (2004) · Zbl 1076.54005
[12] Gregori, V.; Sapena, A., On fixed-point theorems in fuzzy metric spaces, Fuzzy Sets and Systems, 125, 245-253 (2002) · Zbl 0995.54046
[13] Hadzic, O.; Pap, E., Fixed Point Theory in Probabilistic Metric Spaces (2001), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht
[14] Kruse, R., Data Structures and Program Design (1984), Prentice-Hall
[15] Künzi, H. P.A., Nonsymmetric distances and their associated topologies: About the origins of basic ideas in the area of asymmetric topology, (Aull, C. E.; Lowen, R., Handbook of the History of General Topology, vol. 3 (2001), Kluwer: Kluwer Dordrecht), 853-968 · Zbl 1002.54002
[16] Künzi, H. P.A.; Schellekens, M., On the Yoneda completion of a quasi-metric space, Theoret. Comput. Sci., 278, 159-194 (2002) · Zbl 1025.54014
[17] Matthews, S. G., Partial metric topology, (Proc. 8th Summer Conference on General Topology and Its Applications. Proc. 8th Summer Conference on General Topology and Its Applications, Ann. New York Acad. Sci., vol. 728 (1994)), 183-197 · Zbl 0911.54025
[18] Mihet, D., A Banach contraction theorem in fuzzy metric spaces, Fuzzy Sets and Systems, 144, 431-439 (2004) · Zbl 1052.54010
[19] Reilly, I. L.; Subrahmanyam, P. V.; Vamanamurthy, M. K., Cauchy sequences in quasi-pseudo-metric spaces, Monatsh. Math., 93, 127-140 (1982) · Zbl 0472.54018
[20] Romaguera, S.; Sapena, A.; Tirado, P., The Banach fixed point theorem in fuzzy quasi-metric spaces with application to the domain of words, Topology Appl., 154, 2196-2203 (2007) · Zbl 1119.54007
[21] Romaguera, S.; Schellekens, M., Quasi-metric properties of complexity spaces, Topology Appl., 98, 311-322 (1999) · Zbl 0941.54028
[22] Romaguera, S.; Schellekens, M., Partial metric monoids and semivaluation spaces, Topology Appl., 153, 948-962 (2005) · Zbl 1084.22002
[23] Romaguera, S.; Valero, O., On the structure of the complexity space of partial functions, Int. J. Comput. Math., 85, 631-640 (2008) · Zbl 1146.68376
[24] Saadati, R.; Vaezpour, S. M., Linear operators in finite dimensional probabilistic normed spaces, J. Math. Anal. Appl., 346, 446-450 (2008) · Zbl 1153.47065
[25] Saadati, R.; Vaezpour, S. M.; Cho, Y. J., Quicksort algorithm: Application of fixed point theorem in intuitionistic fuzzy quasi-metric spaces at a domain of words, J. Comput. Appl. Math., 228, 219-225 (2009) · Zbl 1189.68040
[26] Schellekens, M., The Smyth completion: a common foundation for denotational semantics and complexity analysis, (Proc. MFPS 11. Proc. MFPS 11, Electron. Notes Theor. Comput. Sci., vol. 1 (1995)), 535-556 · Zbl 0910.68135
[27] Smyth, M. B., Totally bounded spaces and compact ordered spaces as domains of computation, (Reed, G. M.; Roscoe, A. W.; Wachter, R. F., Topology and Category Theory in Computer Science (1991), Clarendon Press: Clarendon Press Oxford), 207-229
[28] Schweizer, B.; Sklar, A., Statistical metric spaces, Pacific J. Math., 10, 314-334 (1960) · Zbl 0091.29801
[29] Schweizer, B.; Sklar, A., Probabilistic Metric Spaces (1983), Springer: Springer North Holland · Zbl 0546.60010
[30] Zhang, G.; Zhang, M., On the normability of generalized Šerstnev PN spaces, J. Math. Anal. Appl., 340, 1000-1011 (2008) · Zbl 1134.54007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.