Complexity spaces as quantitative domains of computation
Complexity spaces offer a domain-theoretic platform to talk about issues of computational complexity by exporting order-theoretic and topological tools. This paper in particular addresses the question of the extent complexity spaces can be incorporated as a quantitative domain. Two classes of complexity spaces are given particular treatment here: (i) pointed complexity spaces, and (ii) the general complexity space. Pointed complexity spaces are natural as most comparison-based sorting algorithms already satisfy the well-known \(\Omega(n \log n)\) lower bound. The important starting point is to pass to defining a quasi-metric space, and to define an order-relation on the complexity space. This initial approach fails to yield a domain structure since continuity fails, though the underlying order is a dcpo. The nice point here is that once we restrict ourselves to the pointed complexity space with a certain lower bound \(f_0\), everything falls in place. Importantly, the pointed complexity space is an \(\omega\)-continuous domain for which the quasi-metric induces the Scott topology. In the perspective of quantitative domain theory, the structure of pointed complexity space has the desirable property that it is a quantifiable domain in the sense of M. Schellekens and a quantitative domain in the sense of (the late) P. Waszkiewicz. Readers who are seeking the connection between the theory of complexity and domain theory should find this paper informative and elegant to read.
- A characterization of partial metrizability: Domains are quantifiable.
- A computational model for metric spaces
- A quantitative computational model for complete partial metric spaces via formal balls
- An Application of Generalized Complexity Spaces to Denotational Semantics via the Domain of Words
- Applications of the complexity space to the general probabilistic divide and conquer algorithms
- Approximation of metric spaces by partial metric spaces
- Continuous Lattices and Domains
- Duality and quasi-normability for complexity spaces
- scientific article; zbMATH DE number 1670818 (Why is no real title available?)
- scientific article; zbMATH DE number 1339873 (Why is no real title available?)
- On the structure of the space of complexity partial functions
- Partial Metric Topology
- Partial metrisability of continuous posets
- Quantitative continuous domains
- Quasi-metric properties of complexity spaces
- Sequence spaces and asymmetric norms in the theory of computational complexity.
- The complexity space of partial functions: a connection between complexity analysis and denotational semantics
- The constructive maximal point space and partial metrizability
- The Smyth Completion
- Characterization of realizable space complexities
- New perspectives of granular computing in relation geometry induced by pairings
- Quasi-metric properties of the dual cone of an asymmetric normed space
- Fixed point theorems in generalized metric spaces with applications to computer science
- A fixed point theorem for preordered complete fuzzy quasi-metric spaces and an application
- On the construction of domains of formal balls for uniform spaces
- An Application of Generalized Complexity Spaces to Denotational Semantics via the Domain of Words
- On fixed point theory in partial metric spaces
- A domain-theoretic approach to fuzzy metric spaces
- scientific article; zbMATH DE number 1258313 (Why is no real title available?)
- scientific article; zbMATH DE number 1543339 (Why is no real title available?)
- Fundamentals of Computation Theory
- Fixed points of contractive maps on dcpo's
- Intrinsic approach spaces on domains
- Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
This page was built for publication: Complexity spaces as quantitative domains of computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q536037)
