Duality and quasi-normability for complexity spaces

Salvador Romaguera; M.P. Schellekens

doi:10.4995/agt.2002.2116

Authors

Salvador Romaguera Universitat Politècnica de València
M.P. Schellekens National University of Ireland

DOI:

https://doi.org/10.4995/agt.2002.2116

Keywords:

Complexity space, Quasi-norm, Quasi-metric, biBanach space, Smyth complete

Abstract

The complexity (quasi-metric) space was introduced in [23] to study complexity analysis of programs. Recently, it was introduced in [22] the dual complexity (quasi-metric) space, as a subspace of the function space [0,) ^ω. Several quasi-metric properties of the complexity space were obtained via the analysis of its dual.

We here show that the structure of a quasi-normed semilinear space provides a suitable setting to carry out an analysis of the dual complexity space. We show that if (E,) is a biBanach space (i.e., a quasi-normed space whose induced quasi-metric is bicomplete), then the function space (B*_E, _B* ) is biBanach, where B*_E = {f : E Σ^âˆž_n=0 2^-n( V ) } and _B* = Σ^âˆž_n=0 2^-n We deduce that the dual complexity space admits a structure of quasinormed semlinear space such that the induced quasi-metric space is order-convex, upper weightable and Smyth complete, not only in the case that this dual is a subspace of [0,)^ω but also in the general case that it is a subspace of F^ω where F is any biBanach normweightable space. We also prove that for a large class of dual complexity (sub)spaces, lower boundedness implies total boundedness. Finally, we investigate completeness of the quasi-metric of uniform convergence and of the Hausdorff quasi-pseudo-metric for the dual complexity space, in the context of function spaces and hyperspaces, respectively.

Downloads

Download data is not yet available.

Author Biographies

Salvador Romaguera, Universitat Politècnica de València

Departamento de Matemática Aplicada

M.P. Schellekens, National University of Ireland

Department of Computation

References

G. Berthiaume, On quasi-uniform hyperspaces, Proc. Amer. Math. Soc. 66 (1977), 335-343. http://dx.doi.org/10.1090/S0002-9939-1977-0482620-9

J. Cao, H.P.A. Künzi, I.L. Reilly and S. Romaguera, Quasi-uniform hyperspaces of compact subsets, Topology Appl. 87 (1998), 117-126. http://dx.doi.org/10.1016/S0166-8641(97)00133-8

M. Davis, R. Sigal and E.J. Weyuker, Computability, Complexity and Languages, Academic Press, 1994.

E. P. Dolzhenko and E. A. Sevast'yanov, Sign-sensitive approximations, the space of sign-sensitive weight. The rigidity and the freedom of a system, Russian Acad. Sci. Dokl. Math. 48 (1994), 397-401.

J. Ferrer, V. Gregori and C. Alegre, Quasi-uniform structures in linear lattices, Rocky Mountain J. Math. 23 (1993), 877-884. http://dx.doi.org/10.1216/rmjm/1181072529

R. C. Flagg and R. D. Kopperman, The asymmetric topology of Computer Science, in: Proc. MFPS 9, S. Brooks et al. editors, Lectures Notes in Computer Science, 802, Springer-Verlag, 1993, 544-553.

P. Fletcher and W. F. Lindgren, Quasi-Uniform Spaces, Marcel Dekker, New York, 1982.

G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Misolave and D. S. Scott, A Compendium of Continuous Lattices, Springer-Verlag, Berlin, Heidelberg, 1980. http://dx.doi.org/10.1007/978-3-642-67678-9

N. Jones, Computability and Complexity from a Programming Perspective, Foundations of Computing series, MIT press, 1997.

K. Keimel and W. Roth, Ordered Cones and Approximation, Springer-Verlag, Berlin, Heidelberg, 1992.

D. Knuth, The Art of Computer Programming, Vol 3, Addison-Wesley, 1973.

