Mostrar el registro sencillo del ítem
dc.contributor.author | Romaguera Bonilla, Salvador | es_ES |
dc.contributor.author | Schellekens, M. | es_ES |
dc.contributor.author | Valero Sierra, Óscar | es_ES |
dc.date.accessioned | 2015-02-09T10:43:28Z | |
dc.date.available | 2015-02-09T10:43:28Z | |
dc.date.issued | 2011 | |
dc.identifier.issn | 0020-7160 | |
dc.identifier.uri | http://hdl.handle.net/10251/46840 | |
dc.description.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. | es_ES |
dc.description.sponsorship | 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. | en_EN |
dc.language | Inglés | es_ES |
dc.publisher | Taylor & Francis Ltd | es_ES |
dc.relation.ispartof | International Journal of Computer Mathematics | es_ES |
dc.rights | Reserva de todos los derechos | es_ES |
dc.subject | Ordered cone | es_ES |
dc.subject | Extended quasi-metric | es_ES |
dc.subject | Complexity space | es_ES |
dc.subject | Fixed point | es_ES |
dc.subject | Recursive specification | es_ES |
dc.subject | Factorial function | es_ES |
dc.subject | Denotational semantics | es_ES |
dc.subject | Complexity analysis | es_ES |
dc.subject | Quicksort | es_ES |
dc.subject.classification | MATEMATICA APLICADA | es_ES |
dc.title | The complexity space of partial functions: A connection between Complexity Analysis and Denotational Semantics | es_ES |
dc.title.alternative | fixed point | es_ES |
dc.type | Artículo | es_ES |
dc.identifier.doi | 10.1080/00207161003631885 | |
dc.relation.projectID | info:eu-repo/grantAgreement/MICINN//MTM2009-12872-C02-01/ES/Construccion De Casi-Metricas Fuzzy, De Distancias De Complejidad Y De Dominios Cuantitativos. Aplicaciones/ | es_ES |
dc.relation.projectID | info:eu-repo/grantAgreement/SFI/SFI Principal Investigator Programme (PI)/07%2FIN.1%2FI977/IE/Expanding the scope and applicability of static average-case analysis via MOQA/ | |
dc.relation.projectID | info:eu-repo/grantAgreement/GVA//ACOMP%2F2009%2F005/ | es_ES |
dc.rights.accessRights | Abierto | es_ES |
dc.contributor.affiliation | Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada | es_ES |
dc.description.bibliographicCitation | Romaguera Bonilla, S.; Schellekens, M.; Valero Sierra, Ó. (2011). The complexity space of partial functions: A connection between Complexity Analysis and Denotational Semantics. International Journal of Computer Mathematics. 88(9):1819-1829. https://doi.org/10.1080/00207161003631885 | es_ES |
dc.description.accrualMethod | S | es_ES |
dc.relation.publisherversion | http://dx.doi.org/10.1080/00207161003631885 | es_ES |
dc.description.upvformatpinicio | 1819 | es_ES |
dc.description.upvformatpfin | 1829 | es_ES |
dc.type.version | info:eu-repo/semantics/publishedVersion | es_ES |
dc.description.volume | 88 | es_ES |
dc.description.issue | 9 | es_ES |
dc.relation.senia | 193397 | |
dc.contributor.funder | Ministerio de Ciencia e Innovación | es_ES |
dc.contributor.funder | Generalitat Valenciana | es_ES |
dc.contributor.funder | Science Foundation Ireland | |
dc.description.references | De Bakker, J. W., & de Vink, E. P. (1998). Denotational models for programming languages: applications of Banach’s Fixed Point Theorem. Topology and its Applications, 85(1-3), 35-52. doi:10.1016/s0166-8641(97)00140-5 | es_ES |
dc.description.references | Emerson, E. A., & Jutla, C. S. (1999). The Complexity of Tree Automata and Logics of Programs. SIAM Journal on Computing, 29(1), 132-158. doi:10.1137/s0097539793304741 | es_ES |
dc.description.references | Flajolet, P., & Golin, M. (1994). Mellin transforms and asymptotics. Acta Informatica, 31(7), 673-696. doi:10.1007/bf01177551 | es_ES |
dc.description.references | 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 | es_ES |
dc.description.references | García-Raffi, L. M., Romaguera, S., & Sánchez-Pérez, E. A. (2003). The supremum asymmetric norm on sequence algebras. Electronic Notes in Theoretical Computer Science, 74, 39-50. doi:10.1016/s1571-0661(04)80764-3 | es_ES |
dc.description.references | García-Raffi, L. M., Romaguera, S., Sánchez-Pérez, E. A. and Valero, O. Normed Semialgebras: A Mathematical Model for the Complexity Analysis of Programs and Algorithms. Proceedings of The 7th World Multiconference on Systemics, Cybernetics and Informatics (SCI 2003), Orlando, Florida, USA. Edited by: Callaos, N., Di Sciullo, A. M., Ohta, T. and Liu, T.K. Vol. II, pp.55–58. Orlando, FL: International Institute of Informatics and Systemics. | es_ES |
dc.description.references | Den Hartog, J. I., de Vink, E. P., & de Bakker, J. W. (2001). Metric Semantics and Full Abstractness for Action Refinement and Probabilistic Choice. Electronic Notes in Theoretical Computer Science, 40, 72-99. doi:10.1016/s1571-0661(05)80038-6 | es_ES |
dc.description.references | 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 | es_ES |
dc.description.references | Medina, J., Ojeda-Aciego, M. and Ruiz-Calviño, J. A fixed point theorem for multi-valued functions with an application to multilattice-based logic programming. Applications of Fuzzy Sets Theory: 7th International Workshop on Fuzzy Logic and Applications, WILF 2007, Camogli, Italy, July 7–10, 2007, Proceedings. Edited by: Masulli, F., Mitra, S. and Pasi, G. Vol. 4578, pp.37–44. Berlin: Springer-Verlag. Notes in Artificial Intelligence | es_ES |
dc.description.references | O’Keeffe, M., Romaguera, S., & Schellekens, M. (2003). Norm-weightable Riesz Spaces and the Dual Complexity Space. Electronic Notes in Theoretical Computer Science, 74, 105-121. doi:10.1016/s1571-0661(04)80769-2 | es_ES |
dc.description.references | Rodríguez-López, J., Romaguera, S., & Valero, O. (2004). Asymptotic Complexity of Algorithms via the Nonsymmetric Hausdorff Distance. Computing Letters, 2(3), 155-161. doi:10.1163/157404006778330816 | es_ES |
dc.description.references | 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 | es_ES |
dc.description.references | 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 | es_ES |
dc.description.references | Romaguera, S., & Schellekens, M. (2000). The quasi-metric of complexity convergence. Quaestiones Mathematicae, 23(3), 359-374. doi:10.2989/16073600009485983 | es_ES |
dc.description.references | Romaguera, S., & Schellekens, M. P. (2002). Duality and quasi-normability for complexity spaces. Applied General Topology, 3(1), 91. doi:10.4995/agt.2002.2116 | es_ES |
dc.description.references | 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 | es_ES |
dc.description.references | Romaguera, S., Sánchez-Pérez, E. A., & Valero, O. (2003). The complexity space of a valued linearly ordered set. Electronic Notes in Theoretical Computer Science, 74, 158-171. doi:10.1016/s1571-0661(04)80772-2 | es_ES |
dc.description.references | Schellekens, M. (1995). The Smyth Completion. Electronic Notes in Theoretical Computer Science, 1, 535-556. doi:10.1016/s1571-0661(04)00029-5 | es_ES |
dc.description.references | Schellekens, M. 1995. “The smyth completion: A common topological foundation for denotational semantics and complexity analysis”. Pittsburgh: Carnegie Mellon University. Ph.D. thesis | es_ES |
dc.description.references | Seda, A. K., & Hitzler, P. (2008). Generalized Distance Functions in the Theory of Computation. The Computer Journal, 53(4), 443-464. doi:10.1093/comjnl/bxm108 | es_ES |
dc.description.references | Straccia, U., Ojeda-Aciego, M., & Damásio, C. V. (2009). On Fixed-Points of Multivalued Functions on Complete Lattices and Their Application to Generalized Logic Programs. SIAM Journal on Computing, 38(5), 1881-1911. doi:10.1137/070695976 | es_ES |
dc.description.references | Tennent, R. D. (1976). The denotational semantics of programming languages. Communications of the ACM, 19(8), 437-453. doi:10.1145/360303.360308 | es_ES |
dc.description.references | Tix, R., Keimel, K., & Plotkin, G. (2005). RETRACTED: Semantic Domains for Combining Probability and Non-Determinism. Electronic Notes in Theoretical Computer Science, 129, 1-104. doi:10.1016/j.entcs.2004.06.063 | es_ES |