The Experts below are selected from a list of 213279 Experts worldwide ranked by ideXlab platform
Oscar Valero - One of the best experts on this subject based on the ideXlab platform.
-
the baire partial quasi metric Space a mathematical tool for asymptotic Complexity analysis in computer science
Theory of Computing Systems \ Mathematical Systems Theory, 2012Co-Authors: M A Cerdauguet, Michel Schellekens, Oscar ValeroAbstract:In 1994, S.G. Matthews introduced the notion of partial metric Space in order to obtain a suitable mathematical tool for program verification (Ann. N.Y. Acad. Sci. 728:183–197, 1994). He gave an application of this new structure to parallel computing by means of a partial metric version of the celebrated Banach fixed point theorem (Theor. Comput. Sci. 151:195–205, 1995). Later on, M.P. Schellekens introduced the theory of Complexity (quasi-metric) Spaces as a part of the development of a topological foundation for the asymptotic Complexity analysis of programs and algorithms (Electron. Notes Theor. Comput. Sci. 1:211–232, 1995). The applicability of this theory to the asymptotic Complexity analysis of Divide and Conquer algorithms was also illustrated by Schellekens. In particular, he gave a new proof, based on the use of the aforenamed Banach fixed point theorem, of the well-known fact that Mergesort algorithm has optimal asymptotic average running time of computing. In this paper, motivated by the utility of partial metrics in Computer Science, we discuss whether the Matthews fixed point theorem is a suitable tool to analyze the asymptotic Complexity of algorithms in the spirit of Schellekens. Specifically, we show that a slight modification of the well-known Baire partial metric on the set of all words over an alphabet constitutes an appropriate tool to carry out the asymptotic Complexity analysis of algorithms via fixed point methods without the need for assuming the convergence condition inherent to the definition of the Complexity Space in the Schellekens framework. Finally, in order to illustrate and to validate the developed theory we apply our results to analyze the asymptotic Complexity of Quicksort, Mergesort and Largesort algorithms. Concretely we retrieve through our new approach the well-known facts that the running time of computing of Quicksort (worst case behaviour), Mergesort and Largesort (average case behaviour) are in the Complexity classes $\mathcal{O}(n^{2})$, $\mathcal{O}(n\log_{2}(n))$ and $\mathcal{O}(2(n-1)-\log_{2}(n))$, respectively.
-
Complexity Spaces as quantitative domains of computation
Topology and its Applications, 2011Co-Authors: Salvador Romaguera, Michel Schellekens, Oscar ValeroAbstract:Abstract We study domain theoretic properties of Complexity Spaces. Although the so-called Complexity Space is not a domain for the usual pointwise order, we show that, however, each pointed Complexity Space is an ω-continuous domain for which the Complexity quasi-metric induces the Scott topology, and the supremum metric induces the Lawson topology. Hence, each pointed Complexity Space is both a quantifiable domain in the sense of M. Schellekens and a quantitative domain in the sense of P. Waszkiewicz, via the partial metric induced by the Complexity quasi-metric.
-
the baire partial quasi metric Space a mathematical tool for asymptotic Complexity analysis in computer science
arXiv: Computational Complexity, 2010Co-Authors: M A Cerdauguet, Michel Schellekens, Oscar ValeroAbstract:In 1994, S.G. Matthews introduced the notion of partial metric Space in order to obtain a suitable mathematical tool for program verification [Ann. New York Acad. Sci. 728 (1994), 183-197]. He gave an application of this new structure to parallel computing by means of a partial metric version of the celebrated Banach fixed point theorem [Theoret. Comput. Sci. 151 (1995), 195-205]. Later on, M.P. Schellekens introduced the theory of Complexity (quasi-metric) Spaces as a part of the development of a topological foundation for the asymptotic Complexity analysis of programs and algorithms [Elec- tronic Notes in Theoret. Comput. Sci. 1 (1995), 211-232]. The applicability of this theory to the asymptotic Complexity analysis of Divide and Conquer algorithms was also illustrated by Schellekens. In particular, he gave a new proof, based on the use of the aforenamed Banach fixed point theorem, of the well-known fact that Mergesort al- gorithm has optimal asymptotic average running time of computing. In this paper, motivated by the utility of partial metrics in Computer Science, we discuss whether the Matthews fixed point theorem is a suitable tool to analyze the asymptotic Complexity of algorithms in the spirit of Schellekens. Specifically, we show that a slight modification of the well-known Baire partial metric on the set of all words over an alphabet constitutes an appropriate tool to carry out the asymptotic Complexity analysis of algorithms via fixed point methods without the need for assuming the convergence condition inherent to the defini- tion of the Complexity Space in the Shellekens framework. Finally, in order to illustrate and to validate the developed theory we apply our results to analyze the asymptotic Complexity of Quicksort, Mergesort and Largesort algorithms.
-
the dual Complexity Space as the dual of a normed cone
Electronic Notes in Theoretical Computer Science, 2006Co-Authors: Salvador Romaguera, E A Sanchezperez, Oscar ValeroAbstract:Abstract In [M. Schellekens, The Smyth completion: A common foundation for denotational semantics and Complexity analysis, in: Proc. MFPS 11, Electronic Notes in Theoretical Computer Science, vol. 1 (1995), 23 pages] M. Schellekens introduced the Complexity (quasi-metric) Space as a part of the research in Theoretical Computer Science and Topology, with applications to the Complexity analysis of algorithms. Later on, S. Romaguera and M. Schellekens ([S. Romaguera, M. Schellekens, Quasi-metric properties of Complexity Spaces, Topology Appl. 98 (1999), 311–322]) introduced the so-called dual Complexity (quasi-metric) Space and established several quasi-metric properties of the Complexity Space via the analysis of th e dual. These authors also proved in [S. Romaguera, M. Schellekens, Duality and quasi-normability for Complexity Spaces, Appl. Gen. Topology 3 (2002), 91–112] that actually the dual Complexity Space C ∗ can be modeled as a norm-weightable cone whose induced quasi-metric is Smyth complete. This fact suggests the existence of deep connections between a general theory of (dual) Complexity Spaces and Asymmetric Functional Analysis. These connections have been recently explored in [L.M. Garca-Raffi, S. Romaguera, E.A. Sanchez-Perez, Sequence Spaces and asymmetric norms in the theory of compuational Complexity, Math. Comput. Model 36 (2002), 1–11], [L.M. Garca-Raffi, S. Romaguera, E.A. Sanchez-Perez, The supremum asymmetric norm on sequence Spaces: a general framework to measure Complexity distances, in: Proceedings of the Second Irish Conference on the Mathematical Foundations of Computer Science and Information Technology (MFCSIT 2002), Galway, Ireland, July 2002; Electronic Notes in Theoret. Comput. Sci. 74 (2003), URL: http://www.elsevier.nl/locate/entcs/volume74.htm 12 pages] and [M. O'Keefe, S. Romaguera, M. Schellekens, Norm-weightable Riesz Spaces and the dual Complexity Space, in: Proceedings of the Second Irish Conference on the Math ematical Foundations of Computer Science and Information Technology (MFCSIT 2002), Galway, Ireland, July 2002; Electronic Notes in Theoret. Comput. Sci. 74 (2003), URL: http://www.elsevier.nl/locate/entcs/volume74.htm 17 pages]. In particular, it was proved in [L.M. Garca-Raffi, S. Romaguera, E.A. Sanchez-Perez, Sequence Spaces and asymmetric norms in the theory of compuational Complexity, Math. Comput. Model 36 (2002), 1–11] that the so-called dual p-Complexity Space C p ∗ , with 1 ⩽ p ∞ , is isometrically isomorphic to the positive cone of the classical Banach Space l p . The Space C 1 ∗ is exactly the dual Complexity Space, and thus it is isometrically isomorphic to the positive cone of the Banach Space l 1 of all absolutely summable real sequences. Here, we continue the analysis of the structure of the dual Complexity Space C ∗ . We show that it is the dual Space of the positive c one of the Banach Space c 0 of all real sequences converging to zero, and that its dual Space is the positive cone of the Banach Space l ∞ of all bounded real sequences. Furthermore, the dual Space of C p ∗ , 1 p ∞ , is C q ∗ where 1 / p + 1 / q = 1 . These results extend to this setting well-known theorems of the classical theory of Functional Analysis.
-
the Complexity Space of a valued linearly ordered set
Electronic Notes in Theoretical Computer Science, 2003Co-Authors: Salvador Romaguera, E A Sanchezperez, Oscar ValeroAbstract:By a valued linearly ordered set (a VLOS for short), we mean a pair (X, ϕ )s uch that X is a linearly ordered set and ϕ is a strictly increasing (= positive monotone) nonnegative real valued function. Clearly, any VLOS is a valuation Space. Each VLOS (X, ϕ) generates a linear weightable quasi-metric dϕ on X whose conjugate is order preserving. We show that the Smyth completion of (X, dϕ )a lso admits the structure of a VLOS. On the other hand, M. Schellekens introduced in 1995, the theory of Complexity Spaces to develop a topological foundation for the Complexity analysis of programs. Here, we introduce the so-called Complexity Space of a VLOS (X, ϕ) and discuss some of its properties. In particular, we show that it is weightable and preserves Smyth completeness of (X, dϕ). We apply this Complexity approach to the measurement of real numbers and discuss some advantages of our methods with respect to those that use the classical Baire metric.
Michel Schellekens - One of the best experts on this subject based on the ideXlab platform.
-
the baire partial quasi metric Space a mathematical tool for asymptotic Complexity analysis in computer science
Theory of Computing Systems \ Mathematical Systems Theory, 2012Co-Authors: M A Cerdauguet, Michel Schellekens, Oscar ValeroAbstract:In 1994, S.G. Matthews introduced the notion of partial metric Space in order to obtain a suitable mathematical tool for program verification (Ann. N.Y. Acad. Sci. 728:183–197, 1994). He gave an application of this new structure to parallel computing by means of a partial metric version of the celebrated Banach fixed point theorem (Theor. Comput. Sci. 151:195–205, 1995). Later on, M.P. Schellekens introduced the theory of Complexity (quasi-metric) Spaces as a part of the development of a topological foundation for the asymptotic Complexity analysis of programs and algorithms (Electron. Notes Theor. Comput. Sci. 1:211–232, 1995). The applicability of this theory to the asymptotic Complexity analysis of Divide and Conquer algorithms was also illustrated by Schellekens. In particular, he gave a new proof, based on the use of the aforenamed Banach fixed point theorem, of the well-known fact that Mergesort algorithm has optimal asymptotic average running time of computing. In this paper, motivated by the utility of partial metrics in Computer Science, we discuss whether the Matthews fixed point theorem is a suitable tool to analyze the asymptotic Complexity of algorithms in the spirit of Schellekens. Specifically, we show that a slight modification of the well-known Baire partial metric on the set of all words over an alphabet constitutes an appropriate tool to carry out the asymptotic Complexity analysis of algorithms via fixed point methods without the need for assuming the convergence condition inherent to the definition of the Complexity Space in the Schellekens framework. Finally, in order to illustrate and to validate the developed theory we apply our results to analyze the asymptotic Complexity of Quicksort, Mergesort and Largesort algorithms. Concretely we retrieve through our new approach the well-known facts that the running time of computing of Quicksort (worst case behaviour), Mergesort and Largesort (average case behaviour) are in the Complexity classes $\mathcal{O}(n^{2})$, $\mathcal{O}(n\log_{2}(n))$ and $\mathcal{O}(2(n-1)-\log_{2}(n))$, respectively.
-
Complexity Spaces as quantitative domains of computation
Topology and its Applications, 2011Co-Authors: Salvador Romaguera, Michel Schellekens, Oscar ValeroAbstract:Abstract We study domain theoretic properties of Complexity Spaces. Although the so-called Complexity Space is not a domain for the usual pointwise order, we show that, however, each pointed Complexity Space is an ω-continuous domain for which the Complexity quasi-metric induces the Scott topology, and the supremum metric induces the Lawson topology. Hence, each pointed Complexity Space is both a quantifiable domain in the sense of M. Schellekens and a quantitative domain in the sense of P. Waszkiewicz, via the partial metric induced by the Complexity quasi-metric.
-
the baire partial quasi metric Space a mathematical tool for asymptotic Complexity analysis in computer science
arXiv: Computational Complexity, 2010Co-Authors: M A Cerdauguet, Michel Schellekens, Oscar ValeroAbstract:In 1994, S.G. Matthews introduced the notion of partial metric Space in order to obtain a suitable mathematical tool for program verification [Ann. New York Acad. Sci. 728 (1994), 183-197]. He gave an application of this new structure to parallel computing by means of a partial metric version of the celebrated Banach fixed point theorem [Theoret. Comput. Sci. 151 (1995), 195-205]. Later on, M.P. Schellekens introduced the theory of Complexity (quasi-metric) Spaces as a part of the development of a topological foundation for the asymptotic Complexity analysis of programs and algorithms [Elec- tronic Notes in Theoret. Comput. Sci. 1 (1995), 211-232]. The applicability of this theory to the asymptotic Complexity analysis of Divide and Conquer algorithms was also illustrated by Schellekens. In particular, he gave a new proof, based on the use of the aforenamed Banach fixed point theorem, of the well-known fact that Mergesort al- gorithm has optimal asymptotic average running time of computing. In this paper, motivated by the utility of partial metrics in Computer Science, we discuss whether the Matthews fixed point theorem is a suitable tool to analyze the asymptotic Complexity of algorithms in the spirit of Schellekens. Specifically, we show that a slight modification of the well-known Baire partial metric on the set of all words over an alphabet constitutes an appropriate tool to carry out the asymptotic Complexity analysis of algorithms via fixed point methods without the need for assuming the convergence condition inherent to the defini- tion of the Complexity Space in the Shellekens framework. Finally, in order to illustrate and to validate the developed theory we apply our results to analyze the asymptotic Complexity of Quicksort, Mergesort and Largesort algorithms.
-
norm weightable riesz Spaces and the dual Complexity Space
Electronic Notes in Theoretical Computer Science, 2003Co-Authors: M Okeeffe, Salvador Romaguera, Michel SchellekensAbstract:Abstract The theory of Complexity Spaces has been introduced in [Sch95], where the applicability to the Complexity analysis of Divide and Conquer algorithms has been discussed. This analysis has been based on the Banach Fixed Point Theorem, which has led to the study of biBanach Spaces in [RS98]. In [RS96] we have introduced the dual Complexity Space as a convenient tool to carry out a mathematical analysis of Complexity Spaces (cf. also [RS98]). We recall that the Complexity Space as well as its dual are weightable quasi-metric Spaces as well as its dual are weightable quasi-metric Spaces or, equivalently, partial metric Spaces (cf. [Sch95], [RS96] as well as [Kun93],[KV94] and [Mat94]. Recently it has been shown in [Sch02a] that partial metric Spaces correspond dually, in the context of Domain Theory, to semivaluation Spaces. Here, we show that the dual Complexity Space is the negative cone of a biBanach norm-weightable Riesz Space (e.g. [BOU52] and [RS98]) and characterize the class of norm-weightable Riesz Spaces in terms of semivaluation Spaces. In particular, we show that the quasi-norm of an element of such a Riesz Space is the quasi-norm of its projection on the negative cone. Hence, quasi-norms are completely determined by partial metrics, justifying, in this context, O'Neill's analogy between these notions. In [Sch02a], It is shown that quasi-uniform semilattices arise naturally in Domain Theory, which motivates a generalization of our characterization to the context of norm-weightable quasi-uniform Riesz Spaces.
M A Cerdauguet - One of the best experts on this subject based on the ideXlab platform.
-
the baire partial quasi metric Space a mathematical tool for asymptotic Complexity analysis in computer science
Theory of Computing Systems \ Mathematical Systems Theory, 2012Co-Authors: M A Cerdauguet, Michel Schellekens, Oscar ValeroAbstract:In 1994, S.G. Matthews introduced the notion of partial metric Space in order to obtain a suitable mathematical tool for program verification (Ann. N.Y. Acad. Sci. 728:183–197, 1994). He gave an application of this new structure to parallel computing by means of a partial metric version of the celebrated Banach fixed point theorem (Theor. Comput. Sci. 151:195–205, 1995). Later on, M.P. Schellekens introduced the theory of Complexity (quasi-metric) Spaces as a part of the development of a topological foundation for the asymptotic Complexity analysis of programs and algorithms (Electron. Notes Theor. Comput. Sci. 1:211–232, 1995). The applicability of this theory to the asymptotic Complexity analysis of Divide and Conquer algorithms was also illustrated by Schellekens. In particular, he gave a new proof, based on the use of the aforenamed Banach fixed point theorem, of the well-known fact that Mergesort algorithm has optimal asymptotic average running time of computing. In this paper, motivated by the utility of partial metrics in Computer Science, we discuss whether the Matthews fixed point theorem is a suitable tool to analyze the asymptotic Complexity of algorithms in the spirit of Schellekens. Specifically, we show that a slight modification of the well-known Baire partial metric on the set of all words over an alphabet constitutes an appropriate tool to carry out the asymptotic Complexity analysis of algorithms via fixed point methods without the need for assuming the convergence condition inherent to the definition of the Complexity Space in the Schellekens framework. Finally, in order to illustrate and to validate the developed theory we apply our results to analyze the asymptotic Complexity of Quicksort, Mergesort and Largesort algorithms. Concretely we retrieve through our new approach the well-known facts that the running time of computing of Quicksort (worst case behaviour), Mergesort and Largesort (average case behaviour) are in the Complexity classes $\mathcal{O}(n^{2})$, $\mathcal{O}(n\log_{2}(n))$ and $\mathcal{O}(2(n-1)-\log_{2}(n))$, respectively.
-
the baire partial quasi metric Space a mathematical tool for asymptotic Complexity analysis in computer science
arXiv: Computational Complexity, 2010Co-Authors: M A Cerdauguet, Michel Schellekens, Oscar ValeroAbstract:In 1994, S.G. Matthews introduced the notion of partial metric Space in order to obtain a suitable mathematical tool for program verification [Ann. New York Acad. Sci. 728 (1994), 183-197]. He gave an application of this new structure to parallel computing by means of a partial metric version of the celebrated Banach fixed point theorem [Theoret. Comput. Sci. 151 (1995), 195-205]. Later on, M.P. Schellekens introduced the theory of Complexity (quasi-metric) Spaces as a part of the development of a topological foundation for the asymptotic Complexity analysis of programs and algorithms [Elec- tronic Notes in Theoret. Comput. Sci. 1 (1995), 211-232]. The applicability of this theory to the asymptotic Complexity analysis of Divide and Conquer algorithms was also illustrated by Schellekens. In particular, he gave a new proof, based on the use of the aforenamed Banach fixed point theorem, of the well-known fact that Mergesort al- gorithm has optimal asymptotic average running time of computing. In this paper, motivated by the utility of partial metrics in Computer Science, we discuss whether the Matthews fixed point theorem is a suitable tool to analyze the asymptotic Complexity of algorithms in the spirit of Schellekens. Specifically, we show that a slight modification of the well-known Baire partial metric on the set of all words over an alphabet constitutes an appropriate tool to carry out the asymptotic Complexity analysis of algorithms via fixed point methods without the need for assuming the convergence condition inherent to the defini- tion of the Complexity Space in the Shellekens framework. Finally, in order to illustrate and to validate the developed theory we apply our results to analyze the asymptotic Complexity of Quicksort, Mergesort and Largesort algorithms.
Salvador Romaguera - One of the best experts on this subject based on the ideXlab platform.
-
Complexity Spaces as quantitative domains of computation
Topology and its Applications, 2011Co-Authors: Salvador Romaguera, Michel Schellekens, Oscar ValeroAbstract:Abstract We study domain theoretic properties of Complexity Spaces. Although the so-called Complexity Space is not a domain for the usual pointwise order, we show that, however, each pointed Complexity Space is an ω-continuous domain for which the Complexity quasi-metric induces the Scott topology, and the supremum metric induces the Lawson topology. Hence, each pointed Complexity Space is both a quantifiable domain in the sense of M. Schellekens and a quantitative domain in the sense of P. Waszkiewicz, via the partial metric induced by the Complexity quasi-metric.
-
hyperSpaces of a weightable quasi metric Space application to models in the theory of computation
Mathematical and Computer Modelling, 2010Co-Authors: Hanspeter A Kunzi, Jesus Rodriguezlopez, Salvador RomagueraAbstract:It is well known that both weightable quasi-metrics and the Hausdorff distance provide efficient tools in several areas of Computer Science. This fact suggests, in a natural way, the problem of when the upper and lower Hausdorff quasi-pseudo-metrics of a weightable quasi-metric Space (X,d) are weightable. Here we discuss this problem. Although the answer is negative in general, we show, however, that it is positive for several nice classes of (nonempty) subsets of X. Since the construction of these classes depends, to a large degree, on the specialization order of the quasi-metric d, we are able to apply our results to some distinguished quasi-metric models that appear in theoretical computer science and information theory, like the domain of words, the interval domain and the Complexity Space.
-
the dual Complexity Space as the dual of a normed cone
Electronic Notes in Theoretical Computer Science, 2006Co-Authors: Salvador Romaguera, E A Sanchezperez, Oscar ValeroAbstract:Abstract In [M. Schellekens, The Smyth completion: A common foundation for denotational semantics and Complexity analysis, in: Proc. MFPS 11, Electronic Notes in Theoretical Computer Science, vol. 1 (1995), 23 pages] M. Schellekens introduced the Complexity (quasi-metric) Space as a part of the research in Theoretical Computer Science and Topology, with applications to the Complexity analysis of algorithms. Later on, S. Romaguera and M. Schellekens ([S. Romaguera, M. Schellekens, Quasi-metric properties of Complexity Spaces, Topology Appl. 98 (1999), 311–322]) introduced the so-called dual Complexity (quasi-metric) Space and established several quasi-metric properties of the Complexity Space via the analysis of th e dual. These authors also proved in [S. Romaguera, M. Schellekens, Duality and quasi-normability for Complexity Spaces, Appl. Gen. Topology 3 (2002), 91–112] that actually the dual Complexity Space C ∗ can be modeled as a norm-weightable cone whose induced quasi-metric is Smyth complete. This fact suggests the existence of deep connections between a general theory of (dual) Complexity Spaces and Asymmetric Functional Analysis. These connections have been recently explored in [L.M. Garca-Raffi, S. Romaguera, E.A. Sanchez-Perez, Sequence Spaces and asymmetric norms in the theory of compuational Complexity, Math. Comput. Model 36 (2002), 1–11], [L.M. Garca-Raffi, S. Romaguera, E.A. Sanchez-Perez, The supremum asymmetric norm on sequence Spaces: a general framework to measure Complexity distances, in: Proceedings of the Second Irish Conference on the Mathematical Foundations of Computer Science and Information Technology (MFCSIT 2002), Galway, Ireland, July 2002; Electronic Notes in Theoret. Comput. Sci. 74 (2003), URL: http://www.elsevier.nl/locate/entcs/volume74.htm 12 pages] and [M. O'Keefe, S. Romaguera, M. Schellekens, Norm-weightable Riesz Spaces and the dual Complexity Space, in: Proceedings of the Second Irish Conference on the Math ematical Foundations of Computer Science and Information Technology (MFCSIT 2002), Galway, Ireland, July 2002; Electronic Notes in Theoret. Comput. Sci. 74 (2003), URL: http://www.elsevier.nl/locate/entcs/volume74.htm 17 pages]. In particular, it was proved in [L.M. Garca-Raffi, S. Romaguera, E.A. Sanchez-Perez, Sequence Spaces and asymmetric norms in the theory of compuational Complexity, Math. Comput. Model 36 (2002), 1–11] that the so-called dual p-Complexity Space C p ∗ , with 1 ⩽ p ∞ , is isometrically isomorphic to the positive cone of the classical Banach Space l p . The Space C 1 ∗ is exactly the dual Complexity Space, and thus it is isometrically isomorphic to the positive cone of the Banach Space l 1 of all absolutely summable real sequences. Here, we continue the analysis of the structure of the dual Complexity Space C ∗ . We show that it is the dual Space of the positive c one of the Banach Space c 0 of all real sequences converging to zero, and that its dual Space is the positive cone of the Banach Space l ∞ of all bounded real sequences. Furthermore, the dual Space of C p ∗ , 1 p ∞ , is C q ∗ where 1 / p + 1 / q = 1 . These results extend to this setting well-known theorems of the classical theory of Functional Analysis.
-
norm weightable riesz Spaces and the dual Complexity Space
Electronic Notes in Theoretical Computer Science, 2003Co-Authors: M Okeeffe, Salvador Romaguera, Michel SchellekensAbstract:Abstract The theory of Complexity Spaces has been introduced in [Sch95], where the applicability to the Complexity analysis of Divide and Conquer algorithms has been discussed. This analysis has been based on the Banach Fixed Point Theorem, which has led to the study of biBanach Spaces in [RS98]. In [RS96] we have introduced the dual Complexity Space as a convenient tool to carry out a mathematical analysis of Complexity Spaces (cf. also [RS98]). We recall that the Complexity Space as well as its dual are weightable quasi-metric Spaces as well as its dual are weightable quasi-metric Spaces or, equivalently, partial metric Spaces (cf. [Sch95], [RS96] as well as [Kun93],[KV94] and [Mat94]. Recently it has been shown in [Sch02a] that partial metric Spaces correspond dually, in the context of Domain Theory, to semivaluation Spaces. Here, we show that the dual Complexity Space is the negative cone of a biBanach norm-weightable Riesz Space (e.g. [BOU52] and [RS98]) and characterize the class of norm-weightable Riesz Spaces in terms of semivaluation Spaces. In particular, we show that the quasi-norm of an element of such a Riesz Space is the quasi-norm of its projection on the negative cone. Hence, quasi-norms are completely determined by partial metrics, justifying, in this context, O'Neill's analogy between these notions. In [Sch02a], It is shown that quasi-uniform semilattices arise naturally in Domain Theory, which motivates a generalization of our characterization to the context of norm-weightable quasi-uniform Riesz Spaces.
-
the Complexity Space of a valued linearly ordered set
Electronic Notes in Theoretical Computer Science, 2003Co-Authors: Salvador Romaguera, E A Sanchezperez, Oscar ValeroAbstract:By a valued linearly ordered set (a VLOS for short), we mean a pair (X, ϕ )s uch that X is a linearly ordered set and ϕ is a strictly increasing (= positive monotone) nonnegative real valued function. Clearly, any VLOS is a valuation Space. Each VLOS (X, ϕ) generates a linear weightable quasi-metric dϕ on X whose conjugate is order preserving. We show that the Smyth completion of (X, dϕ )a lso admits the structure of a VLOS. On the other hand, M. Schellekens introduced in 1995, the theory of Complexity Spaces to develop a topological foundation for the Complexity analysis of programs. Here, we introduce the so-called Complexity Space of a VLOS (X, ϕ) and discuss some of its properties. In particular, we show that it is weightable and preserves Smyth completeness of (X, dϕ). We apply this Complexity approach to the measurement of real numbers and discuss some advantages of our methods with respect to those that use the classical Baire metric.
Naofal Aldhahir - One of the best experts on this subject based on the ideXlab platform.
-
reduced Complexity Space time turbo equalization for frequency selective mimo channels
IEEE Transactions on Wireless Communications, 2002Co-Authors: G Bauch, Naofal AldhahirAbstract:We consider turbo equalization of Space-time-coded transmission over frequency-selective fading multiple-input-multiple-output (MIMO) channels. A MIMO finite-impulse-response prefilter is proposed and shown to reduce the turbo equalizer Complexity significantly at a small performance loss. Advantages of the proposed scheme are that we do not alter the equalization algorithm or require the channel to be minimum phase. The prefiltered turbo equalizer is an attractive receiver structure for broadband wireless transmission using spectrally-efficient high-order modulation schemes as in EDGE.