The Banach fixed point theorem in fuzzy quasi-metric spaces with application to the domain of words. (English) Zbl 1119.54007
The authors present yet another version of the Banach contraction principle translated into fuzzy metric spaces. More precisely they extend the fixed point theorem by M. Grabiec [Fuzzy Sets Syst. 27, No. 3, 385–389 (1988; Zbl 0664.54032)] for a class of fuzzy quasi-metrics of Baire type. It enables application of this theorem in the domain of denotational semantics of programming languages. As an example of such an application the authors analyze the complexity of divide and conquer algorithms which solve a problem by recursively splitting it into subproblems each of which is solved by the same algorithm and the results are combined into a solution of the original problem. The authors seem not to know recent results of O. Hadzic and E. Pap [Fixed point theory in probabilistic metric spaces, Kluwer Academic Publishers, Dordrecht (2002; Zbl 0994.47077)].
Reviewer: A. Šwierniak (Gliwice)
MSC:
| 54A40 | Fuzzy topology |
| 54E50 | Complete metric spaces |
| 54H25 | Fixed-point and coincidence theorems (topological aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q55 | Semantics in the theory of computing |
| 54E05 | Proximity structures and generalizations |
| 68W40 | Analysis of algorithms |
References:
| [1] | de Bakker, J. W.; de Vink, E. P., A metric approach to control flow semantics, Proc. Eleventh Summer Conference on General Topology and Applications. Proc. Eleventh Summer Conference on General Topology and Applications, Ann. New York Acad. Sci., 806, 11-27 (1996) · Zbl 0971.68099 |
| [2] | de Bakker, J. W.; de Vink, E. P., Denotational models for programming languages: applications of Banach’s fixed point theorem, Topology Appl., 85, 35-52 (1998) · Zbl 0933.68086 |
| [3] | de Bakker, J. W.; de Vink, E. P., Control Flow Semantics (1996), The MIT Press: The MIT Press Cambridge, MA · Zbl 0971.68099 |
| [4] | Davis, M.; Weyuker, E., Computability, Complexity and Languages (1983), Academic Press: Academic Press New York · Zbl 0569.68042 |
| [5] | Flajolet, P., Analytic analysis of algorithms, (Kuich, W., Automata, Languages and Programming. Automata, Languages and Programming, 19th Internat. Colloq. ICALP’92, Vienna, July 1992. Automata, Languages and Programming. Automata, Languages and Programming, 19th Internat. Colloq. ICALP’92, Vienna, July 1992, Lecture Notes in Computer Science, vol. 623 (1992), Springer: Springer Berlin), 186-210 · Zbl 1425.68473 |
| [6] | George, A.; Veeramani, P., On some results in fuzzy metric spaces, Fuzzy Sets and Systems, 64, 395-399 (1994) · Zbl 0843.54014 |
| [7] | George, A.; Veeramani, P., On some results of analysis of fuzzy metric spaces, Fuzzy Sets and Systems, 90, 365-368 (1997) · Zbl 0917.54010 |
| [8] | Grabiec, M., Fixed points in fuzzy metric spaces, Fuzzy Sets and Systems, 27, 385-389 (1988) · Zbl 0664.54032 |
| [9] | Gregori, V.; Romaguera, S., Fuzzy quasi-metric spaces, Appl. Gen. Topology, 5, 129-136 (2004) · Zbl 1076.54005 |
| [10] | Gregori, V.; Sapena, A., On fixed point theorems in fuzzy metric spaces, Fuzzy Sets and Systems, 125, 245-253 (2002) · Zbl 0995.54046 |
| [11] | Kahn, G., The semantics of a simple language for parallel processing, (Proc. IFIP Congress (1974), Elsevier, North-Holland: Elsevier, North-Holland Amsterdam), 471-475 · Zbl 0299.68007 |
| [12] | Kramosil, I.; Michalek, J., Fuzzy metrics and statistical metric spaces, Kybernetika, 11, 336-344 (1975) · Zbl 0319.54002 |
| [13] | Kruse, R., Data Structures and Program Design (1984), Prentice-Hall, Inc. |
| [14] | Künzi, H. P.A., Nonsymmetric topology, Proc. Colloquium on Topology, Szekszárd, Hungary, 1993. Proc. Colloquium on Topology, Szekszárd, Hungary, 1993, Colloq. Math. Soc. János Bolyai Math. Studies, 4, 303-338 (1995) · Zbl 0888.54029 |
| [15] | Matthews, S. G., Partial metric topology, Proc. 8th Summer Conference on General Topology and Applications. Proc. 8th Summer Conference on General Topology and Applications, Ann. New York Acad. Sci., 728, 183-197 (1994) · Zbl 0911.54025 |
| [16] | Sapena, A., A contribution to the study of fuzzy metric spaces, Appl. Gen. Topology, 2, 63-76 (2001) · Zbl 0985.54006 |
| [17] | Schellekens, M., The Smyth completion: a common foundation for denotational semantics and complexity analysis, Proc. MFPS 11. Proc. MFPS 11, Electronic Notes in Theoretical Computer Science, 1, 211-232 (1995) · Zbl 0910.68135 |
| [18] | Sehgal, V. M.; Bharucha-Reid, A. T., Fixed points of contraction mappings on PM-spaces, Math. Systems Theory, 6, 97-100 (1972) · Zbl 0244.60004 |
| [19] | Schweizer, B.; Sklar, A., Statistical metric spaces, Pacific J. Math., 10, 314-334 (1960) · Zbl 0091.29801 |
| [20] | Smyth, M. B., Quasi-uniformities: Reconciling domains with metric spaces, (Main, M.; etal., Mathematical Foundations of Programming Language Semantics. Mathematical Foundations of Programming Language Semantics, 3rd Workshop, Tulane, 1987. Mathematical Foundations of Programming Language Semantics. Mathematical Foundations of Programming Language Semantics, 3rd Workshop, Tulane, 1987, Lecture Notes Computer Science, vol. 298 (1988), Springer: Springer Berlin), 236-253 · Zbl 0668.54018 |
| [21] | Vasuki, R.; Veeramani, P., Fixed point theorems and Cauchy sequences in fuzzy metric spaces, Fuzzy Sets and Systems, 135, 415-417 (2003) · Zbl 1029.54012 |
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.
