✦ LIBER ✦

Quasi-metric properties of complexity spaces

✍ Scribed by S. Romaguera; M. Schellekens

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 110 KB
Volume: 98
Category: Article
ISSN: 0166-8641
DOI: 10.1016/s0166-8641(98)00102-3

No coin nor oath required. For personal study only.

✦ Synopsis

The complexity (quasi-metric) space has been introduced as a part of the development of a topological foundation for the complexity analysis of algorithms . Applications of this theory to the complexity analysis of Divide and Conquer algorithms have been discussed by .

Here we obtain several quasi-metric properties of the complexity space. The main results obtained are the Smyth-completeness of the complexity space and the compactness of closed complexity spaces which possess a (complexity) lower bound. Finally, some implications of these results in connection to the above mentioned complexity analysis techniques are discussed and the total boundedness of complexity spaces with a lower bound is discussed in the light of Smyth's computational interpretation of this property .

📜 SIMILAR VOLUMES

Recursive quasi-metric spaces

✍ Vasco Brattka 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 441 KB

In computable analysis recursive metric spaces play an important role, since these are, roughly speaking, spaces with computable metric and limit operation. Unfortunately, the concept of a metric space is not powerful enough to capture all interesting phenomena which occur in computable analysis. So

Computational complexity on computable m

Computational complexity on computable metric spaces

✍ Klaus Weirauch 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

## Abstract We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko [19] et al. Although this definition of TIME as the maximum of a gene

Left K-Completeness in Quasi-Metric Spac

Left K-Completeness in Quasi-Metric Spaces

✍ Salvador Romaguera 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 580 KB

## Abstract Regular left __K__‐sequentially complete quasi‐metric spaces are characterized. We deduce that these spaces are complete Aronszajn and that every metrizable space admitting a left __K__‐sequentially complete quasi‐metric is completely metrizable. We also characterize quasi‐metric spaces

A representation theorem for quasi-metri

A representation theorem for quasi-metric spaces

✍ P. Vitolo 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 246 KB

A quasi-metric space without complete qu

A quasi-metric space without complete quasi-uniformity

✍ Hans-Peter A. Künzi; Stephen Watson 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 266 KB

Some properties of fuzzy metric spaces

✍ Valentı́n Gregori; Salvador Romaguera 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 87 KB

We prove that the topology induced by any (complete) fuzzy metric space (in the sense of George and Veeramani) is (completely) metrizable. We also show that every separable fuzzy metric space admits a precompact fuzzy metric and that a fuzzy metric space is compact if and only if it is precompact an