• Scott's Qualitative Fixed...

Treffer: Scott's Qualitative Fixed Point Technique in Complexity Analysis of Algorithms

Title:
Scott's Qualitative Fixed Point Technique in Complexity Analysis of Algorithms
Authors:
Maria Lopez-Ramirez, Oscar Valero*
Publisher Information:
Zenodo
Publication Year:
2018
Collection:
Zenodo
Subject Terms:
Partial Order, Scott, Kleene, Fixed Point, Denotational Specification, Algorithmic Complexity, Recurrence Equation
Document Type:
Fachzeitschrift article in journal/newspaper
Language:
unknown
Relation:
https://www.boffinaccess.com/advances-in-computer-sciences/scotts-qualitative-fixed-1-101; https://www.boffinaccess.com/advances-in-computer-sciences/scotts-qualitative-fixed-1-101/acs-1-101.pdf; https://zenodo.org/records/7937331; oai:zenodo.org:7937331; https://doi.org/10.31021/acs.20181101
DOI:
10.31021/acs.20181101
Availability:
https://doi.org/10.31021/acs.20181101
https://zenodo.org/records/7937331
Rights:
Creative Commons Attribution 4.0 International ; cc-by-4.0 ; https://creativecommons.org/licenses/by/4.0/legalcode
Accession Number:
edsbas.1607F036
Database:
BASE

Weitere Informationen

In 1972, D.S. Scott developed a qualitative mathematical technique for modeling the meaning of recursive specifications in Deno-tational Semantics. In this paper we show that the same original Scott’s technique remains helpful for Asymptotic Complexity Analy-sis of algorithms requiring really a reduced number of hypotheses and elementary arguments. Thus, we will disclose that such a qualitative approach presents a uni ed mathematical method that is useful for Asymptotic Complexity Analysis and Denotational Semantics. More-over, we will emphasize the introduced technique applying the results to provide the asymptotic complexity (upper and lower bounds) of the running time of computing of a celebrated algorithm. 2010 AMS Classification: 47H10, 54F05, 68N30, 68Q55, 68Q25, 68W40 ; Advances in Computer Sciences (ISSN:2517-5718)