Complexity spaces as quantitative domains of computation (Q536037): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Salvador Romaguera / rank | |||
Property / author | |||
Property / author: Michel Schellekens / rank | |||
Property / author | |||
Property / author: Oscar Valero / rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Weng Kin Ho / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 06B35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 54E35 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5888190 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
complexity space | |||
Property / zbMATH Keywords: complexity space / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pointed complexity space | |||
Property / zbMATH Keywords: pointed complexity space / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
continuous domain | |||
Property / zbMATH Keywords: continuous domain / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Scot topology | |||
Property / zbMATH Keywords: Scot topology / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
quantitative domain | |||
Property / zbMATH Keywords: quantitative domain / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
computational complexity | |||
Property / zbMATH Keywords: computational complexity / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Salvador Romaguera / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Michel Schellekens / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Oscar Valero / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2081459260 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A computational model for metric spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sequence spaces and asymmetric norms in the theory of computational complexity. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Applications of the complexity space to the general probabilistic divide and conquer algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Continuous Lattices and Domains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximation of metric spaces by partial metric spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4265595 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Application of Generalized Complexity Spaces to Denotational Semantics via the Domain of Words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2754138 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Partial Metric Topology / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Quasi-metric properties of complexity spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Duality and quasi-normability for complexity spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexity space of partial functions: a connection between complexity analysis and denotational semantics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of the space of complexity partial functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A quantitative computational model for complete partial metric spaces via formal balls / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Smyth Completion / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A characterization of partial metrizability: Domains are quantifiable. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The constructive maximal point space and partial metrizability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Quantitative continuous domains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Partial metrisability of continuous posets / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:58, 4 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complexity spaces as quantitative domains of computation |
scientific article |
Statements
Complexity spaces as quantitative domains of computation (English)
0 references
16 May 2011
0 references
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.
0 references
complexity space
0 references
pointed complexity space
0 references
continuous domain
0 references
Scot topology
0 references
quantitative domain
0 references
computational complexity
0 references
0 references
0 references
0 references