• Login
    View Item 
    •   Academica-e
    • Departamentos y Centros - Sailak eta Ikastegiak
    • Dpto. Estadística, Informática y Matemáticas - Estatistika, Informatika eta Matematika Saila [desde mayo 2018 / 2018ko maiatzetik]
    • Artículos de revista DEIM - EIMS Aldizkari artikuluak
    • View Item
    •   Academica-e
    • Departamentos y Centros - Sailak eta Ikastegiak
    • Dpto. Estadística, Informática y Matemáticas - Estatistika, Informatika eta Matematika Saila [desde mayo 2018 / 2018ko maiatzetik]
    • Artículos de revista DEIM - EIMS Aldizkari artikuluak
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    2019060197_Estevan_OnFixedPoint.pdf (217.6Kb)
    Date
    2019
    Author
    Estevan Muguerza, Asier Upna Orcid
    Miñana, Juan José 
    Valero, Óscar 
    Version
    Acceso abierto / Sarbide irekia
    Type
    Artículo / Artikulua
    Version
    Versión aceptada / Onetsi den bertsioa
    Project Identifier
    ES/1PE/MTM2015-63608-P 
    European Commission/Horizon 2020 Framework Program/779776 openaire
    Impact
     
     
     
    10.1007/s13398-019-00691-8
     
     
     
    Show full item record
    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 i ... [++]
    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. [--]
    Subject
    Partial order, Quasi-metric, Fixed point, Kleene, Asymptotic complexity, Recurrence equation
     
    Publisher
    Springer
    Published in
    RACSAM (2019) 113:3233–3252
    Departament
    Universidad Pública de Navarra. Departamento de Estadística, Informática y Matemáticas / Nafarroako Unibertsitate Publikoa. Estatistika, Informatika eta Matematika Saila / Universidad Pública de Navarra / Nafarroako Unibertsitate Publikoa. INAMAT2 - Institute for Advanced Materials and Mathematics
     
    Publisher version
    https://doi.org/10.1007/s13398-019-00691-8
    URI
    https://hdl.handle.net/2454/36069
    Sponsorship
    A. 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.
    Appears in Collections
    • Investigaciones financiadas por la Unión Europea (OpenAire) - Europar Batasunak finantzatutako ikerketak (OpenAire) [167]
    • Artículos de revista - Aldizkari artikuluak [4344]
    • Artículos de revista DEIM - EIMS Aldizkari artikuluak [221]
    • Artículos de revista INAMAT2 - INAMAT2 aldizkari artikuluak [253]
    Items in Academica-e are protected by copyright with all rights reserved, unless otherwise noted.

     © Universidad Pública de Navarra - Nafarroako Unibertsitate Publikoa
         Repositorio basado en DSpace

    Contact Us | Send Feedback
     

     

    Browse

    All of Academica-eCommunities & CollectionsAuthorsAuthors By Issue DateTitlesSubjectsBy DegreeThis CollectionAuthorsAuthors By Issue DateTitlesSubjectsBy Degree

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

     © Universidad Pública de Navarra - Nafarroako Unibertsitate Publikoa
         Repositorio basado en DSpace

    Contact Us | Send Feedback