On fixed point theory in partially ordered sets and an application to asymptotic complexity of algorithms

Date

2019

Authors

Miñana, Juan José
Valero, Óscar

Director

Publisher

Springer
Acceso abierto / Sarbide irekia
Artículo / Artikulua
Versión aceptada / Onetsi den bertsioa

Project identifier

  • MINECO//MTM2015-63608-P/ES/ recolecta
  • European Commission/Horizon 2020 Framework Programme/779776/ openaire
Impacto

Abstract

The 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.

Description

Keywords

Partial order, Quasi-metric, Fixed point, Kleene, Asymptotic complexity, Recurrence equation

Department

Estatistika, Informatika eta Matematika / Institute for Advanced Materials and Mathematics - INAMAT2 / Estadística, Informática y Matemáticas

Faculty/School

Degree

Doctorate program

item.page.cita

item.page.rights

© The Royal Academy of Sciences, Madrid 2019

Los documentos de Academica-e están protegidos por derechos de autor con todos los derechos reservados, a no ser que se indique lo contrario.