The complexity probabilistic quasi-metric space (Q624638)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The complexity probabilistic quasi-metric space |
scientific article |
Statements
The complexity probabilistic quasi-metric space (English)
0 references
9 February 2011
0 references
A probabilistic complexity quasi-metric space, as a fuzzy extension of the complexity quasi-metric space of \textit{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 \textit{V. Gregori} and \textit{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.
0 references
Probabilistic quasi-metric
0 references
Complexity function
0 references
Bicomplete
0 references
Fixed point
0 references