Skip to Main content Skip to Navigation
Conference papers

Descriptive complexity on non-Polish spaces

Antonin Callard 1 Mathieu Hoyrup 1
1 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Represented spaces are the spaces on which computations can be performed. We investigate the descriptive complexity of sets in represented spaces. We prove that the standard representation of a countably-based space preserves the effective descriptive complexity of sets. We prove that some results from descriptive set theory on Polish spaces extend to arbitrary countably-based spaces. We study the larger class of coPolish spaces, showing that their representation does not always preserve the complexity of sets, and we relate this mismatch with the sequential aspects of the space. We study in particular the space of polynomials.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-02298815
Contributor : Mathieu Hoyrup <>
Submitted on : Monday, January 13, 2020 - 10:37:17 AM
Last modification on : Wednesday, March 18, 2020 - 3:51:25 PM
Long-term archiving on: : Tuesday, April 14, 2020 - 2:23:47 PM

File

final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Antonin Callard, Mathieu Hoyrup. Descriptive complexity on non-Polish spaces. STACS 2020 - 37th Symposium on Theoretical Aspects of Computer Science, Mar 2020, Montpellier, France. pp.16, ⟨10.4230/LIPIcs.STACS.2020.8⟩. ⟨hal-02298815v3⟩

Share

Metrics

Record views

193

Files downloads

223