The complexity space of partial functions: a connection between complexity analysis and denotational semantics

Abstract

The study of the dual complexity space, introduced by S. Romaguera and M.P. Schellekens [Quasi-metric properties of complexity spaces, Topol. Appl. 98 (1999), pp. 311–322], constitutes a part of the interdisciplinary research on Computer Science and Topology. The relevance of this theory is given by the fact that it allows one to apply fixed point techniques of denotational semantics to complexity analysis. Motivated by this fact and with the intention of obtaining a mixed framework valid for both disciplines, a new complexity space formed by partial functions was recently introduced and studied by S. Romaguera and O. Valero [On the structure of the space of complexity partial functions, Int. J. Comput. Math. 85 (2008), pp. 631–640]. An application of the complexity space of partial functions to model certain processes that arise, in a natural way, in symbolic computation was given in the aforementioned reference. In this paper, we enter more deeply into the relationship between semantics and complexity analysis of programs. We construct an extension of the complexity space of partial functions and show that it is, at the same time, an appropriate mathematical tool for the complexity analysis of algorithms and for the validation of recursive definitions of programs. As applications of our complexity framework, we show the correctness of the denotational specification of the factorial function and give an alternative formal proof of the asymptotic upper bound for the average case analysis of Quicksort.

Keywords:

• ordered cone
• extended quasi-metric
• complexity space
• fixed point
• recursive specification
• factorial function
• denotational semantics
• complexity analysis
• Quicksort

2000 AMS Subject Classifications :

• 06F05
• 54E50
• 54C35
• 68Q25
• 68Q55
• 68Q45

Acknowledgements

The first and the third authors acknowledge the support of the Spanish Ministry of Science and Innovation, and FEDER, grant MTM2009-12872-C02-01 (subprogram MTM), and the support of Generalitat Valenciana, grant ACOMP2009/005. The second author acknowledges the support of the Science Foundation Ireland, SFI Principal Investigator Grant 07/IN.1/I977.