- -

New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

  • Estadisticas de Uso

New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces

Show full item record

Romaguera Bonilla, S.; Tirado Peláez, P.; Valero Sierra, Ó. (2012). New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces. International Journal of Computer Mathematics. 89(13-14):1728-1741. https://doi.org/10.1080/00207160.2012.659246

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/46842

Files in this item

Item Metadata

Title: New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces
Author: Romaguera Bonilla, Salvador Tirado Peláez, Pedro Valero Sierra, Óscar
UPV Unit: Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada
Issued date:
Abstract:
Schellekens [The Smyth completion: A common foundation for denotational semantics and complexity analysis, Electron. Notes Theor. Comput. Sci. 1 (1995), pp. 211-232.] introduced the theory of complexity (quasi-metric) ...[+]
Subjects: Quasi-metric , Complexity space , Fixed Point , Improver , Worsener , Complexity class , Quicksort , Hanoi , Largetwo
Copyrigths: Reserva de todos los derechos
Source:
International Journal of Computer Mathematics. (issn: 0020-7160 )
DOI: 10.1080/00207160.2012.659246
Publisher:
Taylor & Francis Ltd
Publisher version: http://dx.doi.org/10.1080/00207160.2012.659246
Project ID:
info:eu-repo/grantAgreement/MICINN//MTM2009-12872-C02-01/ES/Construccion De Casi-Metricas Fuzzy, De Distancias De Complejidad Y De Dominios Cuantitativos. Aplicaciones/
Thanks:
The authors are thankful for the support from the Spanish Ministry of Science and Innovation, grant MTM2009-12872-C02-01.
Type: Artículo

References

Cerdà-Uguet, M. A., Schellekens, M. P., & Valero, O. (2011). The Baire Partial Quasi-Metric Space: A Mathematical Tool for Asymptotic Complexity Analysis in Computer Science. Theory of Computing Systems, 50(2), 387-399. doi:10.1007/s00224-010-9310-7

Cull, P., & Ecklund, E. F. (1985). Towers of Hanoi and Analysis of Algorithms. The American Mathematical Monthly, 92(6), 407. doi:10.2307/2322448

García-Raffi, L. M., Romaguera, S., & Sánchez-Pérez, E. A. (2002). Sequence spaces and asymmetric norms in the theory of computational complexity. Mathematical and Computer Modelling, 36(1-2), 1-11. doi:10.1016/s0895-7177(02)00100-0 [+]
Cerdà-Uguet, M. A., Schellekens, M. P., & Valero, O. (2011). The Baire Partial Quasi-Metric Space: A Mathematical Tool for Asymptotic Complexity Analysis in Computer Science. Theory of Computing Systems, 50(2), 387-399. doi:10.1007/s00224-010-9310-7

Cull, P., & Ecklund, E. F. (1985). Towers of Hanoi and Analysis of Algorithms. The American Mathematical Monthly, 92(6), 407. doi:10.2307/2322448

García-Raffi, L. M., Romaguera, S., & Sánchez-Pérez, E. A. (2002). Sequence spaces and asymmetric norms in the theory of computational complexity. Mathematical and Computer Modelling, 36(1-2), 1-11. doi:10.1016/s0895-7177(02)00100-0

García-Raffi, L. M., Romaguera, S., & Schellekens, M. P. (2008). Applications of the complexity space to the General Probabilistic Divide and Conquer Algorithms. Journal of Mathematical Analysis and Applications, 348(1), 346-355. doi:10.1016/j.jmaa.2008.07.026

Künzi, H.-P. A. (2001). Nonsymmetric Distances and Their Associated Topologies: About the Origins of Basic Ideas in the Area of Asymmetric Topology. History of Topology, 853-968. doi:10.1007/978-94-017-0470-0_3

Rodríguez-López, J., Romaguera, S., & Valero, O. (2008). Denotational semantics for programming languages, balanced quasi-metrics and fixed points. International Journal of Computer Mathematics, 85(3-4), 623-630. doi:10.1080/00207160701210653

Rodríguez-López, J., Schellekens, M. P., & Valero, O. (2009). An extension of the dual complexity space and an application to Computer Science. Topology and its Applications, 156(18), 3052-3061. doi:10.1016/j.topol.2009.02.009

Romaguera, S., & Schellekens, M. (1999). Quasi-metric properties of complexity spaces. Topology and its Applications, 98(1-3), 311-322. doi:10.1016/s0166-8641(98)00102-3

Romaguera, S., & Valero, O. (2008). On the structure of the space of complexity partial functions. International Journal of Computer Mathematics, 85(3-4), 631-640. doi:10.1080/00207160701210117

Romaguera, S., Schellekens, M. P., & Valero, O. (2011). The complexity space of partial functions: a connection between complexity analysis and denotational semantics. International Journal of Computer Mathematics, 88(9), 1819-1829. doi:10.1080/00207161003631885

Schellekens, M. (1995). The Smyth Completion. Electronic Notes in Theoretical Computer Science, 1, 535-556. doi:10.1016/s1571-0661(04)00029-5

Scott, D. S. 1970. Outline of a mathematical theory of computation. Proceedings of the 4th Annual Princeton Conference on Information Sciences and Systems. March26–271970, Princeton, NJ. pp.169–176.

[-]

recommendations

 

This item appears in the following Collection(s)

Show full item record