The Smyth Completion

摘要: Abstract The Smyth completion ([15], [16], [18] and [19]) provides a topological foundation for Denotational Semantics. We show that this theory simultaneously the complexity analysis of programs via new “complexity (distance) spaces”. spaces are shown to be weightable ([13], [8], [10]) thus belong class S-completable quasi-uniform ([19]). possess sequential completion. applicability “Divide & Conquer” algorithms is illustrated by proof (based on Banach theorem) fact mergesort has optimal asymptotic average running time.