Duality and quasi-normability for complexity spaces

Salvador Romaguera, M.P. Schellekens


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*EB* ) 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.


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

Full Text:



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.

Abstract Views

Metrics Loading ...

Metrics powered by PLOS ALM

Esta revista se publica bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.

Universitat Politècnica de València

e-ISSN: 1989-4147   https://doi.org/10.4995/agt