Duality and quasi-normability for complexity spaces

• Romaguera, Salvador ^[1] ; Schellekens, M.P. ^[2]
  1. [1] Universidad Politécnica de Valencia

     Universidad Politécnica de Valencia

     Valencia, España

     
  2. [2] National University of Ireland

     National University of Ireland

     Irlanda

     
• Localización: Applied general topology, ISSN-e 1989-4147, ISSN 1576-9402, Vol. 3, Nº. 1, 2002, págs. 91-112
• Idioma: inglés
• DOI: 10.4995/agt.2002.2116
• Enlaces
  • Texto completo
• Resumen

  • 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.

• Referencias bibliográficas
  • 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...
  • 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...
  • 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,...
  • 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,...
  • 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....
  • S. G. Matthews, Partial metric topology, in: Proc. 8th Summer Conference on General Topology and Appl., Ann. New York Acad. Sci. 728 (1994),...
  • I. L. Reilly, P. V. Subhramanyam and M. K. Vamanamurthy, Cauchy sequences in quasi-pseudo-metric spaces, Monatsh. Math. 93 (1982), 127-140....
  • 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....
  • 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...
  • M. Schellekens, On upper weightable spaces, in: Proc. 11th Summer Conference on General Topology and Appl., Ann. New York Acad. Sci. 806 (1996),...
  • 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...
  • M. B. Smyth, Totally bounded spaces and compact ordered spaces as domains of computation, in: Topology and Category Theory in Computer Science,...
  • Ph. Sünderhauf, The Smyth-completion of a quasi-uniform space, in: M. Droste and Y. Gurevich editors, Semantics of Programming Languages and...