An extension of the dual complexity space and an application to Computer Science

摘要

In 1999, Romaguera and Schellekens introduced the theory of dual complexity spaces as a part of the development of a mathematical (topological) foundation for the complexity analysis of programs and algorithms [S. Romaguera, M.P. Schellekens, Quasi-metric properties of complexity spaces, Topology Appl. 98 (1999) 311-322], In this work we extend the theory of dual complexity spaces to the case that the complexity functions are valued on an ordered normed monoid. We show that the complexity space of an ordered normed monoid inherits the ordered normed structure. Moreover, the order structure allows us to prove some topological and quasi-metric properties of the new dual complexity spaces. In particular, we show that these complexity spaces are, under certain conditions, Hausdorff and satisfy a kind of completeness. Finally, we develop a connection of our new approach with Interval Analysis.