H. P. A. Künzi, Nonsymmetric topology, in: Proc. Colloquium on topology, 1993, Szekszárd, Hungary, Colloq. Math. Soc. János Bolyai Math. Studies, 4 (1995), 303-338.

H. P. A. Künzi and S. Romaguera, Spaces of continuous functions and quasi-uniform convergence, Acta Math. Hungar. 75 (1997), 287-298. http://dx.doi.org/10.1023/A:1006593505036

H. P. A. Künzi and C Ryser, The Bourbaki quasi-uniformity, Topology Proc. 20 (1995), 161-183.

H. P. A. Künzi and V. Vajner, Weighted quasi-metric spaces, in: Proc. 8th Summer Conference on General Topology and Appl., Ann. New York Acad. Sci. 728 (1994), 64-77. http://dx.doi.org/10.1111/j.1749-6632.1994.tb44134.x

S. G. Matthews, Partial metric topology, in: Proc. 8th Summer Conference on General Topology and Appl., Ann. New York Acad. Sci. 728 (1994), 183-197. http://dx.doi.org/10.1111/j.1749-6632.1994.tb44144.x

I. L. Reilly, P. V. Subhramanyam and M. K. Vamanamurthy, Cauchy sequences in quasi-pseudo-metric spaces, Monatsh. Math. 93 (1982), 127-140. http://dx.doi.org/10.1007/BF01301400

S. Romaguera, Left K-completeness in quasi-metric spaces, Math. Nachr. 157 (1992), 15-23. http://dx.doi.org/10.1002/mana.19921570103

] S. Romaguera, On hereditary precompactness and completeness in quasi-uniform spaces, Acta Math. Hungar. 73 (1996), 159-178. http://dx.doi.org/10.1007/BF00058951

S. Romaguera and M. Ruiz-Gómez, Bitopologies and quasi-uniformities on spaces of continuous functions, Publ. Math. Debrecen 47 (1995), 81-93.

S. Romaguera and M. Sanchis, Semi-Lipschitz functions and best approximation in quasi-metric spaces, J. Approx. Theory 103 (2000), 292-301. http://dx.doi.org/10.1006/jath.1999.3439

S. Romaguera and M. Schellekens, Quasi-metric properties of complexity spaces, Topology Appl. 98 (1999), 311-322. http://dx.doi.org/10.1016/S0166-8641(98)00102-3

M. Schellekens, The Smyth completion: a common foundation for denotational semantics and complexity analysis, in: Proc. MFPS 11, Electronic Notes in Theoretical Computer Science 1 (1995), 211-232. http://dx.doi.org/10.1016/S1571-0661(04)00029-5

M. Schellekens, On upper weightable spaces, in: Proc. 11th Summer Conference on General Topology and Appl., Ann. New York Acad. Sci. 806 (1996), 348-363. http://dx.doi.org/10.1111/j.1749-6632.1996.tb49180.x

M. Schellekens, Complexity spaces revisited. Extended abstract, in: Proc. 8th Prague Topological Symposium, Topology Atlas, 1996, 337-348.

M. Schellekens, The correspondence between partial metrics and semivaluations, Theoretical Computer Sci., to appear.

M. B. Smyth, Quasi-uniformities: Reconciling domains with metric spaces, in: Proc. MFPS 3, LNCS 298, M. Main et al. editors, Springer, Berlin 1988, 236-253.

M. B. Smyth, Totally bounded spaces and compact ordered spaces as domains of computation, in: Topology and Category Theory in Computer Science, G.M. Reed, A.W. Roscoe and R.F. Wachter editors, Clarendon Press, Oxford 1991, 207-229.

Ph. Sünderhauf, The Smyth-completion of a quasi-uniform space, in: M. Droste and Y. Gurevich editors, Semantics of Programming Languages and Model Theory, Algebra, Logic and Appl., 5, Gordon and Breach Sci. Publ., 1993, 189-212.