Show simple item record

dc.creatorEstevan Muguerza, Asieres_ES
dc.creatorMiñana, Juan Josées_ES
dc.creatorValero, Óscares_ES
dc.date.accessioned2020-01-15T11:54:51Z
dc.date.issued2019
dc.identifier.issn1578-7303
dc.identifier.urihttps://hdl.handle.net/2454/36069
dc.description.abstractThe celebrated Kleene fixed point theorem is crucial in the mathematical modelling of recursive specifications in Denotational Semantics. In this paper we discuss whether the hypothesis of the aforementioned result can be weakened. An affirmative answer to the aforesaid inquiry is provided so that a characterization of those properties that a self-mapping must satisfy in order to guarantee that its set of fixed points is non-empty when no notion of completeness are assumed to be satisfied by the partially ordered set. Moreover, the case in which the partially ordered set is coming from a quasi-metric space is treated in depth. Finally, an application of the exposed theory is obtained. Concretely, a mathematical method to discuss the asymptotic complexity of those algorithms whose running time of computing fulfills a recurrence equation is presented. Moreover, the aforesaid method retrieves the fixed point based methods that appear in the literature for asymptotic complexity analysis of algorithms. However, our new method improves the aforesaid methods because it imposes fewer requirements than those that have been assumed in the literature and, in addition, it allows to state simultaneously upper and lower asymptotic bounds for the running time computing.en
dc.description.sponsorshipA. Estevan acknowledges financial support from Spanish Ministry of Economy and Competitiveness under Grants MTM2015-63608-P (MINECO/FEDER) and ECO2015-65031. J.J. Miñana and O. Valero acknowledge financial support from Spanish Ministry of Science, Innovation and Universities under Grant PGC2018-095709-B-C21 and AEI/FEDER, UE funds. This work is also partially supported by Programa Operatiu FEDER 2014–2020 de les Illes Balears, by project PROCOE/4/2017 (Direcció General d’Innovació i Recerca, Govern de les Illes Balears) and by project ROBINS. The latter has received research funding from the EU H2020 framework under GA 779776.en
dc.format.extent22 p.
dc.format.mimetypeapplication/pdfen
dc.language.isoengen
dc.publisherSpringeren
dc.relation.ispartofRACSAM (2019) 113:3233–3252en
dc.rights© The Royal Academy of Sciences, Madrid 2019en
dc.subjectPartial orderen
dc.subjectQuasi-metricen
dc.subjectFixed pointen
dc.subjectKleeneen
dc.subjectAsymptotic complexityen
dc.subjectRecurrence equationen
dc.titleOn fixed point theory in partially ordered sets and an application to asymptotic complexity of algorithmsen
dc.typeinfo:eu-repo/semantics/articleen
dc.typeArtículo / Artikuluaes
dc.contributor.departmentUniversidad Pública de Navarra. Departamento de Estadística, Informática y Matemáticases_ES
dc.contributor.departmentNafarroako Unibertsitate Publikoa. Estatistika, Informatika eta Matematika Sailaeu
dc.contributor.departmentUniversidad Pública de Navarra / Nafarroako Unibertsitate Publikoa. InaMat - Institute for Advanced Materialses_ES
dc.rights.accessRightsinfo:eu-repo/semantics/embargoedAccessen
dc.rights.accessRightsAcceso embargado / Sarbidea bahitua dagoes
dc.embargo.lift2020-05-08
dc.embargo.terms2020-05-08
dc.identifier.doi10.1007/s13398-019-00691-8
dc.relation.projectIDinfo:eu-repo/grantAgreement/ES/1PE/MTM2015-63608-Pen
dc.relation.projectIDinfo:eu-repo/grantAgreement/EC/H2020/779776en
dc.relation.publisherversionhttps://doi.org/10.1007/s13398-019-00691-8
dc.type.versioninfo:eu-repo/semantics/acceptedVersionen
dc.type.versionVersión aceptada / Onetsi den bertsioaes


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record