Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1198.68153
Rodr{\'\i}guez-López, J.; Schellekens, M.P.; Valero, O.
An extension of the dual complexity space and an application to computer science.
(English)
[J] Topology Appl. 156, No. 18, 3052-3061 (2009). ISSN 0166-8641

Summary: 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 [{\it S. Romaguera} and {\it M. Schellekens}, Quasi-metric properties of complexity spaces", Topology Appl. 98, No.~1--3, 311--322 (1999; Zbl 0941.54028)]. 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.
MSC 2000:
*68Q25 Analysis of algorithms and problem complexity
54E50 Complete metric spaces
54F05 Ordered topological spaces

Keywords: ordered normed monoid; dual complexity space; extended quasi-metric; right $K$-sequentially complete; interval analysis

Citations: Zbl 0941.54028

Highlights
Master Server