The complexity space of partial functions: a connection between complexity analysis and denotational semantics

DOI10.1080/00207161003631885zbMath1237.68104OpenAlexW1993517941MaRDI QIDQ3008383

Oscar Valero, Salvador Romaguera, Michel Schellekens

Publication date: 15 June 2011

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10251/46840

zbMATH Keywords

fixed pointdenotational semanticscomplexity analysisextended quasi-metricfactorial functionQuicksortcomplexity spacerecursive specificationordered cone

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Complete metric spaces (54E50) Semantics in the theory of computing (68Q55) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (9)

A new contribution to the fixed point theory in partial quasi-metric spaces and its applications to asymptotic complexity analysis of algorithms ⋮ A characterization of Smyth complete quasi-metric spaces via Caristi's fixed point theorem ⋮ A characterisation of weightable quasi-metric generating functions ⋮ On Matthews' relationship between quasi-metrics and partial metrics: an aggregation perspective ⋮ Characterizations of quasi-metric and \(G\)-metric completeness involving \(w\)-distances and fixed points ⋮ On quasi-metric aggregation functions and fixed point theorems ⋮ New results on the mathematical foundations of asymptotic complexity analysis of algorithms via complexity spaces ⋮ On Fixed Point Theory in Partially Ordered (Quasi-)metric Spaces and an Application to Complexity Analysis of Algorithms ⋮ Complexity spaces as quantitative domains of computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Denotational models for programming languages: Applications of Banach's fixed point theorem
• Mellin transforms and asymptotics. The mergesort recurrence
• Sequence spaces and asymmetric norms in the theory of computational complexity.
• Quasi-metric properties of complexity spaces
• The quasi-metric of complexity convergence
• On Fixed-Points of Multivalued Functions on Complete Lattices and Their Application to Generalized Logic Programs
• The denotational semantics of programming languages
• The Smyth Completion
• The Complexity of Tree Automata and Logics of Programs
• Metric Semantics and Full Abstractness for Action Refinement and Probabilistic Choice
• Denotational semantics for programming languages, balanced quasi-metrics and fixed points
• On the structure of the space of complexity partial functions

This page was built for publication: The complexity space of partial functions: a connection between complexity analysis and denotational semantics