2026-05-21T23:37:34Zhttps://repisalud.isciii.es/rest/oai/requestoai:repisalud.isciii.es:20.500.12105/228172024-11-28T20:00:44Zcom_20.500.12105_15322com_20.500.12105_2051col_20.500.12105_16967
Repisalud
author
Estevan, Asier
author
Miñana, Juan-José
author
Valero, Oscar
2024-09-10T13:10:35Z
2024-09-10T13:10:35Z
2019-10
Estevan Asier, Miñana Prats Juan José, Valero Oscar. On fixed point theory in partially ordered sets and an application to asymptotic complexity of algorithms. Rev Real Acad Cienc Exactas Fis Nat Ser A-Mat. 2019 Oct;113(4):3233-3252.
10.1007/s13398-019-00691-8
1579-1505
1578-7303
Revista de la Real Academia de Ciencias Exactas Fisicas y Naturales Serie A-Matematicas
http://hdl.handle.net/20.500.13003/14764
2-s2.0-85066026409
https://hdl.handle.net/20.500.12105/22817
483725900020
The celebrated Kleene fixed point theorem is crucial in the mathematical modelling of recursive specifications in Denotational Semantics. In this paperwe 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-emptywhen 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 basedmethods 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.
eng
Partial order
Quasi-metric
Fixed point
Kleene
Asymptotic complexity
Recurrence equation
On fixed point theory in partially ordered sets and an application to asymptotic complexity of algorithms
research article