Skip to Main content Skip to Navigation
Conference papers

Descriptive complexity on non-Polish spaces II

Mathieu Hoyrup 1
1 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : This article is a study of descriptive complexity of subsets of represented spaces. Two competing measures of descriptive complexity are available. The first one is topological and measures how complex it is to obtain a set from open sets using boolean operations. The second one measures how complex it is to test membership in the set, and we call it symbolic complexity because it measures the complexity of the symbolic representation of the set. While topological and symbolic complexity are equivalent on countably-based spaces, they differ on more general spaces. Our investigation is aimed at explaining this difference and highly suggests that it is related to the well-known mismatch between topological and sequential aspects of topological spaces.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-02483114
Contributor : Mathieu Hoyrup <>
Submitted on : Tuesday, February 18, 2020 - 1:56:37 PM
Last modification on : Monday, January 4, 2021 - 2:31:11 PM
Long-term archiving on: : Tuesday, May 19, 2020 - 3:16:41 PM

File

full.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Mathieu Hoyrup. Descriptive complexity on non-Polish spaces II. ICALP, Jul 2020, Saarbrücken, Germany. ⟨10.4230/LIPIcs.ICALP.2020.132⟩. ⟨hal-02483114⟩

Share

Metrics

Record views

95

Files downloads

179