Atlas: Topology and Complexity by Michel Schellekens

Atlas home || Conferences | Abstracts | about Atlas

The Eleventh Summer Conference on General Topology and Applications
August 10-13, 1995
University of Southern Maine
Gorham, ME, USA

Organizers
J. Baumgartner, D. Briggs, J. deBakker, B. Flagg, G. Gruenhage, M. Guay, Y. Kong, R. Kopperman, S. Shore, J. Rutten, J. Vaughan

View Abstracts
Conference Homepage

Topology and Complexity
by
Michel Schellekens
Carnegie-Mellon University

The complexity quasi-pseudo-metric spaces were introduced in [4] in order to provide a topological foundation for the complexity analysis of programs. The applicability of the theory to the complexity analysis of Divide & Conquer algorithms has been illustrated and the complexity spaces were in particular shown to be weightable (see also [1], [2] and [3]). We continue the study of the complexity spaces and develop their axiomatization in terms of quasi-uniform spaces with countable base. As the complexity spaces are weightable, this axiomatization amounts to a partial solution of the open problem stated by Kunzi in the survey paper [1]: "Characterize those quasi-uniformities having a countable base which are induced by a weightable quasi-metric". The axiomatization is developed in the theory of "quasi-uniform cones" and leads to a notion of "complexity domain". The complexity spaces are shown to be nonmetrizability and, as part of their topological analysis, several new classes of topological spaces inspired by Computer Science (Complexity Analysis) are introduced and studied.

[1] H. P. Kunzi, Nonsymmetric topology, Proceedings Szekszard Conference, 1993.
[2] H. P. Kunzi, V. Vajner, Weighted quasi-metrics, Proc. Summer Conf. Queens College, Gen. Top. Appl., Proc. NY Acad. Sci, 1993.
[3] S. G. Matthews, Partial metric spaces, research report RR212, University of Warwick, 1992.
[4] S. G. Matthews, The topology of partial metric spaces, research report RR222, University of Warwick, 1992.
[5] M. Schellekens, The Smyth Completion: A Common Foundation for Denotational Semantics and Complexity Analysis, Proceedings of the 11th International Conference on the Mathematical Foundations of Programming Semantics, New Orleans, 1995.

Date received: April 12, 1996