The Smyth completion: A common foundation for denotational semantics and complexity analysis. (English) Zbl 0910.68135
Brookes, Steve (ed.) et al., Mathematical foundations of programming semantics. Proceedings of the 11th conference (MFPS), Tulane Univ., New Orleans, LA, USA, March 29 - April 1, 1995. Amsterdam: Elsevier, Electronic Notes in Theoretical Computer Science. 1, 22 p. (1995).
Summary: The Smyth completion introduced by M. B. Smyth provides a topological foundation for denotational semantics. We show that this theory simultaneously provides a topological foundation for the complexity analysis of programs via the new theory of “complexity (distance) spaces”. The complexity spaces are shown to be weightable and thus belong to the class of S-completable quasi-uniform spaces. We show that the S-completable spaces possess a sequential Smyth completion. The applicability of the theory to “ Divide & Conquer” algorithms is illustrated by a new proof (based on the Banach theorem) of the fact that mergesort has optimal asymptotic average running time. For the entire collection see [Zbl 0903.00064
|54E15||Uniform structures and generalizations|