The Smythe completion: A common topological foundation for denotational semantics and complexity analysis

The theory of complexity spaces developed in this thesis provides a new approach to the complexity analysis of Divide & Conquer algorithms, based on the introduction of a quasi-pseudo-metric "the complexity distance" on function spaces. The complexity distance intuitively measures progress made by syntactic transformations in lowering the complexity of programs. As the theory is based on the topological foundation for Denotational Semantics known as the Smyth completion (topological quasi-uniform spaces), a common foundation is obtained for Denotational Semantics and Complexity Analysis. The thesis focuses on the further development of this topological foundation for Complexity Analysis and the related study of the complexity spaces. This involves research on Topology (Nonsymmetric Topology, quasi-uniform spaces) and Computer Science (Denotational Semantics, Complexity Theory). The applicability of the complexity spaces is demonstrated in the context of the Divide & Conquer algorithms. The parallels between Denotational Semantics and Complexity Analysis are illustrated by a new proof of the optimality (in asymptotic average time) of mergesort, based on the Banach Theorem. Several new classes of topological spaces are introduced, motivated by the topological study of the complexity spaces. Topological properties as total boundedness and metrizability of the complexity spaces are analyzed and interpreted from a Computer Science point of view. All axiomatization of the "complexity quasi-uniform spaces" is developed leading to the (partial solution) of an open problem on the characterization of the weightable spaces stated by H. P. Kunzi: to characterize those quasi-uniformities with countable base, induced by a weightable quasi-pseudo-metric. This characterization leads to the notion of a "complexity domain", which is reminiscent of the notion of a semantic domain and the applicability of the complexity domains to the complexity analysis of Divide & Conquer algorithms is illustrated.