An Application of Generalized Complexity Spaces to Denotational Semantics via the Domain of Words

摘要

In 1995 M. Schellekens introduced the theory of complexity spaces as a part of the development of a mathematical (topological) foundation for the complexity analysis of programs and algorithms [Electronic Notes in Theoret. Comput. Sci. 1 (1995), 211-232]. This theory is based on the structure of quasi-metric spaces which allow to measure relative progress made in lowering the complexity when a program is replaced by another one. In his paper, Schellekens showed the applicability of the theory of complexity spaces to the analysis of Divide & Conquer algorithms. Later on, S. Romaguera and Schellekens introduced the socalled dual (quasi-metric) complexity space in order to obtain a more robust mathematical structure for the complexity analysis of programs and algorithms [Topology Appl. 98 (1999), 311-322]. They studied some properties of the original complexity space, which are interesting from a computational point of view, via the analysis of the dual ones and they also gave an application of the dual approach to the complexity analysis of Divide and Conquer algorithms. Most recently, Romaguera and Schellekens introduced and studied a general complexity framework which unifies the original complexity space and the dual one under the same formalism [Quaestiones Mathematicae 23 (2000), 359-374]. Motivated by the former work we present an extension of the generalized complexity spaces of Romaguera and Schellekens and we show, by means of the so-called domain of words, that the new complexity approach is suitable to provide quantitative computational models in Theoretical Computer Science. In particular our new complexity framework is shown to be an appropriate tool to model the meaning of while-loops in formal analysis of high-level programming languages.