The Smyth completion: a common foundation for denotational semantics and complexity analysis. (English) Zbl 0910.68135

Schellekens, Michel

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, 535-556 (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].

MSC:

68Q55	Semantics in the theory of computing
54E15	Uniform structures and generalizations
68Q25	Analysis of algorithms and problem complexity

Keywords:

denotational semantics; complexity analysis of programs

References:

[1]	Aho, V.; Hopcroft, J.; Ullman, J., Datastructures and algorithms (1987), Addison-Wesley
[2]	Bjerner, B., Time complexity of programs in type theory (1989), University of Goteborg
[3]	Davis, M.; Weyuker, E., Computability, complexity and languages (1983), N.Y. Academic Press · Zbl 0569.68042
[4]	A. Di Concilio, Spazi quasimetrici e topologie ad essi associate, Accademia di Scienze Fisiche e Matematiche, Lettere ed Arti in Napoli, Serie 4 - Vol. XXXVIII, 1971.; A. Di Concilio, Spazi quasimetrici e topologie ad essi associate, Accademia di Scienze Fisiche e Matematiche, Lettere ed Arti in Napoli, Serie 4 - Vol. XXXVIII, 1971.
[5]	Dugundji, J., Topology (1966), Allyn and Bacon, Inc: Allyn and Bacon, Inc Boston · Zbl 0144.21501
[6]	Fletcher, P.; Lindgren, W., Quasi-uniform spaces (1982), Marcel Dekker, Inc: Marcel Dekker, Inc NY · Zbl 0402.54024
[7]	D. Knuth, The art of computer programming vol. 3, 1973, Addison-Wesley.; D. Knuth, The art of computer programming vol. 3, 1973, Addison-Wesley. · Zbl 0302.68010
[8]	H. P. Kunzi, Nonsymmetric Topology, Proceedings Szekszard Conference, 1993.; H. P. Kunzi, Nonsymmetric Topology, Proceedings Szekszard Conference, 1993.
[9]	Kunzi, H. P., Complete quasi-pseudo-metric spaces, Acta Math. Hung, 59 (1992) · Zbl 0784.54026
[10]	H.P. Kunzi, V. Vajner, Weighted quasi-metrics, Proc. Summer Conf. Queens College, Gen. Top. Appl, 1993, Proc. NY Acad. Sci.; H.P. Kunzi, V. Vajner, Weighted quasi-metrics, Proc. Summer Conf. Queens College, Gen. Top. Appl, 1993, Proc. NY Acad. Sci. · Zbl 0915.54023
[11]	Li, Ming; Vitanyi, P., An introduction to Kolmogorov Complexity and its applications (1993), Springer Verlag · Zbl 0805.68063
[12]	Nachbin, L., (Topology and order, New York Mathematical Studies, vol. 4 (1965), Princeton: Princeton N.J) · Zbl 0134.12603
[13]	S.G. Matthews, Partial metric spaces, research report RR212, 1992, University of Warwick.; S.G. Matthews, Partial metric spaces, research report RR212, 1992, University of Warwick.
[14]	S.G. Matthews, The topology of partial metric spaces, research report RR222, 1992, University of Warwick.; S.G. Matthews, The topology of partial metric spaces, research report RR222, 1992, University of Warwick.
[15]	M. Smyth, Completeness of quasi-uniform and syntopological spaces, manuscript, Imperial College.; M. Smyth, Completeness of quasi-uniform and syntopological spaces, manuscript, Imperial College. · Zbl 0798.54036
[16]	Smyth, M., Quasi-uniformities: Reconciling domains with metric spaces (1987), Springer Verlag: Springer Verlag LNCS 298 · Zbl 0668.54018
[17]	Smyth, M., (Totally bounded spaces and compact ordered spaces as domains of computation, Topology and Category Theory in Computer Science (1991), Oxford University Press: Oxford University Press Oxford), 207-229 · Zbl 0733.54024
[18]	P. Sünderhauf, The Smyth completion of a quasi-uniform space, preprint 1427, 1991, Technische Hochschule Darmstadt.; P. Sünderhauf, The Smyth completion of a quasi-uniform space, preprint 1427, 1991, Technische Hochschule Darmstadt.
[19]	P. Sünderhauf, Quasi-uniform completeness in terms of Cauchy nets, preprint 1529, 1992, Technische Hochschule Darmstadt.; P. Sünderhauf, Quasi-uniform completeness in terms of Cauchy nets, preprint 1529, 1992, Technische Hochschule Darmstadt.